第三章栈和队列(修订版本2010.6)

1第三章栈和队列[内容提要]栈和队列的概念；栈和队列的存储结构及它们的应用。栈和队列与线性表有着密切的联系。一方面，栈和队列的逻辑结构也是线性结构；另一方面，栈和队列的基本操作是线性表操作的子集。因此，可将栈和队列看成是两种特殊的线性表。3.1栈3.1.1栈的基本概念在日常生活中有不少类似于栈（如图3.1（a）所示）的例子。假设有一个很窄的死胡同，其宽度只能容纳一辆车，现有五辆车，分别编号为①～⑤，按编号顺序依次进入此胡同，若要退出④，必须先退出⑤；若要退出①必须将⑤④③②依次都退出才行。这个死胡同就是一个栈，如图⒊１(b)所示。图3.1(a)(b)由上面的例子我们可以知道：栈(Stack)是限制仅在表的一端进行插入和删除操作的线性表。允许进行插入和删除的一端称为栈顶(top)，不允许插入和删除的一端称为栈底(bottom)。不含元素的空表称为空栈。假设栈S＝(a0,a1,...,an-1)，如图⒊１(a)所示，a0为栈底元素，an-1为栈顶元素。栈中元素按a0,a1,...,an-1的次序进栈，退栈的第一个元素应为栈顶元素。也就是说，栈的特点是后进先出(LastInFirstOut)，因此，栈又称为后进先出的线性表，简称LIFO线性表。栈的基本操作如下：InitStack(S)：初始化操作。设置一个空栈S。StackEmpty(S)：判栈空操作。若S为空栈，函数值为1，否则为0。Size(S)：求栈深操作。函数值为栈中当前的元素个数。12345进出a1a2a3an栈顶栈底进栈出栈2Top(S)：读栈顶元素操作。若栈S不空，函数值为栈顶元素，否则为空元素NULL。Push(S,x)：进栈操作。将元素x插入栈S中，使x成为栈S的栈顶元素。Pop(S)：出栈操作。若栈S不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULL。Clear(S)：栈置空操作。不论栈S是否为空栈，将S置为空栈。下面我们看一个简单的栈的应用的例子。我们在学习计算机文化基础课时已经学习了用除法把十进制数转换成二进制数的方法。用初始十进制数除以2，把余数记录下来，若商不为0，则再用商去除以2，直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数。如把十进制数35转换成二进制数的过程如下。由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈，这样就可以得到正确的二进制数。上述算法可描述如下：voidconversion(){StackS;intn;InitStack(&S);printf(Inputanumbertoconvert:\n);scanf(%d,&n);if(n0){printf(\nThenumbermustbeover0.);return0;}if(n==0)Push(&S,0);while(n!=0){Push(&S,n%2);n=n/2;}printf(theresultis:);while(!StackEmpty(&S)){printf(%d,Pop(&S));}}35178421011001余数结果：1001133.1.2栈的顺序存储结构由栈的定义以及栈的实例，我们很容易想到用一个数组或类似的结构去存储它。栈的顺序存储结构，简称顺序栈(sequentialstack)。它是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，通常用一维数组存放栈的元素。同时设“指针”top指示栈顶元素的当前位置。（注意，top并不是指针型变量，只是整型变量，它指示栈顶元素在数组中的位置）。空栈的top值为零。在C语言中，顺序栈的类型说明如下：#definemaxsize栈可能的最大数据元素的数目//栈的最大容量typedefstruct{elemtypeelem[maxsize];inttop;}sqstacktp;设s为sqstacktp型变量，即s表示一个顺序栈。图⒊２说明了这个顺序栈的几种状态。(a)表示顺序栈为空，s.top=0；(b)表示栈中只含一个元素A，s.top=1，在(a)的基础上用进栈操作Push(s,A)可以得到这种状态；(c)表示在(b)的基础上将元素B、C依次进栈后的状态，s.top=3；(d)表示在(c)状态下将元素C退栈后的情况，s.top=2，由执行一次Pop(s)得到；(e)表示栈中有五个元素，s.top=maxsize，这种状态称为栈满，此时若有元素进栈则将产生“数组越界”的错误，称为栈溢出。（a）(b)(c)(d)(e)图⒊２顺序栈的几种状态因此，s.top=0表示空栈，出栈和读栈顶元之前应判断栈是否为空。s.top=maxsize表示栈满，进栈之前应判断是否栈满。下面讨论在顺序栈上实现的操作。（1）初始化（栈置空）操作算法⒊１：voidInitStack(sqstacktp*s){//将顺序栈s置为空s-top=0;}如下函数生成了一个顺序栈，并完成了对该顺序栈的初始化。voidmain(){topCBAtopBAtopFEDBAtopAtop4voidInitStack(sqstacktp*s);sqstacktp*s;s=(sqstacktp*)malloc(sizeof(sqstacktp));InitStack(s);}（2）判栈空操作算法⒊２：intStackEmpty(sqstacktp*s){if(s-top0)return0;elsereturn1;}（3）进栈操作算法⒊３：voidPush(sqstacktp*s,elemtypex){//若栈s未满，将元素x压入栈中；否则，栈的状态不变并给出出错信息if(s-top==maxsize)printf(Overflow);elses-elem[s-top++]=x;//x进栈}（4）出栈操作算法⒊４：elemtypePop(sqstacktp*s){//若栈s不空，则删去栈顶元素并返回元素值，否则返回空元素NULLif(s-top==0)returnNULL;else{s-top--;//栈顶指针减1returns-elem[s-top];//返回原栈顶元素值}}（5）求栈深操作算法⒊５:intSize(sqstacktp*s){return(s-top);5}（6）读取栈顶元素操作算法⒊６：elemtypeTop(sqstacktp*s){if(s-top==0)returnNULL;elsereturn(s-elem[s-top-1]);}顺序栈使用起来比较简单，但是必须预先给它分配一个存储空间。为了使栈不溢出，我们通常必须为它分配一个较大的空间，然而在大多数时候都会造成存储空间的浪费。但是在当程序中同时使用两个栈时，有一种方法可以提高存储空间的使用效率：可以将两个栈的栈底设在一维数组空间的两端，让两个栈各自向中间延伸，仅当两个栈的栈顶相遇时才可能发生上溢，如图⒊３所示。这样当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。所以，当两个栈共享一个长度为maxsize的数组空间时，每个栈实际可利用的最大空间大于maxsize/2。图⒊３两个栈共亨空间示意图上述结构的类型描述如下：#definemaxsize栈可能的最大数据元素的数目//栈的最大容量typedefstruct{elemtypeelem[MAXSIZE];inttop[2];}dustacktp若ds为dustacktp型变量，显然，栈1的顶由ds.top[0]指示，ds.top[0]=0表示栈1为空。栈2的顶由ds.top[1]指示，ds.top[1]=maxsize+1表示栈2为空。ds.top[0]+1=ds.top[1]表示栈满。3.1.3栈的链式存储结构由栈的顺序存储结构可知，顺序栈的最大缺点是：为了保证不溢出，必须事先给栈分配一个较大的空间，这显然浪费了存储空间，而且在很多时候我们并不能保证所分配的空间就一定够用，这大大降低了顺序栈的可用性，这时我们就要采用链式存储结构。栈的链式存储结构，简称链栈(linkedstack)，它的组织形式与单链表类似，链表的尾部结点是栈底，链表的头部结点是栈顶。由于只在链表的头部进行操作，故链栈没有必要设置头结点。如图⒊４所示，其中，单链表的头指针head作为栈顶指针。链栈由栈顶指针head唯一确定，栈底结点的next域为NULL。abcaABtop1top26图⒊４链栈示意图链栈的类型定义如下：typedefstructstacknode{elemtypedata;structstacknode*next;}stacknode;typedefstruct{stacknode*top;//栈顶指针}LinkStack;下面给出初始化、进栈和出栈操作在链栈上的实现。(1)初始化操作算法⒊７：voidInitStack(LinkStack*ls){//建立一个空栈lsls-top=NULL;}下面函数完成了对一个链栈的创建和初始化操作。voidmain(){LinkStack*ls;ls=(LinkStack*)malloc(sizeof(LinkStack));InitStack(ls);}(2)进栈操作算法⒊８：voidPush(LinkStack*ls,elemtypex){stacknode*s=NULL;s=(stacknode*)malloc(sizeof(stacknode));//生成新结点s-data=x;s-next=ls-top;//链入新结点FheaddatanextEDANULL栈顶栈底7ls-top=s;//修改栈顶指针}（3）出栈操作算法⒊９：elemtypePop(LinkStack*ls){//若栈ls不空，删去栈顶元素并返回元素值，否则返回空元素NULLstacknode*p=NULL;elemtypex;if(ls-top==NULL)returnNULL;else{x=(ls-top)-data;p=ls-top;ls-top=p-next;free(p);returnx;//返回原栈顶元素值}}链栈一般不会产生栈满，只有当整个可用空间都被占满，malloc()函数过程无法实现时才会发生上溢。另外，链栈占用的空间是动态分配的，所以多个链栈可以共享存储区域。3.2栈的应用实例栈在计算机科学领域具有广泛的应用，只要问题满足后进先出原则，均可使用栈作为其数据结构。例如：在编译和运行计算机语言程序的过程中，就需要利用栈进行语法检查（如检查PASCAL语言中begin和end、（和）、[和]是否配对等）、计算机表达式的值、实现递归过程和函数的调用等。⒊⒉１表达式求值要把一个表达式翻译成能正确求值的机器指令，或者直接对表达式求值，首先要能正确解释表达式。例如，要对下面的算术表达式求值1+2*4-9/3必须遵循先乘除后加减、先左后右及先括号内后括号外的四则运算法则，其计算顺序应为1+2*4-9/3└—┘└─┘①③└─┘②└───┘④8那么，如何让机器也按照这样的规则求值呢？通常采用“运算符优先数法”。一般表达式中会遇到操作数、运算符和表达式结束符（为了简化问题，这里仅讨论只含加、减、乘、除四种运算，并且不含括号的情况）。对每种运算符赋予一个优先数，如运算符：*/+-#优先数：22110其中#是表达式结束符。对表达式求值时，一般设立两个栈，一个称为运算符栈(OPTR)。另一个称为操作数栈(OPND)，以便分别存放表达式中的运算符和操作数。具体处理方法是：从左至右扫描表达式，⑴凡遇操作数，一律进OPND栈；⑵若遇运算符，则比较它与OPTR栈的栈顶元素的优先数。若它的优先数大，则将该运算符进栈；反之，则弹出OPTR栈顶的运算符θ，并从OPND栈连续弹出两个栈顶元素y和x，进行运算xθy，并将运算结果压进OPND栈。为了使算法简捷，在表达式的最左边也虚设一个“#”。一旦左边的“#”与