高等学校数据结构课程系列教材数据结构简明教程(第2版 微课版)/王芳荣

　　第3章栈和队列　　栈和队列是两种特殊的线性表。从数据逻辑结构角度看，栈和队列的元素均呈现一种线性关系； 从运算的角度看，栈和队列是操作受限的线性表。本章介绍栈和队列的概念、存储结构和基本运算的实现算法。　　3.1栈　　3.1.1栈的基本概念　　栈是一种特殊的线性表，其特殊性体现在元素插入和删除运算上，它的插入和删除运算仅限定在表的某一端进行，不能在表中间和另一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作称为进栈(或入栈)，删除操作称为出栈(或退栈)。处于栈顶位置的数据元素称为栈顶元素。不含任何数据元素的栈称为空栈。　　正是这种受限的元素插入和删除运算，使得栈表现出先进后出或者后进先出的特点。举一个例子进行说明，假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有5个人，分别编号为①~⑤，按编号的顺序依次进入此死胡同，如图3.1(a)所示。此时若编号为④的人要退出死胡同，必须等⑤退出后才可以。若①要退出，则必须等到⑤、④、③、②依次都退出后才行，如图3.1(b)所示。这里人进出死胡同的原则是先进去的后出来。　　图3.1死胡同示意图　　在该例中，死胡同就看作是一个栈，栈顶相当于死胡同口，栈底相当于死胡同的另一端，进、出死胡同可看作进栈、出栈操作。插入栈的示意图如图3.2所示。　　栈的基本运算主要包括以下6种。　　（1） 初始化栈InitStack(st)： 建立一个空栈st。　　（2） 销毁栈DestroyStack(st)： 释放栈st占用的内存空间。　　（3） 进栈Push(st，x)： 将元素x插入栈st中，使x成为栈st的栈顶元素。　　（4） 出栈Pop(st，x)： 当栈st不空时，将栈顶元素赋给x，并从栈中删除当前栈顶元素。　　（5） 取栈顶元素GetTop(st，x)： 若栈st不空，取栈顶元素x并返回1； 否则返回0。　　（6） 判断栈空StackEmpty(st)： 判断栈st是否为空栈。　　包含基本运算的栈如图3.3所示，其中，op1~op6表示上述6个基本运算。　　图3.2栈的示意图　　图3.3包含基本运算的栈　　【例3.1】设一个栈的输入序列为a、b、c、d，借助一个栈(假设栈大小足够大)所得到的出栈序列不可能是。　　A. a、b、c、dB. b、d、c、aC. a、c、d、bD. d、a、b、c　　解： a、b、c、d序列经过栈的情况如图3.4所示，根据栈的特点，很容易得出d、a、b、c是不可能的，因为d先出栈，说明a、b、c均已在栈中，按照进栈顺序，从栈顶到栈底的顺序应为c、b、a，出栈的顺序只能是d、c、b、a。所以不可能的出栈序列是D。　　【例3.2】已知一个栈的进栈序列是1，2，3，…，n，其出栈序列是p1，p2，…，pn，若p1=n，则pi的值为。　　A. iB. n-iC. n-i+1D. 不确定　　解： p1=n，则出栈序列是唯一的，即为n，n-1，…，2，1，由此推出pi=n-i+1。本题答案为C。　　【例3.3】元素a、b、c、d、e依次进入初始为空的栈中，假设栈大小足够大。若元素进栈后可停留、可立即出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的出栈序列个数是。　　A. 3B. 4C. 5D. 6　　解： 若元素d**个出栈，a、b、c均在栈中，从栈顶到栈底的顺序应为c、b、a，如图3.5所示，此后合法的栈操作如下。　　(1) e进栈，e出栈，c出栈，b出栈，a出栈，得到的出栈序列decba。　　(2) c出栈，e进栈，e出栈，b出栈，a出栈，得到的出栈序列dceba。　　(3) c出栈，b出栈，e进栈，e出栈，a出栈，得到的出栈序列dcbea。　　(4) c出栈，b出栈，a出栈，e进栈，e出栈，得到的出栈序列dcbae。　　以元素d开头的出栈序列个数为4，本题答案为B。　　图3.4序列经过一个栈的情况　　图3.5元素出栈的情况　　3.1.2栈的顺序存储结构　　栈是一种特殊的线性表，和线性表存储结构类似，栈也有两种存储结构： 顺序存储结构和链式存储结构。　　栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组data和一个记录栈顶元素位置的变量top组成。习惯上将栈底放在数组下标小的那端，栈顶元素由栈顶指针top所指向。顺序栈类型声明如下。　　#define MaxSize 100//顺序栈的初始分配空间大小　　typedef struct　　{ElemType data［MaxSize］;//保存栈中元素，这里假设ElemType为char类型　　int top;//栈顶指针　　} SqStack;　　在上述顺序栈定义中，ElemType为栈元素的数据类型，MaxSize为一个常量，表示data数组中*多可放的元素个数，data元素的下标范围为0~MaxSize-1。当top=-1时表示栈空； 当top=MaxSize-1时表示栈满。　　图3.6说明了顺序栈st的几种状态(假设MaxSize=5)。图3.6(a)表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶指针top=-1。如果做出栈运算，则会“下溢出”。　　……