三章栈与队列ppt课件

1、第三章 栈与队列山东财经大学管理科学与工程学院3.1 栈的基本概念栈是一种特殊的线性表，是操作受限的线性表，只能在表尾进行插入或删除操作。表首栈顶表尾栈底不含元素的空表称空栈特点先进后出FILO）后进先出LIFO）栈栈S=(a1,a2,an)ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈的基本运算Empty( )判断栈空Full( )判断栈满Top( )返回栈顶元素Push(x)将元素x入栈Pop(x)出栈，并将栈顶元素存入x中栈的应用举例表达式或字符串的括号匹配问题算术表达式(x*(x+y)-z)算术表达式(x+y)*z)(对于给定表达式，从左到右逐字扫描，每个右括号和距他最近的没有配对

2、的左括号匹配。将所有左括号依次放入栈中，遇到右括号，就与栈顶的左括号配对，并将左括号出栈，若最后栈空，则匹配，若栈不为空，则不匹配。top= -1123450栈空栈空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为-1top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为设数组维数为Mtop= -1,栈空，此时出栈，则下溢栈空，此时出栈，则下溢underflow)top=M-1,栈满，此时入栈，则上溢栈满，此时入栈，则上溢overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空3.

3、2 用数组实现栈利用继承派生栈类templateclass Stack：private list /利用list类派生栈类 public: Stack(int mx = 10)：list()max=mx; bool Empty( ) const return list():empty(); bool Full( ) const return size()=max; T Top( ) constreturn back(); Stack& Push(const T& x) push_back(x);return *this; Stack& Pop(T& x)pop_back(x);treturn

4、*this; pivate: int max;用数组实现栈基类定义templateclass Stack public: Stack(int Max = 10); Stack( ) delete stack; bool Empty( ) const return top = -1; bool Full( ) const return top = = MaxTop; T Top( ) const; Stack& Push(const T& x); Stack& Pop(T& x); private: int top; /栈的栈顶元素所在数组分量的下标 int MaxTop; /数组能容纳的栈元素

5、的最大个数 T *stack; / 栈元素数组 ; 构造函数构造一个空栈templateStack:Stack( int Max)MaxTop=max-1;Stack=new TMax;Top=-1;取栈顶元素 返回栈顶元素的值 template T Stack: Top( ) const If(Empty() throw outbounds(); Else return stacktop; 入栈将元素x入栈templateStack& Stack:Push(const T& x) if (Full() throw NoMem( ); stack+top = x; return *this;/

6、时间复杂度为O(1)出栈将栈顶元素出栈，并存入x中templateStack& Stack:Pop(T& x) if (Empty( ) throw OutOfBounds(); x = stacktop -; return *this; /时间复杂度为O(1) 栈的数组实现的优缺点优点所列的7个基本运算都可在O(1)的时间里完成，效率高。缺点为了使每个栈在算法运行过程中不会溢出，通常要为每个栈预置一个较大的栈空间。另一方面，由于各个栈的实际大小在算法运行过程中不断变化。经常会发生其中一个栈满，而另一个栈空的情形，空间利用率低。两个栈共用一个数组的实现2个栈共享一个数组stack0.n利用栈底

7、位置不变的特性，可以将2个栈的栈底分别设在数组stack的两端。然后各自向数组stack的中间伸展，如下图。好处：提高空间利用率，减好处：提高空间利用率，减少栈发生上溢的可能性。少栈发生上溢的可能性。3.3 用指针实现栈链栈用链表作为栈的存储结构链栈结点类定义template class Stack;template class Node friend class Stack; private: T data; Node *next; ;用指针实现栈定义templateclass Stack public: Stack( ) top = 0; /约定空栈时top = 0 Stack( ); b

8、ool Empty( ) const return top = 0; bool Full( ) const; T Top( ) const; Stack& Push(const T& x); Stack& Pop(T& x); private: Node *top; ; / 指向栈顶结点的指针析构函数释放链栈中的所有空间templateStack:Stack()Node*next;While(top)next=top-next；Delet top；top=next；取栈顶元素返回栈顶元素的值templateT Stack: Top( ) constIf(Empty() throw outbou

9、nds();Else return top-data; .栈底栈底toptopxp入栈将元素x入栈为元素x创建一个新结点，然后将新结点插入到原有的栈顶结点之前，并修改栈顶指针，使之指向新的栈顶结点。入栈将元素x入栈templateStack& Stack:Push(const T& x) if Full( ) throw NoMem( ); Node *p = new Node; p-data = x; p-next = top; top = p; return *this; /时间复杂度为O(1) top .栈底栈底topp出栈返回栈顶元素的值将栈顶元素存于x中，修改原有栈顶指针指向栈顶的下

10、一个元素，作为新的栈顶，释放原栈顶结点空间。出栈将栈顶元素出栈，并存入x中templateStack& Stack:Pop(T& x) if (Empty( ) throw OutOfBounds( ); x = top-data; Node *p = top; top = top-next; delete p; return *this; /时间复杂度为O(1) 栈的应用表达式或字符串的括号匹配问题算术表达式(x*(x+y)-z)算术表达式(x+y)*z)(对于给定表达式，从左到右逐字扫描，每个右括号和距他最近的没有配对的左括号匹配。将所有左括号依次放入栈中，遇到右括号，就与栈顶的左括号配对

11、，并将左括号出栈，若最后栈空，则匹配，若栈不为空，则不匹配。括号匹配算法凡出现左括弧，则进栈凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧多余否则和栈顶元素比较，若相匹配，那么“左括弧出栈”否则表明不匹配表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧有余表达式的计算 表达式的三种标识方法： OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法中缀表达式求值从左到右扫描表达式，若当前读入的是操作数，则进操作数NS栈，若读入的符号是运算符，应进行判断：若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”

12、，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。中缀表达式求值实例 计算：2+4-3*6操作数操作数 运算符运算符24+操作数操作数 运算符运算符6-操作数操作数 运算符运算符6-18操作数操作数 运算符运算符-12操作数操作数 运算符运算符6-36*后缀表达式求值1、从左到右读入表达

13、式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算 结果再压入栈4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1后缀表达式求值实例 计算 4+3*5，其后缀表达式为435*+top4top43toptop415top735top193.4 队列的基本概念队列是一种特殊的线性表，是操作受限的线性表队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队首(front)允许删除的一端特点先进先出FIFO）a1 a2 a3.an 入队入队出队出队frontrear队列队列Q=(a1,a2,an)队列的基本运算Empty(

14、 ): 判断队列空Full( ):判断队列满Front( ): 返回队首元素Back():返回队尾元素Push(x):将元素x入队列队尾Pop(x):删除队首元素并存入x中3.5 用指针实现队列template class Node friend class Queue; private: T data; Node *next; ;用指针实现队列定义templateclass Queue public: Queue( ) front = rear = 0; Queue( ); bool Empty( ) const return (front) ? false : true); bool Fu

15、ll( ) const; T Front( ) const; T Back( ) const; Queue& Push(const T& x); Queue& Pop(T& x); private: Node *que_front; / 指向队首结点的指针 Node *que_rear; /指向队尾结点的指针 ; 析构函数释放队列中的所有空间templateQueue:Queue()Node*next;While(que_front)next=que_front-next；Delet que_front；que_front=next；取队首元素 返回队首元素的值 template T Queu

16、e: Front( ) const If(Empty() throw outbounds(); Else return que_front-data; 取队尾元素 返回队尾元素的值 template T Queue: Back( ) const If(Empty() throw outbounds(); Else return que_rear-data; 在队尾插入元素templateQueue& Queue:EnQueue(const T& x) if Full( ) throw NoMem( ); Node *p = new Node; / 创建一个新结点 p-data = x; p-n

17、ext = 0; /在队尾插入新结点 if (front) rear-next = p; /队列非空 else front = p; /空队列 rear = p; return *this; /时间复杂度为O(1)删除队首元素templateQueue& Queue:DeQueue(T& x) if (Empty( ) throw OutOfBounds( ); x = front-data; / 将队首元素存于x中 Node *p = front; front = front-next; delete p; / 删除队首结点 return *this;/时间复杂度为O(1) frontrea

18、rx入队入队xfront rear空队空队fronty z入队入队 xyrearzfrontrearx出队出队yzxfront rear空队列front rearA进队进队Afront rearB进队进队A Bfront rearC, D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F GC D E F Gfront rearH进队进队,溢出溢出队列的顺序存储结构队列的顺序存储方式存在问题设数组维数为M，那么：当front=-1,rear=M-1时，再有元素入队发生溢出溢出当front-1,r

19、ear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列3.6 用循环数组实现队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;实现：利用“模运算入队： rear=(rear+1)%M; sqrear=x;出队： front=(front+1)%M; x=sqfront;0M-11frontrear.队满队空的判断条件J4J5J6012345rearfrontJ4,J5,J6出队出队J7,J8,J9入队入队012345rearfrontJ4J5J6012345rearfrontJ9J8J7解决方案：解

20、决方案：1.另外设一个标志以区别队空、队满另外设一个标志以区别队空、队满2.少用一个元素空间：少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front用循环数组实现队列队列元素的类型：T循环数组的规模: MaxSize存放队列的循环数组：T *queue 指示队首元素的前一个位置的下标：front;指示队尾元素位置的下标： rear;约定：front= rear时为空队列，(rear + 1) % MaxSize = front) 时为满队列。用循环数组实现队列定义templateclass Queue public: Queue(int Max = 10); Queue( ) delete queue; bool Empty( ) const return front = rear; bool Full( ) const return (rear + 1) % MaxSize = front) ? 1 : 0); T Front( ) const; T Back( ) const; Queue& Push(c