栈详解
队列详解

单项选择题

1. 【2010统考真题】若元素a,b,c,d,e,f,依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作,不可能得到的出栈序列是（)。
   A. dcebfa B.cbdaef C. bcaefd D.afedcb

2. 【2018统考真题】若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作:
   1）从S1中依次弹出两个操作数a和b。
   2）从S2中弹出一个运算符op。
   3）执行相应的运算b op a.
   4）将运算结果压入S1中。
   假定S1中的操作数依次是5,8,3,2(2在栈顶)，S2中的运算符依次是*、-、+(+在栈顶)。调用3次F()后,S1栈顶保存的值是（).
   A.-15 B. 15 C.-20 D. 20

3. 【2009统考真题】设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S，若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是().
   A. 1 B. 2 C. 3 D. 4

4. 【2013统考真题】一个栈的入栈序列为1,2,3,.…, n，出栈序列是P1,P2,P3.…,Pn。若P=3，则P3可能取值的个数是（).
   A. n-3 B. n-2 C. n-1 D.无法确定

5. 【2011统考真题】元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（).
   A. 3 B. 4 C. 5 D. 6

6. 采用共享栈的好处是（).
   A.减少存取时间,降低发生上溢的可能
   **B.**节省存储空间,降低发生上溢的可能
   C.减少存取时间,降低发生下溢的可能
   D.节省存储空间,降低发生下溢的可能

7. 【2017统考真题】下列关于栈的叙述中,错误的是().
   Ⅰ采用非递归方式重写递归程序时必须使用栈
   Ⅱ.函数调用时,系统要用栈保存必要的信息
   Ⅲ.只要确定了入栈次序，即可确定出栈次序
   Ⅳ．栈是一种受限的线性表，允许在其两端进行操作
   A. Ⅰ B. Ⅰ、Ⅱ、Ⅲ C. Ⅰ、Ⅲ、Ⅳ D. Ⅱ、Ⅲ、Ⅳ

8. 【2020统考真题】对空栈S进行Push和 Pop操作，入栈序列为a, b, c,d,e，经过Push、Push、Pop、Push、Pop、Push、Push、Pop操作后得到的出栈序列是（ ).
   A. b, a, c B. b,a,e C. b, c, a D. b, c, e

9. 若用数组A[0…5]来实现循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素，再加入两个元素后，rear和 front的值分别为（).
   A. 3和4 B. 3和0 C. 5和0 D. 5和1

10. 【2014统考具题】循环队列放在一年数组A[0…m-1 ] 中,end1 指向队头元素,end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（).
    A.队空:end1== end2; 队满:end1==(end2+1) mod M
    B.队空:end1== end2; 队满:end2==(end1+1)mod(M-1)
    C.队空:end2==(end1+1)mod M; 队满:end1==(end2+1) mod M
    D.队空:end1==(end2+1)mod M; 队满:end2==(end1+1) mod(M-1)

11. 最适合用作链队的链表是（)。
    A.带队首指针和队尾指针的循环单链表必 B.带队首指针和队尾指针的非循环单链表
    C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表

12. 假设循环单链表表示的队列长度为n,队头固定在链表尾，若只设头指针，则进队操作的时间复杂度为（).
    A. O(n) B. O(1) C. O(n^2) D. O(nlogn)

13. 【2018统考真题】现有队列Q与栈S,初始时Q中元素依次是1,2,3,4,5,6;1在队头,S为空。若仅允许下列3种操作:①出队开输出出队元系，②出队并将元素入栈，③出栈并输出出栈元素，则不能得到的输出序列是().
    A. 1,2,5,6,4,3 B. 2,3,4,5,6,1 C. 3,4,5,6,1,2 D. 6,5,4,3,2,1

14. 【2016统考真题】设有如下图所示的火车车轨,入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~9的9列列车，驶入的次序依次是8,4,2,5,3,9,1,6,7.若期望驶出的次序依次为1-9，则n至少是().
    A. 2 B. 3 C. 4 D. 5

15. 对于一个问题的递归算法求解和其相对应的非递归算法求解，().
    A.递归算法通常效率高一些 B.非递归算法通常效率高一些
    C.两者相同 D.无法比较

16. 11.【2012统考真题】已知操作符包括+、-、×、/、( 和 ) 。将中缀表达式a+b-a× ((c+d)/e-f)+g 转换为等价的后缀表达式ab+acd+e/f-×-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（).
    A. 5 B. 7 C. 8 D. 11

17. 【2014统考真题】假设栈初始为空，将中缀表达式a/b+ (c×d-e×f)/g转换为等价的后
    缀表达式的过程中,当扫描到f时,栈中的元素依次是（ ).
    A.+(×- B+(-× C./＋(×一× D./+一×

18. 【2015统考真题】已知程序如下:

    int S(int n){ return (n<=0)?0:s(n-1) +n;}
    void main(){ cout<<S(1);}
    

    程序运行时使用栈来保存调用过程的信息，p栈底到栈顶保存的信息依次对应的是()

    A. main()-S(1)-S(0) B. S(0)-S(1)-main()
    C. main()-S(0)-S(1) D. S(1)-S(0)-main()

19. 有一个n×n的对称矩阵A,将其下三角部分按行存放在一维数组B中，而A[0] [0]存放于B[0]中,则第i+1行的对角元素A[i] [i]存放于B中的()处。
    A. (i+3)/2 B、(i+1)i/2 C (2n-i+1)i/2 D.(2n -i-1)i/2

20. 在一个二维数组A中，假设每个数组元素的长度为3个存储单元，行下标i为0_{8，列下标j为0}9，从首地址SA开始连续存放。在这种情况下，元素A[8] [5]的起始地址为().
    A. SA+141 B. SA+144 C. SA+222 D. SA+255

21. 【2016统考真题】有一个100阶的三对角矩阵M,其元素mi,j ( 1≤i,j≤100）按行优先依次压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是().
    A. 86 B. 87 C. 88 D. 89

22. 【2017统考真题】适用于压缩存储稀疏矩阵的两种存储结构是（).
    A.三元组表和十字链表 B.三元组表和邻接矩阵
    C.十字链表和二叉链表 D.邻接矩阵和十字链表

23. 【2018统考真题】设有一个12×12的对称矩阵M，将其上三角部分的元素mi,f(1≤i≤j≤12）按行优先存入C语言的一维数组N中,元素ms,6在N中的下标是（)。
    A. 50 B. 51 C. 55 D. 66

24. 【2020统考真题】将兰个10×10对称矩阵M的上三角部分的元素m;, （1≤i≤j≤10)按列优先存入C语言的一维数组N中，元素m,2在N中的下标是（).
    A. 15 B. 16 C. 22 D. 23

综合应用题

第一题

题面：设有两个栈s1、s2都采用顺序栈方式，并共享一个存储区[0… maxsize-1]，为了尽量利用空间，减少溢出的可能，可栈顶相向、迎面增长的存储方式。试设计s1、s2有关入栈和出栈的操作算法。
思路：利用共享栈
算法实现：

#include<bits/stdc++.h>
using namespace std;typedef int ElemType; 		//栈元素数据类型#define MaxSize 100  		//栈中元素最大个数
typedef struct{ElemType data[MaxSize]; //存放栈中元素int top[2];            	//栈顶指针
}stk;
stk s;                      //全局变量bool push(int i,ElemType x); //入栈
ElemType pop(int i);        //出栈int main(){}bool push(int i,ElemType x){//入栈算法。i为栈号，i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素//入栈成功返回1，否则返回0if(i<0||i>1) {printf("栈号输入错误！！！\n");return false;}if(s.top[1]-s.top[0]==1){printf("栈已满！！！\n");return false;}switch(i){case 0: s.data[++s.top[0]]=x;return true;break;case 1: s.data[--s.top[1]]=x;return true;}
}ElemType pop(int i){//退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈//退栈成功返回退栈元素，否则返回-1if(i<0||i>1){printf("栈号输入错误\n");return -1;}switch(i){case 0:if(s.top[0]==-1){printf("栈空\n");return -1;}elsereturn s.data[s.top[0]--];case 1:if(s.top[1]==MaxSize){printf("栈空\n");return -1;}elsereturn s.data[s.top[1]++];}
}

第二题

利用两个栈S1,S2来模拟一个队列,已知栈的4个运算定义如下:

Push(S,x);				//元素×入栈S
Pop (S,x);				//S出栈并将出栈的值赋给×
StackEmpty(S);	  //判断栈是否为空
Stackoverflow(S);  //判断栈是否满

如何利用栈的运算来实现该队列的3个运算（形参由读者根据要求自己设计)?

Enqueue;	//将元素x入队
Dequeue;	//出队,并将出队元素存储在x中
QueueEmpty;	//判断队列是否为空

算法思想：队列需要元素先进先出而栈则是先进后出，但用第二个栈对第一个栈逆置则可实现先进先出，来模拟队列。算法实现入队时只需要压入S1栈（未满）出对时只需要弹出S2栈顶（非空）

算法实现：

bool Enqueue(Stack &S1,Stack &S2,Elemtype e){if(!Stackoverflow(S1)){	//S1栈未满Push(S1,e);			//压入S1栈return true;}if(Stackoverflow(S1)&&!StackEmpty(S2)){//S1栈已满，且S2非空printf("队列已满\n");return false;}if(Stackoverflow(S1)&&StackEmpty(S2)){//S1栈已满，且S2为空while(!StackEmpty(S1)){	//将S1中元素转移到S2中Pop(S1,x);Push(S2,x);}}Push(S1,e);			//压入S1栈return true;
}void Dequeue(Stack &S1,Stack &S2,Elemtype x){if(!StackEmpty(S2)){//S2非空Pop(S2,x);}else if(StackEmpty(S1)){	//S1、S2都为空printf("队列为空");}else{	//S1非空S2为空while(!StackEmpty(S1)){	//将S1中元素转移到S2中Pop(S1,x);Push(S2,x);}Pop(S2,x);}
}bool QueueEmpty(Stack S1,Stack S2){return (StackEmpty(S1) && StackEmpty(S2));
}

第三题【2019统考真题】

请设计一个队列，要求满足;①初始时队列为空;②入队时，允许增加队列占用空间;③出队后，出队元素所占用的空间可重夏便用，即整个队列所占用的空间只增不减;④入队操作和出队操作的时间复杂度始终保持为O(1)。请回答下列问题:
1）该队列是应选择链式存储结构,还是应选择顺序存储结构?
2）画出队列的初始状态，并给出判断队空和队满的条件。
3）画出第一个元素入队后的队列状态。
4）给出入队操作和出队操作的基本过程。

参考王道书中的详细解答

笔记

1. 栈和队列在统考中主要一选择题的形式出现
2. 栈的概念和实现比较简单，考点主要在于出栈顺序和栈的应用（括号匹配、表达式求值、共享栈），理解算法思想
3. 队列头尾都有不同的操作所以比栈复杂一点，要注意题目给出的front和rear分别指向哪一个元素，以及判空和判满的方法，选择题一般和栈一起出现或者考查各种双端队列的出入队顺序，关于队列的应用将在后续章节详解
4. 矩阵压缩存储一定要注意题目给出的起始地址，一半默认从0位置开始。题目变化较多，背公式作用不大，主要是观察每行每列的存储规律，可以自己用一个3×3或4×4的矩阵测试