《第03章栈与队列剖析》由会员分享，可在线阅读，更多相关《第03章栈与队列剖析（112页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 栈与队列,数据结构电子教案,殷人昆 王 宏,2,栈 队列 栈的应用：表达式求值 栈的应用：递归 队列的应用：打印杨辉三角形 优先级队列,第三章 栈与队列,3,只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO),栈 ( Stack ),退栈,进栈,a0,an-1,an-2,top,bottom,4,template class Stack /栈的类定义 public: Stack() ; /构造函数 virtual void Push(E x) = 0; /进栈 virtual bool Pop(
2、E /判栈满 ；,栈的抽象数据类型,5,#include #include #include “stack.h” template class SeqStack : public Stack /顺序栈类定义 private:,栈的数组存储表示 顺序栈,6,E *elements; /栈元素存放数组 int top; /栈顶指针 int maxSize; /栈最大容量 void overflowProcess(); /栈的溢出处理 public: SeqStack(int sz =50); /构造函数 SeqStack() delete elements; /析构函数 void Push(E x
3、); /进栈 bool Pop(E,7,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,8,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,9,顺序栈的操作,template void SeqStack:overflowProcess() /私有函数：当栈满则执行扩充栈存储空间处理 E *newArray = new E2*maxSize; /创建更大的存储数组 for (int i =
4、 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete elements; elements = newArray; /改变elements指针 ;,10,template void SeqStack:Push(E x) /若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() = true) overflowProcess; /栈满 elements+top = x; /栈顶指针先加1, 再进栈 ; template bool SeqStack:Pop(E,11,template bool S
5、eqstack:getTop(E,12,双栈共享一个栈空间,b0 t0 t1 b1,0 maxSize-1,V,两个栈共享一个数组空间VmaxSize 设立栈顶指针数组 t2 和栈底指针数组 b2 ti和bi分别指示第 i 个栈的栈顶与栈底 初始 t0 = b0 = -1, t1 = b1 = maxSize 栈满条件：t0+1 = t1 /栈顶指针相遇 栈空条件：t0 = b0或t1 = b1 /退到栈底,13,bool push(DualStack ,14,栈的链接存储表示 链式栈,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,top,15,链
6、式栈 (LinkedStack)类的定义,#include #include “stack.h” template struct StackNode /栈结点类定义 private: E data; /栈结点数据 StackNode *link; /结点链指针 public: StackNode(E d = 0, StackNode *next = NULL) : data(d), link(next) ;,16,template class LinkedStack : public Stack /链式栈类定义 private: StackNode *top; /栈顶指针 void outpu
7、t(ostream /退栈,17,bool getTop(E,18,链式栈类操作的实现,template LinkedStack:makeEmpty() /逐次删去链式栈中的元素直至栈顶指针为空。 StackNode *p; while (top != NULL) /逐个结点释放 p = top; top = top-link; delete p; ; template void LinkedStack:Push(E x) /将元素值x插入到链式栈的栈顶,即链头。,19,top = new StackNode (x, top); /创建新结点 assert (top != NULL); /创建
8、失败退出 ; template bool LinkedStack:Pop(E,20,template bool LinkedStack:getTop(E template void LinkedStack:output(ostream& os, StackNode *ptr, int& i) /递归输出栈中所有元素（沿链逆向输出） if (ptr != NULL) ,21,if (ptr-link != NULL) output(os, ptr-link, i+); os data endl; /逐个输出栈中元素的值 ; 问题是：当进栈元素的编号为1, 2, , n时，可能的出栈序列有多少种？
9、,关于栈的进一步讨论,22,设进栈元素数为n，可能出栈序列数为mn: n = 0，m0 = 1: 出栈序列。 n = 1，m1 = 1: 出栈序列1。 n = 2，m2 = 2：= m0*m1+m1*m0 出栈序列中1在第1位。1进 1出 2进 2出，出栈序列为1, 2。= m0*m1= 1 出栈序列中1在第2位。1进 2进 2出 1出，出栈序列为2, 1。= m1*m0 = 1 n = 3，m3 = 5: = m0*m2+m1*m1+m2*m0 出栈序列中1在第1位。后面2个元素有m2 = 2个出栈序列：1, 2, 3, 1, 3, 2。,23,= m0*m2 = 2 出栈序列中1在第2位。
10、1前有2后有3，出栈序列为 2, 1, 3。= m1*m1 = 1 出栈序列中1在第3位。前面2个元素有m2 = 2个出栈序列：2, 3, 1, 3, 2, 1。 = m2*m0 = 2 n = 4，m4 = 14: = m0*m3+m1*m2+m2*m1+m3*m0 出栈序列中1在第1位。后面3个元素有m3 = 5个出栈序列： 1, 2, 3, 4, 1, 2, 4, 3, 1, 3, 2, 4, 1, 3, 4, 2, 1, 4, 3, 2。,24,= m0*m3 = 5 出栈序列中1在第2位。前面有2，后面3、4有m2 = 2个出栈序列: 2, 1, 3, 4, 2, 1, 4, 3。
11、= m1*m2 = 2 出栈序列中1在第3位。前面2、3有m2 = 2个出栈序列，后面有4: 1, 4, 3, 2, 2, 4, 3, 1。 = m2*m1 = 2 出栈序列中1在第4位。前面3个元素有m3 = 5个出栈序列：2, 3, 4, 1, 2, 4, 3, 1, 3, 2, 4, 1, 3, 4, 2, 1, 4, 3, 2, 1。 = m3*m0 = 5,25,一般地，设有 n 个元素按序号1, 2, , n 进栈，轮流让 1在出栈序列的第1, 第2, 第n位，则可能的出栈序列数为： 推导结果为：,26,队列 ( Queue ),定义 队列是只允许在一端删除，在另一端插入的线性表
12、允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out),27,template class Queue public: Queue() ; /构造函数 Queue() ; /析构函数 virtual bool EnQueue(E x) = 0; /进队列 virtual bool DeQueue(E,队列的抽象数据类型,28,#include #include #include “Queue.h” template class SeqQueue : public Queue /队列类定义 protected
13、: int rear, front; /队尾与队头指针 E *elements; /队列存放数组 int maxSize; /队列最大容量 public: SeqQueue(int sz = 10); /构造函数,队列的数组存储表示 顺序队列,29,SeqQueue() delete elements; /析构函数 bool EnQueue(E x); /新元素进队列 bool DeQueue(E,30,队列的进队和出队,front,rear,空队列,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C, D进队,A B C D,front,rear
14、,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,31,队列的进队和出队原则,进队时先将新元素按 rear 指示位置加入，再将队尾指针加一 rear = rear + 1。 队尾指针指示实际队尾的后一位置。 出队时按队头指针指示位置取出元素，再将队头指针进一 front = front + 1， 队头指针指示实际队头位置。 队满时再进队将溢出出错（假溢出） ； 队空时再出队将队空处理。 解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。,32,队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: front = (front+1) % maxSize; 队尾指针进1: re
