数据结构(第四章-栈和队列)--课件

数据结构第4章栈和队列l现实生活中的一些线性数据结构的事例：l递归问题的解决方法l表达式的计算：如5（43（52）l排队等车的队列l栈和队列的特点：l它们的状态是不断变化的l添加和删除是它们共同的操作l添加和删除在特定的位置（哪些位置？）l考虑：此类数据结构应该对用户提供哪些操作？栈和队列栈和队列栈和队列是在程序设计中被广泛使用的两种特殊的线性表，它们的特殊性在于对栈和队列的插入和删除操作被限制为只能在表的两端（或一端）进行：L=（a1,a2,a3,ai,an）线性表：在表的任意位置进行插入和删除：栈：只能在表尾进行插入和删除：“后进先出”。队列:只能在表尾进行插入,而在表头删除：“先进先出”。和线性表相比，栈和队列的插入和删除操作受更多的约束和限定，故又称为操作受限（或限定性）的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下：线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1/表尾/表尾 Delete(L,i)Delete(S,n)Delete(Q,1)1in/表尾/表头栈和队列主要内容4.1 栈栈4.2 队列队列4.1 栈栈的抽象数据类型 栈的定义栈的定义l栈栈(Stack)(Stack)是一种特殊的线性表，其是一种特殊的线性表，其插入和删除操作只允插入和删除操作只允许在线性表的一端进行。通常称允许插入、删除操作的这许在线性表的一端进行。通常称允许插入、删除操作的这一端为一端为栈顶栈顶(Top)(Top)，不允许操作的一端称为，不允许操作的一端称为栈底栈底(Bottom)(Bottom)。当表中没有元素时称为当表中没有元素时称为空栈空栈。l假设栈假设栈S=(aS=(a0 0，a a1 1，a a2 2，a a3 3，aan-1n-1)，则，则a a0 0称为称为栈底元素栈底元素，a an-1n-1为为栈顶元素栈顶元素，标识栈顶位置的指针称为，标识栈顶位置的指针称为栈顶指针栈顶指针。栈中。栈中元素按元素按a a0 0，a a1 1，a a2 2，a a3 3，a an-1n-1的的次序次序进栈，退栈的第一进栈，退栈的第一个元素应为个元素应为栈顶元素栈顶元素。换句话说，栈的修改是按。换句话说，栈的修改是按后进先出后进先出的原则进行的。因此，栈称为后进先出表（的原则进行的。因此，栈称为后进先出表（LIFOLIFO）。）。栈的操作栈的操作l习惯上将每次删除（也称为退栈）操作又称为习惯上将每次删除（也称为退栈）操作又称为出栈或弹出（出栈或弹出（POP）操作。删除的元素总是当操作。删除的元素总是当前栈中前栈中“最新最新”的元素（栈顶元素）。的元素（栈顶元素）。l每次插入（称为进栈）操作称为每次插入（称为进栈）操作称为入栈或压入入栈或压入（PUSH）操作，入栈的元素总是当前栈中操作，入栈的元素总是当前栈中“最新最新”的元素。的元素。l在空栈中最先插入的元素总被放在栈的底部，在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。只有所有元素被弹出之后它才能被删除。4.1 栈栈的抽象数据类型basebasebasebasebasestacksize入栈示例入栈示例4.1 栈栈的抽象数据类型basebasebasebasebase出栈示例出栈示例4.1 栈栈的抽象数据类型 出、入栈示例出、入栈示例4.1 栈栈的抽象数据类型图图4.1 栈（顺序栈）及其状态变化：栈（顺序栈）及其状态变化：A,B,C,D 入栈入栈,入栈入栈,出栈出栈,入栈入栈,入栈入栈,出栈出栈,出栈出栈,出栈出栈【思考题思考题4-1】入栈入栈A,B,C,D，出栈，出栈A,B,C,D、D,C,B,A？还有哪些？有哪些不可能的出栈序列？为什么？还有哪些？有哪些不可能的出栈序列？为什么？出、入栈示例出、入栈示例4.1 栈栈的抽象数据类型栈的数据元素栈的数据元素 栈的数据元素和线性表的数据元素完全相同，栈的数据元素和线性表的数据元素完全相同，即栈的数据元素是即栈的数据元素是n（n=0）个相同类型的数）个相同类型的数据元素据元素a0，a1，。，。an-1组成的有限序列，组成的有限序列，记为：记为：a0,a1,an-1。l其中，其中，n为数据元素的个数，称为栈的长度。为数据元素的个数，称为栈的长度。n=0时，为空栈。时，为空栈。l考虑考虑：线性表和栈的区别在哪呢？线性表和栈的区别在哪呢？4.1 栈栈的抽象数据类型栈的运算栈的运算l栈的基本运算一般有以下几种：栈的基本运算一般有以下几种：l InitStack（S）构造一个空栈）构造一个空栈S。l StackEmpty（S）判栈空，若）判栈空，若S为空栈返回为空栈返回TRUE，否则返，否则返回回FALSE。l StackFull（S）判栈满，若）判栈满，若S为满栈，则返回为满栈，则返回TRUE，否则，否则返回返回 FALSE。该运算只适用于栈的顺序存储结构。该运算只适用于栈的顺序存储结构。l Push（S，x）入栈。若栈）入栈。若栈S不满，则将元素不满，则将元素x压入压入S的栈顶。的栈顶。l Pop（S）出栈。若栈）出栈。若栈S非空，则将非空，则将S的栈顶元素弹出，并的栈顶元素弹出，并返回该元素。返回该元素。l StackTop（S）取栈的栈顶元素，不修改栈顶指针。）取栈的栈顶元素，不修改栈顶指针。l比较重要的运算就是比较重要的运算就是入栈和出栈入栈和出栈两种。两种。4.1 栈栈的抽象数据类型栈的溢出栈的溢出l当栈满时进栈运算称为当栈满时进栈运算称为“上溢上溢”。l当栈空时退栈运算称为当栈空时退栈运算称为“下溢下溢”。l栈上溢是一种出错状态，应该设法避免之；而下溢栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转则可能是正常现象，通常下溢用来作为程序控制转移的条件。移的条件。4.1 栈栈的抽象数据类型栈抽象数据类型栈抽象数据类型ADT，栈接口，栈接口public interface Stack public abstract boolean isEmpty();/判空 public abstract void push(T x);/x入栈 public abstract T peek();/返回栈顶，未出栈 public abstract T pop();/出栈，返回栈顶4.1 栈栈的抽象数据类型总结总结l栈的运算规则是按后进先出的原则进行的（又称为栈的运算规则是按后进先出的原则进行的（又称为后进先出），简称为后进先出），简称为LIFO（last in first out）表。）表。l就线性表而言，实现栈的方法有很多，就线性表而言，实现栈的方法有很多，由于栈也是由于栈也是线性表，因此线性表的存储结构对栈也适用，线性表，因此线性表的存储结构对栈也适用，我们我们着重介绍着重介绍顺序栈顺序栈（arrary-based stack）和）和链式栈链式栈（linked stack），它们类似于顺序表和链式表。，它们类似于顺序表和链式表。l这两种存储结构的不同，则使得实现栈的基本运算这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。的算法也有所不同。4.1 栈栈的抽象数据类型栈的表示和实现栈的表示和实现4.1 栈栈的抽象数据类型 能否使用一个线性表对象作为栈，或将栈声明为继承线性表？入栈调用insert(0,x)函数，出栈调用remove(0)函数？为什么？【习题解答】都不能。习题习题4.1 栈栈的抽象数据类型l由于栈是运算受限的线性表，因此线性表的存储结构对由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈也适应。l栈的顺序存储结构简称为顺序栈（栈的顺序存储结构简称为顺序栈（Sequential StackSequential Stack），），它是运算受限的线性表。因此，可用它是运算受限的线性表。因此，可用数组数组来实现顺序栈。来实现顺序栈。l因为栈底位置是固定不变的，所以可以将栈底位置设置因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，一般需用一个整型变量退栈操作而变化的，一般需用一个整型变量toptop。顺序栈的定义顺序栈的定义4.1 栈顺序栈顺序栈的操作实例如上图所示顺序栈的操作实例如上图所示4.1 栈顺序栈顺序栈的定义顺序栈的定义n栈的顺序存储结构及操作实现public class SeqStack implements Stack /顺序栈类，实现栈接口 Object element;/存储栈数据元素的数组 int top;/栈顶元素下标n注意：element数组存储栈的数据元素；top表示当前栈顶元素的下标。顺序栈的实现（顺序栈的实现（经典实现经典实现）4.1 栈顺序栈基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）l顺序栈的实现从本质上讲，就是顺序线性表实现的简顺序栈的实现从本质上讲，就是顺序线性表实现的简化。惟一重要的是需要确定应该用数组的哪一端表示化。惟一重要的是需要确定应该用数组的哪一端表示栈顶：栈顶：l一种选择是把数组的第一种选择是把数组的第0个位置作为栈顶。根据线性表的函个位置作为栈顶。根据线性表的函数，所有的插入数，所有的插入(insert)和删除和删除(remove)操作都在第操作都在第0个位个位置的元素上进行。由于这时每次置的元素上进行。由于这时每次push(insert)或者或者pop(remove)操作都需要把当前栈中的所有元素在数组中操作都需要把当前栈中的所有元素在数组中移动一个位置，因此效率不高。如果栈中有移动一个位置，因此效率不高。如果栈中有n个元素，则时个元素，则时间代价为间代价为O(n)。l另一种选择是当栈中有另一种选择是当栈中有n个元素时把位置个元素时把位置n-1作栈顶。也就作栈顶。也就是说，当向栈中压人元素时，把它们添加到线性表的表尾，是说，当向栈中压人元素时，把它们添加到线性表的表尾，成员函数成员函数pop也是删除表尾元素。在这种情况下，每次也是删除表尾元素。在这种情况下，每次push或者或者pop操作的时间代价仅为操作的时间代价仅为O(1)。4.1 栈顺序栈l栈的运算主要考虑栈的入栈和出栈算法：栈的运算主要考虑栈的入栈和出栈算法：l其原因是在栈的基本运算中有六种：判断栈空、栈初始其原因是在栈的基本运算中有六种：判断栈空、栈初始化、判断栈满（化、判断栈满（仅限于顺序存储的情况下仅限于顺序存储的情况下），入栈元素、），入栈元素、出栈元素、取栈顶元素等出栈元素、取栈顶元素等l而入栈时需要考虑的操作步骤是：而入栈时需要考虑的操作步骤是：l栈初始化，然后判断栈是否为满，如果不满，则可以插入栈初始化，然后判断栈是否为满，如果不满，则可以插入元素（入栈）元素（入栈）l出栈时，需要考虑的步骤是：出栈时，需要考虑的步骤是：l判断栈是否为空，如果不空，删除元素（出栈），出栈之判断栈是否为空，如果不空，删除元素（出栈），出栈之前，保存栈顶元素。前，保存栈顶元素。l也就是说，栈的入出栈运算包含了其他的六种基本运算，也就是说，栈的入出栈运算包含了其他的六种基本运算，取栈顶元素的运算，只是不用修改栈顶的指针而已。取栈顶元素的运算，只是不用修改栈顶的指针而已。基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈（1）栈的初始化）栈的初始化 public SeqStack(int size)/构造容量为构造容量为size的空栈的空栈 this.element=new ObjectMath.abs(size);this.top=-1;public SeqStack()/构造默认容量的空栈构造默认容量的空栈 this(64);基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈（2）判读栈是否为空）判读栈是否为空 public boolean isEmpty()/判断栈是否空，若空返回判断栈是否空，若空返回true return this.top=-1;基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈l判读栈是否为满？判读栈是否为满？l本实现采用与顺序表同样的处理：当本实现采用与顺序表同样的处理：当容量不够时，则将数组容量扩充一倍。容量不够时，则将数组容量扩充一倍。基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈（3）入栈）入栈空元素不能入栈空元素不能入栈栈的容量不够时，数组容量倍增栈的容量不够时，数组容量倍增栈顶元素栈顶元素top加加1，将，将element放入放入top位置，作为新的栈顶元素位置，作为新的栈顶元素 public void push(T x)/元素元素x入栈，空对象不能入栈入栈，空对象不能入栈 if(x=null)return;/空对象不能入栈空对象不能入栈 if(this.top=element.length-1)/若栈满，则扩充栈容量若栈满，则扩充栈容量 Object temp=this.element;this.element=new Objecttemp.length*2;/重新申请一个容量更大的数组重新申请一个容量更大的数组 for(int i=0;itemp.length;i+)/复制数组元素，复制数组元素，O(n)this.elementi=tempi;this.top+;this.elementthis.top=x;基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈（4）出栈栈不空时，取走top位置处栈顶元素，top减1，下一位置数据元素作为新的栈顶元素 public T pop()/出栈，返回栈顶元素，若栈空返回null return this.top=-1?null:(T)this.elementthis.top-;基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈（5）获得栈顶数据元素栈不空时，获取top位置处栈顶元素，此时数据元素未出栈，top值不变 public T get()/取栈顶元素，未出栈，若栈空返回null return this.top=-1?null:(T)this.elementthis.top;基于数组的顺序栈（基于数组的顺序栈（经典实现经典实现）4.1 栈顺序栈顺序栈实现（顺序栈实现（基于已有顺序表基于已有顺序表）/顺序栈类，最终类，实现栈接口，T表示元素类型public final class SeqStack implements Stack private SeqList list;/顺序表 public SeqStack(int capacity)/构造空栈 public SeqStack()/构造空栈 public boolean isEmpty()/判空 public void push(T x)/x入栈 public T peek()/返回栈顶（未出栈）public T pop()/出栈，返回栈顶元素4.1 栈顺序栈/顺序栈类，最终类，实现栈接口，顺序栈类，最终类，实现栈接口，T表示数据元素的数据类型表示数据元素的数据类型public final class SeqStack implements Stack private SeqList list;/使用顺序表（第使用顺序表（第2章）存储栈元素章）存储栈元素 public SeqStack(int length)/构造容量为构造容量为length的空栈的空栈 this.list=new SeqList(length);/执行顺序表构造方法执行顺序表构造方法 public SeqStack()/构造默认容量的空栈构造默认容量的空栈 this(64);顺序栈实现（顺序栈实现（基于已有顺序表基于已有顺序表）4.1 栈顺序栈 public boolean isEmpty()/判断栈是否空，若空返回true return this.list.isEmpty();public void push(T x)/元素x入栈，空对象不能入栈 this.list.insert(x);/顺序表尾插入元素x，自动扩充容量 public T peek()/返回栈顶元素（未出栈），若栈空返回null return this.list.get(list.size()-1);/若栈空，get(i)返回null/return this.isEmpty()?null:this.list.get(list.size()-1);顺序栈实现（顺序栈实现（基于已有顺序表基于已有顺序表）4.1 栈顺序栈public T pop()/出栈，返回栈顶元素；若栈空返回出栈，返回栈顶元素；若栈空返回null return this.list.remove(list.size()-1);/若栈不空，顺序表尾删除，返回删除元素若栈不空，顺序表尾删除，返回删除元素/return this.isEmpty()?null:this.list.remove(list.size()-1);/若栈不空，顺序表尾删除，返回删除元素若栈不空，顺序表尾删除，返回删除元素 public String toString()/返回栈所有元素的描述字符串，形式为返回栈所有元素的描述字符串，形式为“(,)”return this.getClass().getName()+this.list.toString();顺序栈实现（顺序栈实现（基于已有顺序表基于已有顺序表）4.1 栈顺序栈习题解答习题解答4-4 使用顺序表对象作为栈成员变量的操作效率分析使用顺序表对象作为栈成员变量的操作效率分析 4.1 栈顺序栈链式栈定义链式栈定义l栈的链式存储，称为链栈。栈的链式存储，称为链栈。l链式栈的基本运算同顺序栈，定义也同线性表的链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。是对链表的头部操作）。l可用可用单向链表单向链表实现链栈。实现链栈。l它的元素只能在表头进行插入和删除。在链式存它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（储结构中，不需要给出表头结点（head），因），因为其中惟一的已知条件是栈顶指针为其中惟一的已知条件是栈顶指针top，它是指，它是指向链式栈的向链式栈的第一个结点第一个结点（相当于头指针）。（相当于头指针）。4.1 栈链式栈图 栈的链式存储结构链式栈定义链式栈定义4.1 栈链式栈n栈的链式存储结构及操作实现public class LinkedStack implements Stack private Node top;链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈l栈的各种运算比链式存储的普通线性表运算实现时栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各种运算只能在栈的要方便得多，主要原因是栈的各种运算只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除性表的一端操作的情况，并且只能在一端插入删除（栈顶）（栈顶）l而线性表除此之外（不限定一端插入删除），还需而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算查询等操作，理解时，我们可以把栈的入出栈运算当作线性表的一端进行插入删除的特例即可。当作线性表的一端进行插入删除的特例即可。链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈图图 链式栈的入栈和出栈操作链式栈的入栈和出栈操作 链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈l栈的特性是只有一端（栈顶）可以删除和添加。栈的特性是只有一端（栈顶）可以删除和添加。l单链表单链表表头操作表头操作比较方便。比较方便。l入栈操作只需向单链表的头部添加一个结点即入栈操作只需向单链表的头部添加一个结点即可。可。l出栈操作只需将单链表的表头结点删除即可。出栈操作只需将单链表的表头结点删除即可。链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈（1）栈的初始化 public LinkedStack()/构造空栈 this.top=null;链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈（2）判读栈是否为空 public boolean isEmpty()/判断栈是否空，若空返回true return this.top=null;链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈（3）入栈 public void push(T x)/元素x入栈，空对象不能入栈 if(x!=null)this.top=new Node(x,this.top);/头插入，x结点作为新的栈顶结点 链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈（4）出栈 public T pop()/出栈，返回栈顶元素，若栈空返回null if(this.top=null)return null;T temp=this.top.data;/取栈顶结点元素 this.top=this.top.next;/删除栈顶结点 return temp;链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈（5）获得栈顶元素 public T get()/取栈顶元素，未出栈，若栈空返回null return this.top=null?null:this.top.data;链式栈实现（链式栈实现（经典实现经典实现）4.1 栈链式栈/链式栈类，最终类，实现栈接口，T表示元素类型public final class LinkedStack implements Stack private SinglyList list;/单链表单链表 public LinkedStack()/构造空栈 public boolean isEmpty()/判空 public void push(T x)/x入栈 public T peek()/返回栈顶（未出栈）public T pop()/出栈，返回栈顶元素链式栈实现（链式栈实现（基于单链表基于单链表）4.1 栈链式栈/链式栈类，最终类，实现栈接口，T表示数据元素的数据类型public final class LinkedStack implements Stack private SinglyList list;/使用单链表（第单链表（第2章）存储栈元素章）存储栈元素 public LinkedStack()/构造空栈 this.list=new SinglyList();/构造空单链表 public boolean isEmpty()/判断栈是否空，若空返回true return this.list.isEmpty();链式栈实现（链式栈实现（基于单链表基于单链表）4.1 栈链式栈public void push(T x)/元素x入栈，空对象不能入栈 this.list.insert(0,x);/单链表头插入元素x public T peek()/返回栈顶元素（未出栈）；若栈空返回null return this.list.get(0);链式栈实现（链式栈实现（基于单链表基于单链表）4.1 栈链式栈 public T pop()/出栈，返回栈顶元素；若栈空返回null return this.list.remove(0);/若栈不空，单链表头删除，返回删除元素 public String toString()/返回栈所有元素的描述字符串，形式为“(,)”return this.getClass().getName()+this.list.toString();链式栈实现（链式栈实现（基于单链表基于单链表）4.1 栈链式栈习题解答习题解答4-4 使用单链表对象作为栈成员变量的操作效率分析使用单链表对象作为栈成员变量的操作效率分析 4.1 栈链式栈l实现链式栈和顺序栈的操作，都是需要常数时实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为间，即时间复杂度为O（1）。主要两者从空）。主要两者从空间和时间两个方面考虑：间和时间两个方面考虑：l初始时，顺序栈必须说明一个固定的长度，当栈不初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可够满时，造成一些空间的浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间，变则是长度不需要预先设定，相对比较节省空间，但是在每个结点中，设置了一个指针域，从而产生但是在每个结点中，设置了一个指针域，从而产生了结构开销。了结构开销。4.1 栈顺序栈和链式栈的比较l当需要多个栈共享时，顺序存储中可以充分利用顺序当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的空间就每个栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个栈的空间需求有相反会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种方法才有效。也就是说，最好一个栈的需求时，这种方法才有效。也就是说，最好一个栈增长，一个栈缩短。反之，如果两个栈同时增长，则增长，一个栈缩短。反之，如果两个栈同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可能需要大量的数据移动，造成时间的开销增间，则可能需要大量的数据移动，造成时间的开销增大。而链式栈由于存储的不连续性，一般不存在栈满大。而链式栈由于存储的不连续性，一般不存在栈满的问题，所以一般不需要栈的共享的问题，所以一般不需要栈的共享。4.1 栈顺序栈和链式栈的比较（一）程序调用（一）程序调用（二）递归（二）递归（三）括号匹配（三）括号匹配 （四）表达式的求值（四）表达式的求值（五）汉内塔（五）汉内塔（hanoihanoi）问题）问题 （六）数制转换（六）数制转换（七）行编辑程序（七）行编辑程序4.1 栈栈的应用函数（过程）的嵌套调用：在一个函数内调用另一个函数断断点点r r r r主主程程序序srrrs s函函数数1rst t函函数数2rst函函数数3Call 1Call 2Call 34.1 栈栈的应用-程序调用函数嵌套调用1.将所有的实参、返回地址等信息传递给被调用函数保存；2.为被调用函数的局部变量分配存储区；3.将控制转移到被调用函数的入口。-保护断点 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：4.1 栈栈的应用-程序调用1.保存被调函数的计算结果；2.释放被调函数的数据区；3.依照被调函数保存的返回地址将控制转移到调用函数。-恢复断点从被调用函数返回调用函数之前，应该完成下列三项任务：4.1 栈栈的应用-程序调用例例 用栈实现程序设计语言中的子程序调用和返回。用栈实现程序设计语言中的子程序调用和返回。假假设设有有一一个个主主程程序序mainmain和和三三个个子子程程序序A1A1，A2A2和和A3A3，其其调调用用关关系如下图所示。系如下图所示。图图 子程序调用示意图子程序调用示意图void main()void A1()void A2()void A3()A1();A2();A3();r:s:t:4.1 栈栈的应用-程序调用从上图可知，主程序从上图可知，主程序mainmain调用子程序调用子程序A1A1，子程序，子程序A1A1完成之后，返回到主完成之后，返回到主程序的程序的r r处继续执行。但是，因为子程序处继续执行。但是，因为子程序A1A1又调用了子程序又调用了子程序A2A2，所以在，所以在A2A2执行完毕并返回之前，执行完毕并返回之前，A1A1是不可能结束的。类似地，是不可能结束的。类似地，A2A2也必须在也必须在A3A3执行执行完毕并返回之后才能从完毕并返回之后才能从t t处继续进行。其调用与返回的过程如下图所示。处继续进行。其调用与返回的过程如下图所示。显然，调用次序和返回次序是显然，调用次序和返回次序是相反的，最后调用到的子程序相反的，最后调用到的子程序最先返回。为了保证各个被调最先返回。为了保证各个被调用子程序能正确地返回，可以用子程序能正确地返回，可以在程序运行期间设置一个工作在程序运行期间设置一个工作栈来保存返回地址栈来保存返回地址。图 子程序调用与返回main()A1()A2()A3()rst4.1 栈栈的应用-程序调用4.1 栈栈的应用-程序调用使用栈以非递归方式实现递归算法使用栈以非递归方式实现递归算法 4.1 栈栈的应用-递归例例 括号匹配的语法检查括号匹配的语法检查程程序序设设计计语语言言的的表表达达式式中中，只只能能通通过过括括号号改改变变运运算算次次序序，而且括号必须是左右匹配的。而且括号必须是左右匹配的。在在程程序序实实际际运运行行的的过过程程中中，编编译译系系统统是是通通过过栈栈来来判判断断括括号号是否匹配的。是否匹配的。本本例例中中，声声明明了了类类BracketBracket，对对于于给给定定字字符符串串infix,infix,方方法法isMatchedisMatched（）判断其中的括号是否匹配。（）判断其中的括号是否匹配。4.1 栈栈的应用-括号匹配4.1 栈栈的应用-括号匹配isMatchedisMatched（）的算法描述如下：（）的算法描述如下：设设chch是待检测字符串是待检测字符串infixinfix的当前字符：则有的当前字符：则有1.1.若若chch是左括号，则是左括号，则chch入栈；入栈；2.2.若若chch是右括号，则出栈一个值。是右括号，则出栈一个值。若出栈值为左括号，表示括号匹配；若出栈值为左括号，表示括号匹配；若出栈值为空（若出栈值为空（nullnull）或不为左括号，则表示缺少）或不为左括号，则表示缺少左括号，期望左括号。左括号，期望左括号。重复执行上一步。当重复执行上一步。当infixinfix检测结束后：检测结束后：若栈为空，表示括号匹配；若栈为空，表示括号匹配；1.1.否则表示缺少右括号，期望右括号。否则表示缺少右括号，期望右括号。4.1 栈栈的应用-括号匹配public class Bracket /检查infix表达式中的圆括号是否匹配，若匹配，返回空串；/否则返回错误信息 public static String isMatched(String infix)SeqStack stack=new SeqStack(infix.length();/声明接口对象stack，引用实现Stack接口的顺序栈类的实例，/创建空栈/Stack stack=new LinkedStack();4.1 栈栈的应用-括号匹配 for(int i=0;iinfix.length();i+)char ch=infix.charAt(i);switch(ch)case(:stack.push(ch+);/左括号入栈 System.out.println(stack.toString();break;case):if(stack.isEmpty()|!stack.pop().equals()/遇见右括号时，出栈 return 期望(;/检查出栈字符是否为左括号 return(stack.isEmpty()?:期望);/返回空串表示没有错误 4.1 栈栈的应用-括号匹配 public static void main(String args)String infix=(1+2)*3+4)(;System.out.println(infix+，编译错误：+Bracket.isMatched(infix);/*运行结果如下：(1+2)*3+4)(，编译错误：期望(*/4.1 栈栈的应用-括号匹配例例 使用栈计算算术表达式值使用栈计算算术表达式值算算术术表表达达式式有有三三种种表表示示方方法法：，如如A+BA+B，称称为为中中缀缀(infix)(infix)表表示示；，如如+AB+AB称称为为前前缀缀(prefix)(prefix)表表示示；，如，如AB+AB+，称为后缀，称为后缀(postfix)(postfix)表示。表示。在在后后缀缀表表达达式式中中，没没有有括括号号，也也不不存存在在优优先先级级的的差差别别，计计算算过过程程完完全全按按照照运运算算符符出出现现的的先先后后次次序序进进行行，整整个个计计算算过过程程仅仅需需一一遍遍扫扫描描便便可可完完成成，显显然然比比中中缀缀表表达达式式的的计计算算要要简简单单得得多多。因因此此，程程序序设设计计语语言言的的编编译译系系统统要要将将通通常常的的中中缀缀表表达达式式转转换换成后缀表达式成后缀表达式4.1 栈栈的应用-表达式求值例例如如，A*(B+C)的的后后缀缀表表达达式式是是ABC+*,因因+运运算算符符在在前前，*运算符在后，所以应先做加法，后做乘法。运算符在后，所以应先做加法，后做乘法。再再如如，表表达达式式A/B*C+D*(E-A)+C/(D*B)的的后后缀缀形形式式是是AB/C*DEA-*+CDB*/+.怎样设计算法把运算符放在两个运算对象中间的中缀表达式转换为后缀怎样设计算法把运算符放在两个运算对象中间的中缀表达式转换为后缀形式呢？形式呢？观察一下两种形式的表达式，我们注意到操作数在两种形式中出现的次观察一下两种形式的表达式，我们注意到操作数在两种形式中出现的次序是相同的。所以在扫描表达式时，凡遇到操作数就马上输出，剩下的序是相同的。所以在扫描表达式时，凡遇到操作数就马上输出，剩下的事情就是处理所遇到的运算符。事情就是处理所遇到的运算符。解决的办法是把遇到的运算符存放到栈解决的办法是把遇到的运算符存放到栈中，直到某个适当时刻再将运算符退栈并输出。中，直到某个适当时刻再将运算符退栈并输出。4.1 栈栈的应用-表达式求值我们来看两个例子：我们来看两个例子：（1）要要由由表表达达式式A+B*C产产生生出出后后缀缀表表达达式式ABC*+，必必须须按按照照如如表表3.1所所示示的的操操作作顺顺序序执执行行（栈栈向向右右增增长长）。到到达达第第4步步时时必必须须确确定定是是*进进入入栈栈顶顶，还还是是+退退栈栈；由由于于*的的优优先先级级更更高高，应应该该是是*进进栈栈，从从而而产产生生第第5步步；现现在在已已从从表表达达式式中中取取完完所所有有的的符符号号，于于是是我我们们输输出出运运算算符符栈栈中中所所有有剩剩余余的的运运算算符符得到：得到：ABC*+4.1 栈栈的应用-表达式求值（2）表表达达式式A*(B+C)/D 的的后后缀缀形形式式为为ABC+*D/，当当遇遇到到左左括括号号时时必必须须入入栈栈，遇遇到到右右括括号号时时，必必须须依依次次把把栈栈中中元元素素退退栈栈。直直到到相相应应的的左左括括号号为为止止，然然后后去去掉掉左右括号。如表左右括号。如表3.2所示。所示。4.1 栈栈的应用-表达式求值这这些些例例子子启启发发我我们们，算算术术运运算算符符和和括括号号可可用用如如上上表表3.3所所示示分级方案实现。其规则是：分级方案实现。其规则是：只要运算符在栈中的优先级只要运算符在栈中的优先级isp(in-stack prioriisp(in-stack priority)ty)大于或等于新运算符进来时的优先级大于或等于新运算符进来时的优先级icp(in-cicp(in-coming priority)oming priority)，则运算符就从栈中取出。，则运算符就从栈中取出。4.1 栈栈的应用-表达式求值【习题解答】ABCDEF+*G/-H+*+IJ+K*-习题习题4-5 中缀表达式如下，中缀表达式如下，写出后缀表达式。写出后缀表达式。A+B*(C-D*(E+F)/G+H)-(I+J)*K4.1 栈栈的应用-表达式求值中缀表达式：中缀表达式：1+2*(3-4)+54.1 栈栈的应用-表达式求值（1）将中缀表达式转换为后缀表达式）将中缀表达式转换为后缀表达式4.1 栈栈的应用-表达式求值（2）后缀表达式求值）后缀表达式求值 4.1 栈栈的应用-表达式求值public class Expression StringBuffer toPostfix(String infix)/返回将infix中缀表达式转换成的后缀表达式 int toValue(StringBuffer postfix)/计算后缀表达式的值 4.1 栈栈的应用-表达式求值队列的定义队列的定义 l队列队列(Queue)(Queue)也是一种运算受限的特殊线性表。也是一种运算受限的特殊线性表。其插入其插入和删除操作分别在线性表的两端进行（和删除操作分别在线性表的两端进行（只允许在表的只允许在表的一一端端进行插入，而在进行插入，而在另一端另一端进行删除）。允许删除的一端进行删除）。允许删除的一端称为称为队头队头(front)(front)，允许插入的一端称为，允许插入的一端称为队尾队尾(rear)(rear)。l当队列中没有元素时称为当队列中没有元素时称为空队列空队列。在空队列中依次加入。在空队列中依次加入元素元素a a1 1,a,a2 2,a,an n之后，之后，a a1 1是是队头元素队头元素，a an n是是队尾元素队尾元素。显。显然退出队列的次序也只能是然退出队列的次序也只能是a a1 1,a,a2 2,a,an n ，也就是说队列，也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。的修改是依先进先出的原则进行的，例如：排队购物。l先进入队列的成员总是先离开队列。因此队列亦称作先进入队列的成员总是先离开队列。因此队列亦称作先先进先出进先出(First In First Out)(First In First Out)的线性表，简称的线性表，简称FIFOFIFO表表。4.2 队列队列抽象数据类型下图是队列的示意图：4.2 队列队列抽象数据类型队列的数据元素队列的数据元素l队列的数据元素和线性表的数据元素完全相同，即队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是队列的数据元素是n（n=0）个相同类型的数据元）个相同类型的数据元素素a0，a1，。，。an-1组成的有限序列，记为：组成的有限序列，记为：a0,a1,an-1。l其中，其中，n为数据元素的个数，称为队列的长度。为数据元素的个数，称为队列的长度。n=0时，为空队列时，为空队列。l考虑：那么线性表和队列的区别在哪呢考虑：那么线性表和队列的区别在哪呢？4.2 队列队列抽象数据类型队列的操作队列的操作l队列的基本运算通常和栈的基本运算类似，有以下队列的基本运算通常和栈的基本运算类似，有以下6种：种：l 置空队；置空队；/构造一个空队列。构造一个空队列。l 判队空；判队空；/队空返回真，否则返回假。队空返回真，否则返回假。l 判队满；判队满；/队满返回真，否则返回假，仅限于队满返回真，否则返回假，仅限于顺序存储结构顺序存储结构。l 入队；入队；/队列非满时，从队尾插入元素。队列非满时，从队尾插入元素。l 出队；出队；/队列非空时，从队首删除元素。队列非空时，从队首删除元素。l 取队首元素；取队首元素；/返回队首元素，不修改队首指针。返回队首元素，不修改队首指针。4.2 队列队列抽象数据类型队列的操作队列的操作 l队列的操作：队列的操作：l一般情况下，一般情况下，入队入队(enqueue)操作又称为队列的插入。操作又称为队列的插入。l出队出队(dequeue)操作又称为队列的删除。操作又称为队列的删除。4.2 队列队列抽象数据类型 0 1 2 3frontrearfront rear(a)(a)队列初始为空（队列初始为空（b b）a,b,ca,b,c入队入队 front rear front rear（c)a出队出队 (d)b,c出队，队为出队，队为空空 4.2 队列队列抽象数据类型队列的操作队列的操作 队列抽象数据类型队列抽象数据类型/队列接口，描述队列抽象数据类型，队列接口，描述队列抽象数据类型，T表示元素类型表示元素类型public interface Queue public abstract boolean isEmpty();/判空判空 public abstract boolean add(T x);/x入队入队 public abstract T peek();/返回队头，没有删除返回队头，没有删除 public abstract T poll();/出队，返回队头出队，返回队头4.2 队列队列抽象数据类型队列的存储结构队列的存储结构l队列的存储具有顺序和链式存储两种队列的存储具有顺序和链式存储两种4.2 队列队列抽象数据类型习题 能否使用一个线性表对象作为队列，或将队列声明为继承线性表，入栈调用insert(x)函数，出栈调用remove(0)函数？为什么？【习题解答习题解答】都不能。都不能。4.2 队列队列抽象数据类型顺序队列的基本概念：顺序队列的基本概念：l队列的顺序存储结构称为顺序队列。队列的顺序存储结构称为顺序队列。l顺序队列实际上是运算受限的顺序表，和顺序表一顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个数组空间来存放当前队样，顺序队列也必须用一个数组空间来存放当前队列中的元素。列中的元素。l由于队列的队头和队尾的位置是变化的，因而要设由于队列的队头和队尾的位置是变化的，因而要设置两个指针置两个指针front和和和和rear分别指示队头元素和队尾分别指示队头元素和队尾元素在元素在数组空间数组空间中的位置，它们的初值在队列初始中的位置，它们的初值在队列初始化时可以置为化时可以置为0。4.2 队列顺序队列l如果队列的长度（即上限）可以事先预知，对我们分配队列的内存空间有很大帮助。l我们说的队列长度队列长度是指在某一瞬间，队列的长度，不是指通过队列的元素之和。l键盘的敲击产生的消息也是存放在队列中，依次进入系统进行处理。基于数组的队列基于数组的队列4.2 队列顺序队列l数组队列的操作：数组队列的操作：l主要考虑队列的入队和出队算法。其原因是在队列的基本运算主要考虑队列的入队和出队算法。其原因是在队列的基本运算中有六种：判断队空、队列初始化、判断队列满（仅限于顺序中有六种：判断队空、队列初始化、判断队列满（仅限于顺序存储的情况下），入队元素、出队元素、取队首元素等。存储的情况下），入队元素、出队元素、取队首元素等。l而入队时需要操作的步骤是：初始化，然后判断队列是否为满，而入队时需要操作的步骤是：初始化，然后判断队列是否为满，如果不满，则可以插入元素（入队）。如果不满，则可以插入元素（入队）。l出队时，需要考虑的操作步骤是：判断队列是否为空，如果不出队时，需要考虑的操作步骤是：判断队列是否为空，如果不空，删除元素（出队），出队之前，保存队首元素。空，删除元素（出队），出队之前，保存队首元素。l也就是说，队列的入出队运算包含了其他的六种基本运算，取也就是说，队列的入出队运算包含了其他的六种基本运算，取队首元素的运算，只是不用修改队首的指针而已。队首元素的运算，只是不用修改队首的指针而已。基于数组的队列基于数组的队列4.2 队列顺序队列01234567基于数组的队列基于数组的队列4.2 队列顺序队列1234567基于数组的队列基于数组的队列4.2 队列顺序队列234567基于数组的队列基于数组的队列4.2 队列顺序队列34567基于数组的队列基于数组的队列4.2 队列顺序队列345678基于数组的队列基于数组的队列4.2 队列顺序队列l数组队列的操作：数组队列的操作：l入队时将新元素插入入队时将新元素插入rear所指的位置，然后将所指的位置，然后将rear加加1。l出队时，删去出队时，删去front所指的元素，然后将所指的元素，然后将front加加1并返回被删元素。并返回被删元素。l由此可见，当头尾指针相等时队列为空。由此可见，当头尾指针相等时队列为空。l在非空队列里，头指针始终指向队头元素，而尾在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。指针始终指向队尾元素的下一个位置。基于数组的队列基于数组的队列4.2 队列顺序队列n非循环的数组队列的几个条件：非循环的数组队列的几个条件：队空：队空：Q.front=Q.rearQ.front=Q.rear队满：队满：Q.rear=maxsizeQ.rear=maxsize（假溢出假溢出）求队长：求队长：Q.rear-Q.frontQ.rear-Q.front 入队：新元素按入队：新元素按 rearrear 指示位置加入，再将队尾指示位置加入，再将队尾指针加一指针加一 ，即，即 rear=rearrear=rear+1+1 出队：将出队：将frontfront指示的元素取出，再将队头指针指示的元素取出，再将队头指针加一，即加一，即front=frontfront=front+1+1基于数组的队列基于数组的队列4.2 队列顺序队列l数组已经到了最右端，此时，我们无法再往数数组已经到了最右端，此时，我们无法再往数组中加入数据了，但组中加入数据了，但前面显然有空间我们没有前面显然有空间我们没有使用使用。我们称这种情况为。我们称这种情况为假上溢假上溢。8基于数组的队列基于数组的队列4.2 队列顺序队列l数组队列的假溢出：数组队列的假溢出：l队列同栈一样也有上溢和下溢现象。队列同栈一样也有上溢和下溢现象。l此外队列中还存在此外队列中还存在“假溢出假溢出”现象。所谓现象。所谓“假溢出假溢出”是指是指在入队和出队操作中，头尾指针不断增加而不减小或只减在入队和出队操作中，头尾指针不断增加而不减小或只减小而不增加，致使被删除元素的空间无法重新利用，最后小而不增加，致使被删除元素的空间无法重新利用，最后造成队列中有空闲空间，但是不能够插入元素，也不能够造成队列中有空闲空间，但是不能够插入元素，也不能够删除元素的现象。删除元素的现象。l因此，尽管队列中实际的元素个数远远小于向量空间的规因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针已超越向量空间的上界而不能进模，但也可能由于尾指针已超越向量空间的上界而不能进行入队或出队操作。该现象称为行入队或出队操作。该现象称为假上溢假上溢。基于数组的队列基于数组的队列4.2 队列顺序队列l解决假上溢现象的方法有很多种：解决假上溢现象的方法有很多种：1.基于顺序表：基于顺序表：l如固定队首指针，一旦删除元素，需要移动所有元素后，如固定队首指针，一旦删除元素，需要移动所有元素后，修改队尾指针，这样又可以插入元素了，只有在不能插入修改队尾指针，这样又可以插入元素了，只有在不能插入元素时，队列才满，否则可以一直插入元素，这种方法虽元素时，队列才满，否则可以一直插入元素，这种方法虽然能够解决然能够解决“假溢出假溢出”，但需要造成大量的数据元素的移，但需要造成大量的数据元素的移动。动。基于顺序表的队列基于顺序表的队列4.2 队列顺序队列l基于顺序表：l缺点：l使用顺序表，出队效率低。基于顺序表的队列基于顺序表的队列4.2 队列顺序队列l解决假上溢现象的方法有很多种：解决假上溢现象的方法有很多种：2.顺序循环队列：顺序循环队列：l现在解决现在解决“假溢出假溢出”比较好的解决方案是使用循环向比较好的解决方案是使用循环向量，存储在循环向量中的队列称为量，存储在循环向量中的队列称为循环队列循环队列（Circular Quene）。）。l将顺序队列设计成在逻辑上首尾相接的循环结构，则将顺序队列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。可循环使用顺序队列的连续存储单元。顺序循环队列顺序循环队列4.2 队列顺序队列l假设数组的空间是假设数组的空间是m，只要在入