本章主要介绍了两种运算受限的线性表：栈和队列。讨论了它们的基本概念、存储结构、基本运算的实现以及一些应用实例。
对于栈来说，它的插入和删除运算均在表的同一端进行，是一种“先进后出”的线性表，随着节点的进栈和出栈，用栈顶指针指示栈顶的变化。用顺序存储结构时，要注意栈满、栈空的条件；用链式存储结构时，要注意链的方向。
对于队列来说，它的插入运算在表的一端进行，而删除运算在表的另一端进行，是一种“先进先出”的线性表，分别用队头指针和队尾指针指示队列头节点和尾节点的变化。熟记队列中节点的插入、删除运算的算法及其溢出的条件。在顺序队列结构中，当节点不断插入、删除时，会很快移到队列末端而造成假溢出，用循环队列是一个好的解决方法。
1．选择题
（1）设有顺序栈S，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是 。
A．2 B．3 C．5 D．6
（2）若有一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为 。
A．4 B．5 C．6 D．7
（3）和顺序栈相比，链栈有一个比较明显的优势是 。
A．通常不会出现栈满的情况
B．通常不会出现栈空的情况
C．插入操作更容易实现
D．删除操作更容易实现
（4）若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是 。
A．不确定 B．n-i C．n-i+1 D．n-i-1
（5）以下说法正确的是 。
A．因链接本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
B．因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
C．对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢”
D．对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”
（6）顺序队列的入队操作为 。
A．sq.rear=sq.rear+1;sq.data[sq.rear]=x;
B．sq.rear=(sq.rear)=x;sq．rear=sq.rear+1;
C．sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x;
D．sq.data=[sqrear]=x; sq.rear=(sq.rear+1)%maxsize;
（7）循环队列的入队操作为 。
A．sq.rear=sq.rear+1;sq.data[sq.rear]=x;
B．sq.data[sq.rear]=x; sq.rear=sq.rear+1;
C．sq.rear=(sq.rear+1)%maxsize;sq.data[sq．rear]=x;
D．sq.data[sq.rear]=x;sq.rear=(sq.rear+1)%maxsize;
（8）顺序队列的出队操作为 。
A．sq.front=(sq.front+1)%maxsize;
B．sq.front=sq.front+1;
C．sq.rear=(sq.rear+1)%maxsize;
D．sq.rear=sq.rear+1;
（9）循环队列的出队操作为 。
A．sq.front=(sq.front+1)%maxsize;
B．sq.front=sq.front+1;
C．sq.rear=(sq.rear+1)%maxsize;
D．sq.rear=sq.rear+1;
（10）循环队列的队满条件为 。
A．(sq.rear+1)maxsize= =(sq.front+1)%maxsize;
B．(sq.rear+1)maxsize= =sq.front+1;
C．(sq.rear+1)maxsize= =sq.front;
D．sq.rear= =sq.front;
（11）循环队列的队空条件为 。
A．(sq.rear+1)maxsize= =(sq.front+1)%maxsize;
B．(sq.rear+1)maxsize= =sq.front+1;
C．(sq.rear+1)maxsize= =sq.front;
D．sq.rear= =sq.front;
（12）如果以链表作为栈的存储结构，则出栈操作时 。
A．必须判别栈是否满
B．判别栈元素的类型
C．必须判别栈是否空
D．对栈不做任何判别
（13）向一个栈顶指针为Top的链栈中插入一个s所指节点时，其操作步骤为 。
A．Top->next=s;
B．s->next=Top->next;Top->next=s;
C．s->next=Top;Top=s;
D．s->next=Top;Top=top->next;
（14）从栈顶指针为Top的链栈中删除一个节点，并将被删节点的值保存到x中，其操作步骤为 。
A．x=Top->data;Top=Top->next;
B．Top=Top->next;x=Top->data;
C．x=Top;Top=Top->next;
D．x=Top->data;
（15）在一个链队中，若f、r分别为队头、队尾指针，则插入s所指节点的操作为 。
A．f->next=s;f=s; B．r->next=s;r=s;
C．s->next=r;r=s; D．s->next=f;f=s;
（16）一个栈的入栈序列是a，b，c，d，e，则栈不可能的输出序列是 。
A．e，d，c，b，a B．d，e，c，b，a
C．d，c，e，a，b D．a，b，c，d，e
（17）一个队列的入队序列是1，2，3，4，则队列可能的输出序列是 。
A．4，3，2，1 B．1，2，3，4
C．1，4，3，2 D．3，2，4，1
（18）设计一个判别表达式中左、右括号是否配对出现的算法，采用 数据结构最佳。
A．线性表的顺序存储结构 B．栈
C．队列 D．线性表的链式存储结构
（19）若以1，2，3，4作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是 。
A．1，2，3，4 B．4，1，3，2
C．4，2，3，1 D．4，2，1，3
2．填空题
（1）向栈中压入元素的操作是 。
（2）对栈进行退栈时的操作是 。
（3）在一个循环队列中，队首指针指向队首元素的 。
（4）从循环队列中删除一个元素时，其操作是 。
（5）在具有n个单元的循环队列中，队满时共有 个元素。
（6）假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为 。
（7）栈的特点是 ，队列的特点是 。
（8）栈结构通常采用的两种存储结构是 和 。
3．问答题
（1）栈与队列可以利用C语言的哪一种数据结构来表示？请举出一些其性质类似于栈和队列的例子。
（2）叙述栈和队列之间的区别和联系。
（3）设有4个元素a，b，c，d进栈，给出它们所有可能的出栈次序。
（4）与一般队列相比，环形队列有什么优点？并给出环形队列队满和队空的判断条件。
（5）若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是多少？
4．上机操作题
（1）已知num为无符号十进制整数，请写一个非递归算法，依次输出num所对应的r进制数的各位数字。
（2）在一个顺序循环队列中，用count存放队列长度，要求充分利用循环队列中所有的存储空间，请设计循环队列的入队、出队算法。
（3）设用带表头节点的循环链表表示队列，且仅设一个尾指针，尾指针指向数据域值为队尾元素的节点，不设队首指针，请编写实现置空队列、入队和出队的算法。
（4）已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。