第三章栈与队列.ppt
《第三章栈与队列.ppt》由会员分享,可在线阅读,更多相关《第三章栈与队列.ppt(79页珍藏版)》请在三一文库上搜索。
1、第三章 栈与队列,赵建华,栈 队列 栈的应用:表达式求值 栈的应用:递归 优先级队列,第三章 栈与队列,只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top),另一端称 为栈底(bottom) 特点 后进先出 (LIFO),栈 ( Stack ),template class Stack /栈的类定义 public: Stack() ; /构造函数 virtual void Push(T x) = 0; /进栈 virtual bool Pop(T /判栈满 ;,栈的抽象数据类型,top,空栈,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,
2、e,c,d,e 进栈,a,b,d,退栈,c,退栈,f退栈,a,b,a,退栈,top,a,b,退栈,c,top,a,b,f,top,top,b,template class SeqStack : public Stack /顺序栈类定义 private: T *elements; /栈元素存放数组 int top; /栈顶指针 int maxSize; /栈最大容量 void overflowProcess(); /栈的溢出处理 public: ;,栈的数组存储表示 顺序栈,template void SeqStack:Push(T,template bool Seqstack:getTop(T
3、,template void SeqStack:overflowProcess() /私有函数:当栈满则执行扩充栈存储空间处理 T *newArray = new T2*maxSize; /创建更大的存储数组 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete elements; elements = newArray; /改变elements指针 ;,考虑直接使用SeqList实现,class SeqStack : public Stack private: SeqList st; /栈
4、元素存放数组 public: push(T,双栈共享一个栈空间,b0 t0 t1 b1,0 maxSize-1,V,两个栈共享一个数组空间VmaxSize,两个栈的栈底分别位于数组的开头和结尾;分别向中间生长。 主要目的是节约空间: 两个独立栈,预期的最大空间max(size of stack1)+max(size of stack2)。 而双栈空间是max(size of stack1 + size of stack2)。,实现方法,设立栈顶指针数组 t2 和栈底指针数组 b2 ti和bi分别指示第 i 个栈的栈顶与栈底 初始化 t0 = b0 = -1, t1 = b1 = maxSize
5、 栈满条件:t0+1 = t1 /栈顶指针相遇 栈空条件:t0 = b0 t1 = b1 /退到栈底 对第一个栈压栈时:元素放入Vt0+1; 对第二个栈压栈时:元素放入Vt1-1;,bool push(DualStack 可以看到,这个程序实际上就是前面的普通压栈程序; 当i=1时,相当于反向的压栈。,bool Pop(DualStack ,栈的链接存储表示 链式栈,链式栈无栈满问题,空间可扩充 插入与删除仅在栈顶处执行,效率为O(1) 链式栈的栈顶在链头 适合于多栈操作,top,链式栈 (LinkedStack)类的定义,实际上是使用单链表来实现栈的操作 #include #include
6、“stack.h” template struct StackNode /栈结点类定义 private: T data; /栈结点数据 StackNode *link; /结点链指针 public: StackNode(T d = 0, StackNode *next = NULL) : data(d), link(next) ;,template class LinkedStack : public Stack /链式栈类定义 private: StackNode *top; /栈顶指针 void output(ostream,链式栈类操作的实现,LinkedStack:makeEmpty(
7、) /逐次删去链式栈中的元素直至栈顶指针为空。 StackNode *p; while (top != NULL) /逐个结点释放 p = top; top = top-link; delete p; ; 回忆单链表中的makeempty操作 void LinkedStack:Push(T x) /将元素值x插入到链式栈的栈顶,即链头。 top = new StackNode (x, top); /创建新结点,并使得新结点的link执行原来的top assert (top != NULL); /创建失败退出 ; 回忆单链表中的Insert(0,x)操作,bool LinkedStack:Pop
8、(T 回忆单链表中的getData(0, T& x),用LinkList实现栈,template class LinkedStack : public Stack private: LinkList st; /栈中元素; public: void Push(T x)st.Insert(0, x); /进栈 bool Pop(T 注:上面对st的各个成员函数的调用都是O(1)时间的。,队列 ( Queue ),定义 队列是只允许在一端删除,在另一端插入的线性表 允许删除的一端叫做队头(front),允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First O
9、ut),template class Queue public: Queue() ; /构造函数 Queue() ; /析构函数 virtual bool EnQueue(E x) = 0; /进队列 virtual bool DeQueue(E 注:如果需要访问队列内部的元素,或者遍历,那么仍然建议实现Iterator接口,队列的抽象数据类型,使用数组来存放队列中的元素;数组中的元素是循环存放的。 两个指针front和rear指示队列的首尾位置。 如果rear大于front,队列中就包括从front到rear(不含)的元素。 如果rear等于front,表示空表; 如果rear小于front
10、,那么队列中包括从front到数组末尾,再从数组开头到达rear(不含)的数据。 队空:front=rear 队满:(rear+1)%maxSize=front,队列的数组存储表示 顺序队列,队列的进队和出队,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C, D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,front,rear,H进队,C D E F G,H,队头、队尾指针加1时从maxSize-1直接进到0,可用语言的取模(余数)
11、运算实现。 队头指针进1: front = (front+1) % maxSize; 队尾指针进1: rear = (rear+1) % maxSize; 队列初始化:front = rear = 0; 队空条件:front = rear; 队满条件:(rear+1) % maxSize = front,循环队列 (Circular Queue),class SeqQueue : public Queue /队列类定义 protected: int rear, front; /队尾与队头指针 E *elements; /队列存放数组 int maxSize; /队列最大容量 public: S
12、eqQueue(int sz = 10); /构造函数: /申请空间,设置maxSize,front,rear。 SeqQueue() delete elements; /析构函数 bool EnQueue(E x); /新元素进队列 bool DeQueue(E,template bool SeqQueue:EnQueue(E x) /若队列不满, 则将x插入到该队列队尾, 否则返回 if (IsFull() = true) return false; elementsrear = x; /先存入 rear = (rear+1) % maxSize; /尾指针加一 return true;
13、; template bool SeqQueue:DeQueue(E,template bool SeqQueue:getFront(E /在调试版本下,如果elements = NULL会报告错误; ,队列的链接存储表示 链式队列,队头在链头,队尾在链尾。 链式队列在进队时无队满问题,但有队空问题。 队空条件为 front = NULL 此时rear为空?,template struct QueueNode /队列结点类定义 private: E data; /队列结点数据 QueueNode *link; /结点链指针 public: QueueNode(E d = 0, QueueNod
14、e* next = NULL) : data(d), link(next) template class LinkedQueue private: QueueNode *front, *rear; /队头、队尾指针 public: LinkedQueue() : rear(NULL), front(NULL) LinkedQueue(); ;,链式队列类的定义,template LinkedQueue:LinkedQueue() /析构函数 QueueNode *p; while (front != NULL) /逐个结点释放 p = front; front = front-link; de
15、lete p; ; template bool LinkedQueue:EnQueue(T x) /将新元素x插入到队列的队尾 if (front = NULL) /创建第一个结点 front = rear = new QueueNode (x); /保证rear总是指向对尾 if (front = NULL) return false; /分配失败 else /队列不空, 插入 rear-link = new QueueNode (x); if (rear-link = NULL) return false; rear = rear-link; return true; ;,template
16、 /如果队列不空,将队头结点从链式队列中删去 bool LinkedQueue:DeQueue(T,思考题,增加附加的队列头结点能否简化实现? 如使用单链表的Insert(n,X)和Remove(0,X)分别实现EnQueue和DeQueue,效率如何? 带有尾指针的单链表呢?,栈的应用:表达式求值,栈的LIFO特性决定了它比较适合用来处理具有嵌套结构/递归结构的问题: 括号匹配,表达式求值 由于LIFO特性,如果一个应用中总是把前面求出的某个值和后续求出的某个值进行运算得到一个新结果,并且从此之后前面求出的值就不再需要,就可以考虑使用栈来完成计算。 在计算这些值的过程中,可能还需要计算一些中
17、间结果,那么这些中间结果的计算也需要遵循这样的模式。 此时可以把运算分量入栈,然后在计算结果时在栈顶获得运算分量。结果可能还需要入栈。,中缀表达式 a + b * ( c - d ) - e / f 后缀表达式 a b c d - * + e f / - 前缀表达式 - + a * b c d / e f 中缀表达式中相邻两个操作符的计算次序为: 优先级高的先计算 优先级相同的自左向右计算 当使用括号时从最内层括号开始计算 但是括号左边的值的计算可以先期进行,表达式示例,后缀表达式的计算,每个子表达式的计算结果,和下一个并列子表达式的计算结果,根据后续的运算符进行运算,得到较大的子表达式的结果
18、。 从左向右顺序地扫描表达式,并用一个栈暂存扫描到的操作数或计算结果。 计算,rst1,rst2,rst3,rst4,rst5,a b c d - * + e f / -,计算方式,从左到右扫描后缀表达式: 如果是数字(最小的子表达式),压栈 如果是运算符(和前面的子表达式一起,组成一个较大的子表达式),从栈中弹出相应的分量,并计算结果。将结果压栈。 例如:3 5 + 2 * 首先3,5入栈 然后处理+,3、5出栈,得到结果8(3 5 +),再入栈 2入栈 处理*,8,2出栈,得到结果(3 5 + 2 *)16,再入栈,完成。 思考题 如果要把后缀表达式转成中缀表达式,怎么做? 如果利用上面的
19、算法的框架?,中缀表示转后缀表示,中缀表达式: 用+、-连接起来的项的序列; 项: 用*、/连接起来的因子序列 因子: 整数(变量)或括号中的表达式 转化规则 term1 + term2 - term3 term1 term2 + term3 - factor1 * factor2 / factor3 factor1 factor2 * factor3 /,方法(不考虑效率),将中缀到后缀的转换看作是一种运算 普通的+运算是求和 分量的值是其后缀表示,+运算是把分量的后缀表示组合成为新的后缀表示 同样使用栈来存放结果和运算符 栈顶有+号 下一个运算符是+/-/)/#,将两个运算分量相加; 下一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 队列
链接地址:https://www.31doc.com/p-2554000.html