第3章栈3.1 知识点分析1．栈的基本概念（1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。

允许插入、删除的一端称为栈顶，另一端称为栈底。

（2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。

（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。

（4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。

（5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基本原理解决一些实际应用问题。

2．顺序栈顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针来指示栈顶元素在栈中的位置。

（1）用一维数组实现顺序栈设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#define MAXLEN 10 // 分配最大的栈空间char s[MAXLEN]；// 数据类型为字符型int top；// 定义栈顶指针（2）用结构体数组实现顺序栈顺序栈的结构体描述：#define MAXLEN 10 // 分配最大的栈空间typedef struct // 定义结构体{ datatype data[MAXLEN]；// datatype可根据用需要定义类型int top；// 定义栈顶指针}SeqStack；SeqStack *s；// 定义S为结构体类型的指针变量（3）基本操作的实现要点(a）顺序栈进栈之前必须判栈是否为满，判断的条件：s->top==MAXLEN–1。

(b）顺序栈出栈之前必须判栈是否为空，判断的条件：s->top==–1。

(c）初始化栈（置栈空）：s->top==–1。

(d）进栈操作：if （s->top!=MAXLEN–1）// 如果栈不满{ s->top++；// 指针加1s->data[s->top]=x；// 元素x进栈}(e）出栈操作：if （s->top!=–1）// 如果栈不空{ *x=s->data[s->top]；// 出栈（即栈顶元素存入*x）s->top––；// 指针加1}(f）读栈顶元素if （s->top!=–1）// 如果栈不空return(s->data[s->top])；// 读栈顶元素，但指针未移动3．链栈用链式存储结构实现的栈称为链栈。

（1）链栈的特点：(a）数据元素的存储与不带头结点的单链表相似；(b）用指针top指向单链表的第一个结点；(c）插入和删除在top端进行。

（2）链栈的存储表示：typedef struct stacknode // 栈的存储结构{ datatype data; // 定义数据类型struct stacknode *next; // 定义一个结构体的链指针}stacknode，* Linkstack；Linkstack top；// top为栈顶指针（3）基本操作的实现要点(a) 链栈进栈之前不必判栈是否为满。

(b) 链栈出栈之前必须判栈是否为空，判断的条件：s->top==NULL。

(c) 初始化栈（置栈空）：s->top=NULL。

（4）进栈操作：stacknode *p=new stacknode; // 申请一个新结点p->data=x; // 数据入栈p->next=s->top; // 修改栈顶指针s->top=p;（5）出栈操作：int x; // 定义一个变量x，用以存放出栈的元素stacknode *p=s->top; // 栈顶指针指向px=p->data; // 栈顶元素送xs->top=p->next; // 修改栈顶指针delete p; // 回收结点preturn x; // 返回栈顶元素（6）取栈顶元素if (p!=NULL){x=s->top->data; //输出栈顶元素return x; // 返回栈顶元素}3.2 典型习题分析【例1】若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是P1，P2，P3，…，P n ，若P1=n，则P i=（）。

A．i B．n-i C．n-i+1 D．不确定分析：栈的特点是后进先出，p1输出为n，p2输出为n-1…，p i输出为n-i，所以选C。

【例2】在对栈的操作中，能改变栈的结构的是（）。

A．SEmpty(S) B．SFull(S) C．ReadTop (S) D．InitStack(S)分析：SEmpty(S) 是判栈满函数，SFull(S) 是判栈空函数，ReadTop (S)是读栈顶元素的函数，它们都不改变栈中的数据和结构。

InitStack(S)为初始化栈函数，若栈S中原来有数据存在，则经过初始化以后，就成为一个空栈，也就是说改变了栈的结构。

所以D为正确答案。

【例3】“后进先出”是栈的特点，那么出栈的次序一定是入栈次序的逆序列吗？分析：不一定。

因为当栈后面的元素未进栈时，先入栈的元素可以先出栈。

例如将1、2、3依次入栈，得到出栈的次序可以是：123、132、213、231、321五种。

在1、2、3的六种全排列中，只有312不可能是出栈的序列。

例如213可以这样得到：1入栈；2入栈，并出栈；1出栈；3入栈，并出栈。

312之所以不可能是出栈的序列，原因是：3第一个出栈，表示1、2必然在栈中，且2是栈顶元素，它必须先于1出栈。

所以，312是不可能得到的出栈次序。

【例4】设一个栈的进栈序列是a、b、c、d，进栈的过程中可以出栈，不可能的出栈序列是（）。

A．d，c，b，a B．c，d，b，a C．d，c，a，b D．a，b，c，d分析：栈是仅能在表的一端进行插入和删除操作的线性表，即进栈和出栈运算仅能在栈顶进行，其操作原则是后进先出。

（1）要求出栈序列是d，c，b，a时，要将a，b，c，d都进栈，再依次出栈。

（2）要求出栈序列是c，d，b，a时，需要将a，b，c进栈，c出栈，d出栈，再b出栈，a出栈。

（3）要求出栈序列是d，c，a，b时，需要将a、b、c、d依次进栈，d出栈，c出栈，当前栈顶元素是b，故a不能出栈。

所以C是不可能的出栈序列。

（4）要求出栈序列是a，b，c，d时，可将a、b、c、d逐个进栈后立即出栈。

【例5】铁路列车调度时，常把站台设计成栈式结构，如图3-1所示。

1,2,3,4,5,6图3-1 栈式站台结构（1）设有编号为1，2，3，4，5，6的6辆列车顺序开入栈式结构的站台，则可能的出栈的序列有几种？（2）进栈顺序如上所述，能否得到435612和325641两个出栈序列。

答：（1）可能的出栈的序列有(1/(6+1))*C6=13212（2）不能得到435612的出栈序列。

因为若在4，3，5，6之后再将1，2出栈，则1，2必须一直在栈中，此时1先进栈，2后进栈，2应压在1的上面，不可能1先于2出栈。

出栈序列325641可以得到，其进栈、出栈过程如图3-2所示。

3 5 62 2 4 4 4 41 1 1 1 1 1 1 13 32 32 325 325 3256 32564 325641图3-2 进栈、出栈过程分析【例6】在链栈中为什么不必设头结点？分析：在链栈中，首结点为栈顶元素。

在栈中的插入、删除操作都在栈顶进行，因此每次插入、删除操作都要修改栈顶指针。

如果设置头结点，则头结点后跟的是栈顶元素，每次插入、删除操作就要修改头结点中的指针。

反正要修改一个指针，可见设置头结点是没有必要的。

【例7】指出下述程序段的功能是什么？void Prog1(SeqStack *S){ int i, n=0, a[64]; // 设栈中的元素个数小于64while (! StackEmpty(S))a[n++]=Pop(S);for (i=0; i<=n; i++)Push(S, a[i]);}答：Prog1的功能是将顺序栈S中的元素逆置。

例如，执行Demo1前S=(a 1,a2,……，a n)，则执行Prog1后S=(a n, ……, a2, a1)。

【例8】指出下述程序段的功能是什么？void Prog2(SeqStack *S1, S2){ SeqStack S1, S2,Temp; // 设S1已存在，S2, Temp已初始化DataType x;while (! StackEmpty(&S1)){ x=Pop (&S1);Push(&Temp, x);}while (! StackEmpty(&Temp)){ x=Pop (&Tepm);Push(&S1, x);Push(&S2, x);}}答：Prog2的功能是用Temp作为辅助栈，将S1复制到S2中，并保持S1中的内容不变。

设执行此程序段之前S1=(a1,a2,……，a n)，执行此程序段之后，S1=(a1,a2,……，a n)，S2=(a1,a2,……，a n)。

程序的第一个while语句把S1的内容倒到Temp中，第二个while语句把Temp中的内容分别倒到S1和S2中。

【例9】指出下述程序段的功能是什么？void Prog3 (SeqStack *S, char x){ SeqStack T;char i;InitStack (&T);while (! StackEmpty(S))if ((i=Pop(S)) != ’k’ )Push(&T, i);while (! StackEmpty(&T)){ i=Pop (&T);Push(S, i);}}答：Prog3的功能是把栈S中值为“k”的结点删除。

【例10】写出运行下列程序段的输出结果void main(){ Stack S;char x,y;InitStack(S); // 初始化栈x= "c ";y= "k ";Push(S,x);Push(S, "a ");Push(S,y);Pop(S,x);Push(S, "t ");Push(S,x);Pop(S,x);Push(S, "s ");While (!SEmpty(S)){ Pop(S,y);cout<<y; };cout<<x;}分析：本题主要是分清变量的内容进栈，还是字符直接进栈。

按照程序，其进栈、出栈的主要步骤，以及变量x和y值的变化过程如图3-3所示。

在While循环语句中，栈顶数据依次弹出到y，并输出。