第二章第二章 线性表、堆栈和队列线性表、堆栈和队列 2.1 2.1 线性表的定义和基本操作线性表的定义和基本操作线性表的定义和基本操作线性表的定义和基本操作2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构2.3 2.3 线性表的链接存储结构线性表的链接存储结构线性表的链接存储结构线性表的链接存储结构2.4 2.4 复杂性分析复杂性分析复杂性分析复杂性分析2.5 2.5 堆栈堆栈堆栈堆栈2.6 2.6 队列队列队列队列2.5 堆堆 栈栈2.5.1 堆栈的定义和主要操作堆栈的定义和主要操作2.5.2 顺序栈顺序栈2.5.3 链式栈链式栈2.5.4 顺序栈与链式栈的比较顺序栈与链式栈的比较2.5.5 堆栈的应用堆栈的应用1、堆栈的定义、堆栈的定义栈的定义：栈的定义：栈的定义：栈的定义：栈是插入和删除只能在其一端进行的线性表栈是插入和删除只能在其一端进行的线性表栈是插入和删除只能在其一端进行的线性表栈是插入和删除只能在其一端进行的线性表,并按后进先出的原则进行操作。并按后进先出的原则进行操作。并按后进先出的原则进行操作。并按后进先出的原则进行操作。栈顶栈顶栈顶栈顶：进行插入、删除的一端；：进行插入、删除的一端；：进行插入、删除的一端；：进行插入、删除的一端；栈底栈底栈底栈底：另一端；：另一端；：另一端；：另一端；空栈空栈空栈空栈：表中没有元素时。：表中没有元素时。：表中没有元素时。：表中没有元素时。a5a3a2a1 a4进栈进栈出栈出栈栈顶栈顶栈底栈底 例例 线性表线性表 (a1,a2,a5)，进栈出栈情况进栈出栈情况 栈栈的的后后进进先先出出性性：可可以以对对输输入入序序列列部部分分或或全全局局求求逆逆；凡凡符符合合后后进进先先出出性性，都都可可应应用用栈栈，如如十十进进制制数数与与其其它它数数制制的的转转换换、递递归归的实现、算数表达式求值等问题。的实现、算数表达式求值等问题。栈栈的的封封闭闭性性：除除了了栈栈顶顶元元素素外外，其其他他元元素素不不会会被被改改变变。因因而而，栈栈的的封封闭闭性性非非常常好好，使用起来非常安全。使用起来非常安全。2、堆栈的基本操作堆栈的基本操作（1）栈初始化）栈初始化（2）进栈）进栈 Push（3）出栈）出栈 Pop（4）读取栈顶元素）读取栈顶元素 Peek（5）判栈空）判栈空 StackEmpty（6）判栈满）判栈满 StackFull （7）置空栈）置空栈 2.5 堆堆 栈栈2.5.1 堆栈的定义和主要操作堆栈的定义和主要操作2.5.2 顺序栈顺序栈2.5.3 链式栈链式栈2.5.4 顺序栈与链式栈的比较顺序栈与链式栈的比较2.5.5 堆栈的应用堆栈的应用堆栈的顺序存储堆栈的顺序存储 使用数组存放栈元素，使用数组存放栈元素，栈的规模必须小于或等栈的规模必须小于或等于数组的规模，于数组的规模，当栈的规模等于数组的规模时，当栈的规模等于数组的规模时，就不能再向栈中插入元素。就不能再向栈中插入元素。栈顶栈顶所在数组元素的所在数组元素的下标下标：int top;堆栈空堆栈空：top=-1 堆栈满堆栈满：top=MaxStackSize-1 top1230-1top1230ACBtop1230ABtop1230Atop1230-1栈栈内内变变化化情情况况顺序栈顺序栈顺序栈顺序栈AStackAStack的类定义的类定义的类定义的类定义template template class AStack class AStack private:private:int size;int size;/数组的规模数组的规模数组的规模数组的规模 T*stackArray;T*stackArray;/存放堆栈元素的数组存放堆栈元素的数组存放堆栈元素的数组存放堆栈元素的数组 int top;int top;/栈顶所在数组元素的下标栈顶所在数组元素的下标栈顶所在数组元素的下标栈顶所在数组元素的下标public:public:AStackAStack(int MaxStackSize)(int MaxStackSize)/构造函数构造函数构造函数构造函数 size=MaxStackSize;size=MaxStackSize;stackArray=new T MaxStackSize;top=-1;stackArray=new T MaxStackSize;top=-1;AStackAStack()delete stackArray;/()delete stackArray;/析构函数析构函数析构函数析构函数bool Push(const T&item);/向栈顶压入一个元素向栈顶压入一个元素bool Pop(T&item);/从栈顶弹出一个元素从栈顶弹出一个元素bool Peek(T&item)const;/存取栈顶元素存取栈顶元素int IsEmpty(void)const return top=-1;/检测栈是否为空检测栈是否为空int IsFull(void)const return top size-1;/检测栈是否为满检测栈是否为满void clear(void)top-1;/清空栈清空栈;算法算法算法算法 PushPush(A,item)/(A,item)/向顺序栈向顺序栈向顺序栈向顺序栈A A中压入一个元素中压入一个元素中压入一个元素中压入一个元素itemitemP1.P1.栈满？栈满？栈满？栈满？IF top IF top sizesize-1 THEN(PRINT“1 THEN(PRINT“栈满无法压入栈满无法压入栈满无法压入栈满无法压入”.”.RETURN.)RETURN.)P2.P2.入栈入栈入栈入栈 top toptoptop 1./1./更新栈顶元素的下标更新栈顶元素的下标更新栈顶元素的下标更新栈顶元素的下标 Atop Atopitem./item./压入新栈顶元素压入新栈顶元素压入新栈顶元素压入新栈顶元素 top1230-1top1230ABtop1230A堆堆堆堆栈栈栈栈变变变变化化化化情情情情况况况况top1230ACB算法算法 Pop(A.item)/从顺序栈从顺序栈A中弹出栈顶元素，中弹出栈顶元素，并存放在变量并存放在变量item中中P1.栈空？栈空？IF top -1 THEN(PRINT“栈空无法弹出栈空无法弹出”.RETURN.)P2.出栈出栈 itemAtop./保存栈顶元素值保存栈顶元素值 toptop-1./更新栈顶元素的下标更新栈顶元素的下标 top1230ACBtop1230ABtop1230-1top1230A堆堆堆堆栈栈栈栈变变变变化化化化情情情情况况况况算法算法 Peek(A,item)/将顺序栈将顺序栈A的栈顶元素存的栈顶元素存放在变量放在变量item中中P1.栈空？栈空？IF top -1 THEN(PRINT“栈空栈空”.RETURN.)P2.读取栈顶元素读取栈顶元素 itemAtop./保存栈顶元素值保存栈顶元素值 与与pop的区别是什么？的区别是什么？top top top top-1 12.5 堆堆 栈栈2.5.1 堆栈的定义和主要操作堆栈的定义和主要操作2.5.2 顺序栈顺序栈2.5.3 链式栈链式栈2.5.4 顺序栈与链式栈的比较顺序栈与链式栈的比较2.5.5 堆栈的应用堆栈的应用2.5.3 堆栈的链式存储堆栈的链式存储n n用用用用单单单单链链链链表表表表实实实实现现现现堆堆堆堆栈栈栈栈要要要要为为为为每每每每个个个个栈栈栈栈元元元元素素素素分分分分配配配配一一一一个个个个额额额额外外外外的的的的指针空间。指针空间。指针空间。指针空间。n n首首首首先先先先考考考考虑虑虑虑栈栈栈栈顶顶顶顶对对对对应应应应链链链链表表表表的的的的表表表表头头头头还还还还是是是是表表表表尾尾尾尾。因因因因为为为为堆堆堆堆栈栈栈栈主主主主要要要要操操操操作作作作（插插插插入入入入、删删删删除除除除、存存存存取取取取）的的的的对对对对象象象象是是是是栈栈栈栈顶顶顶顶元元元元素素素素，若若若若栈栈栈栈顶顶顶顶对对对对应应应应表表表表尾尾尾尾，则则则则每每每每次次次次操操操操作作作作的的的的时时时时间间间间复复复复杂杂杂杂性性性性为为为为O O(n n)；若若若若栈栈栈栈顶顶顶顶对对对对应应应应表表表表头头头头，则则则则每每每每个个个个操操操操作作作作的的的的时时时时间间间间复复复复杂杂杂杂性性性性是是是是O O(1)(1)，显然，显然，显然，显然，栈顶对应表头是合理的栈顶对应表头是合理的栈顶对应表头是合理的栈顶对应表头是合理的。n n另外，链式栈中不需要哨位结点。另外，链式栈中不需要哨位结点。另外，链式栈中不需要哨位结点。另外，链式栈中不需要哨位结点。链式栈链式栈LStack的类定义的类定义template class LStackprivate:SLNode *top;/栈顶指针指向表头栈顶指针指向表头public:LStack()top=NULL;/构造函数构造函数 LStack()clear();/析构函数析构函数void void clearclear ();();/清空栈清空栈清空栈清空栈bool bool PushPush(const T&item);/(const T&item);/向栈顶压入一个元素向栈顶压入一个元素向栈顶压入一个元素向栈顶压入一个元素bool bool PopPop(T&item);(T&item);/从栈顶弹出一个元素从栈顶弹出一个元素从栈顶弹出一个元素从栈顶弹出一个元素bool bool Peek Peek(T&item)const;(T&item)const;/读取栈顶元素读取栈顶元素读取栈顶元素读取栈顶元素int int IsEmptyIsEmpty(void)const return top=NULL;(void)const return top=NULL;/检测栈是否为空检测栈是否为空检测栈是否为空检测栈是否为空;算法算法算法算法 PushPush(item)/(item)/向栈顶指针为向栈顶指针为向栈顶指针为向栈顶指针为toptop的链式栈中压的链式栈中压的链式栈中压的链式栈中压入一个元素入一个元素入一个元素入一个元素item item P1.P1.创建新结点创建新结点创建新结点创建新结点 s sAVAIL./AVAIL./为新结点申请空间为新结点申请空间为新结点申请空间为新结点申请空间 data(s)data(s)item.next(s)item.next(s)top./top./新结点的数据域新结点的数据域新结点的数据域新结点的数据域存放存放存放存放itemitem，指针域存放原栈顶结点的地址信息，指针域存放原栈顶结点的地址信息，指针域存放原栈顶结点的地址信息，指针域存放原栈顶结点的地址信息P2.P2.更新栈顶指针更新栈顶指针更新栈顶指针更新栈顶指针 top tops./s./更新栈顶指针，令其指向新入栈结点更新栈顶指针，令其指向新入栈结点更新栈顶指针，令其指向新入栈结点更新栈顶指针，令其指向新入栈结点 算法算法算法算法 Pop Pop(item)/(item)/从栈顶指针为从栈顶指针为从栈顶指针为从栈顶指针为toptop的链式栈中弹出栈的链式栈中弹出栈的链式栈中弹出栈的链式栈中弹出栈顶元素，并存放在变量顶元素，并存放在变量顶元素，并存放在变量顶元素，并存放在变量itemitem中中中中P1.P1.栈空？栈空？栈空？栈空？IF top=NULL THEN(PRINT“IF top=NULL THEN(PRINT“栈空无法弹出栈空无法弹出栈空无法弹出栈空无法弹出”.”.RETURN.)RETURN.)P2.P2.出栈出栈出栈出栈 item itemdata(top).data(top)./保存栈顶结点的字段值保存栈顶结点的字段值保存栈顶结点的字段值保存栈顶结点的字段值 q qnext(top).next(top)./令指针令指针令指针令指针q q指向次栈顶结点指向次