三章栈与队列.ppt
三章栈与队列 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望3.1 栈的基本概念栈是一种特殊的线性表，是操作受限的线性表，只能在表尾进行插入或删除操作。表首栈顶表尾栈底不含元素的空表称空栈特点先进后出（FILO）后进先出（LIFO）栈栈S=(a1,a2,an)ana1a2.栈底栈底栈顶栈顶.出栈出栈进栈进栈栈的基本运算Empty()判断栈空Full()判断栈满Top()返回栈顶元素Push(x)将元素x入栈Pop(x)出栈，并将栈顶元素存入x中栈的应用举例表达式或字符串的括号匹配表达式或字符串的括号匹配问题问题算算术术表达式表达式(x*(x+y)-z)(x*(x+y)-z)算术表达式(x+y)*z)(x+y)*z)(对对于于给给定表达式，从左到右逐字定表达式，从左到右逐字扫扫描，每个右括描，每个右括号和距他最近的没有配号和距他最近的没有配对对的左括号匹配。的左括号匹配。将所有左括号依次放入将所有左括号依次放入栈栈中，遇到右括号，就与中，遇到右括号，就与栈顶栈顶的左括号配的左括号配对对，并将左括号出，并将左括号出栈栈，若最后，若最后栈栈空，空，则则匹匹配，若配，若栈栈不不为为空，空，则则不匹配。不匹配。top=-1123450栈空栈空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为-1top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为设数组维数为Mtop=-1,栈空，此时出栈，则下溢（栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空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*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;/数组能容纳的栈元素的最大个数 T*stack;/栈元素数组 ;构造函数构造函数构造一个空栈templateStack:Stack(int Max)MaxTop=max-1;Stack=new TMax;Top=-1;取栈顶元素返回栈顶元素的值templateT Stack:Top()constIf(Empty()throw outbounds();Else return stacktop;入栈将元素x入栈templateStack&Stack:Push(const T&x)if(Full()throw NoMem();stack+top=x;return*this;/时间复杂度为O(1)出栈将栈顶元素出栈，并存入x中templateStack&Stack:Pop(T&x)if(Empty()throw OutOfBounds();x=stacktop-;return*this;/时间复杂度为O(1)栈的数组实现的优缺点优点所列的7个基本运算都可在O(1)的时间里完成，效率高。缺点为了使每个栈在算法运行过程中不会溢出，通常要为每个栈预置一个较大的栈空间。另一方面，由于各个栈的实际大小在算法运行过程中不断变化。经常会发生其中一个栈满，而另一个栈空的情形，空间利用率低。两个栈共用一个数组的实现2个栈共享一个数组stack0.n利用栈底位置不变的特性，可以将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();bool 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 outbounds();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中，修改原有栈顶指针指向栈顶的下一个元素，作为新的栈顶，释放原栈顶结点空间。出栈将栈顶元素出栈，并存入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)(对于给定表达式，从左到右逐字扫描，每个右括号和距他最近的没有配对的左括号匹配。将所有左括号依次放入栈中，遇到右括号，就与栈顶的左括号配对，并将左括号出栈，若最后栈空，则匹配，若栈不为空，则不匹配。括号匹配算法括号匹配算法凡出现左括弧，则进栈凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，u若相匹配，则“左括弧出栈”u否则表明不匹配表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余表达式的计算表达式的三种标识方法：OP+S1+S2 为前缀表示法S1+OP+S2 为中缀表示法S1+S2+OP 为后缀表示法中缀表达式求值从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是运算符，应进行判断：若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。中缀表达式求值实例计算：2+4-3*6操作数操作数 运算符运算符24+操作数操作数 运算符运算符6-操作数操作数 运算符运算符6-18操作数操作数 运算符运算符-12操作数操作数 运算符运算符6-36*后缀表达式求值1、从左到右读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算 结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1后缀表达式求值实例计算 4+3*5，其后缀表达式为435*+top4top43toptop415top735top193.4 队列的基本概念队列是一种特殊的线性表，是操作受限的线性表队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表u队尾(rear)允许插入的一端u队首(front)允许删除的一端特点先进先出（FIFO）a1 a2 a3.an 入队入队出队出队frontrear队列队列Q=(a1,a2,an)队列的基本运算Empty():判断队列空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 Full()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；取队首元素返回队首元素的值templateT Queue:Front()constIf(Empty()throw outbounds();Else return que_front-data;取队尾元素返回队尾元素的值templateT Queue:Back()constIf(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-next=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)frontrearx入入队队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，则：u当front=-1,rear=M-1时，再有元素入队发生溢出溢出u当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列3.6 用循环数组实现队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;实现：利用“模”运算入队：urear=(rear+1)%M;sqrear=x;出队：ufront=(front+1)%M;x=sqfront;0M-11frontrear.队满队空的判断条件J4J5J6012345rearfrontJ4,J5,J6出队出队J7,J8,J9入队入队012345rearfrontJ4J5J6012345rearfrontJ9J8J7解决方案：解决方案：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(const T&x);Queue&Pop(T&x);private:int que_front，que_rear;/指示队首与队尾的游标 int MaxSize;/循环数组的规模 T*queue;/循环数组取队首元素返回队首元素的值templateT Queue:Front()constIf(Empty()throw outbounds();Return queque(que_front+1)%MaxSize;取队尾元素返回队尾元素的值templateT Queue:Back()constIf(Empty()throw outbounds();Else return quequeque_rear;在队尾插入元素templateQueue&Queue:Push(const T&x)if(Full()throw NoMem();que_rear=(que_rear+1)%MaxSize;/使0=que_rear=MaxSize-1 queueque_rear=x;return*this;/时间复杂度为O(1)删除队首元素templateQueue&Queue:Pop(T&x)if(Empty()throw OutOfBounds();que_front=(que_front+1)%MaxSize;/使0=que_front=MaxSize-1 x=queueque_front;return*this;/时间复杂度为O(1)
