栈

类似于一个盒子

特性

先进后出：要想取a1,则必须先取出a2

队列

类似于小朋友排队

特性

先进先出：先排队的小朋友先打到饭

栈、队列和线性表的关系

栈和队列是受限的线性表，具体表现为栈只能在头节点后进行插入和删除，队列是在头结点删除,尾节点插入。

课后习题

【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

参考答案：B

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

参考答案：C

【2015年真题】已知程序如下：

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

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（）。
A．main()→S(1)→S(0)            B．S(0)→S(1)→main()
C．main()→S(0)→S(1)            D．S(1)→S(0)→main() 

参考答案：A

【2013年真题】一个栈的入栈序列为1,2,3,...,n，其出栈序列是p1,p2,p3,...,pn。若p2 = 3，则p3可能取值的个数是（）
 A. n - 3             B. n - 2             C. n - 1             D. 无法确定

参考答案：C
答案解析：除了 3 本身以外，其他的值均可以取到，因此可能取值的个数为n - 1。 

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

参考答案：B
答案解析：出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。 

【2010年真题】若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则 不可能得到的出栈序列是（）。 
A．d c e b f a         B．c b d a e f         C．b c a e f d         D．a f e d c b

参考答案：D
答案解析：考查限定条件的出栈序列。 
A 可由 in,in,in,in,out,out,in,out,out,in,out,out 得到； 
B 可由 in,in,in,out,out,in,out,out,in,out,in,out 得到； 
C 可由 in,in,out,in,out,out,in,in,out,in,out,out 得到； 
D 可由 in,out,in,in,in,in,in,out,out,out,out,out 得到，
但题意要求不允许连续三次退栈操作，故 D 错。