● 对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列（栈）的含义是序列的每个元素都入队列（栈）且出队列（栈）一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是（57）。（57）A．出队序列和出栈序列一定相同B．出队序列和出栈序列一定互为逆序C．入队序列与出队序列一定相同，入栈序列与出栈序列不一定相同D．入栈序列与出栈序列一定互为逆序，入队序列与出队序列不一定互为逆序

第1题：

第2题：

第3题：

答案：B

解析：

栈的运算特点为在同一端插入和删除元素，即先入后出，总是栈顶元素先出栈，新元素总是压在栈顶元素之上并成为栈顶元素。初始栈为空，如下图(a)所示。对于元素 1、2、3，依照操作序列push、push、pop、pop、push、pop，可以得到出栈序列213，其过程为：第一个push操作将元素1压入栈中，如下图(b)所示：第二个push操作将元素2压入栈中，如下图(c)所示：第一个pop将栈顶元素2弹出栈，新栈顶元素为1，如下图(d)所示；第二个pop将栈顶元素1弹出栈，导致栈空，如下图(e)所示：其后的push和pop分别将元素3压入和弹出栈，操作结果如下图(f)和(g)所示。

第4题：

第5题：

第6题：

答案：A

解析：

第7题：

答案：B

解析：

栈的特点是先进后出的，如下图所示，且每个元素进栈、出栈各1次，经分析c第一个出栈的话，后面只能跟b，不可能跟a。所以B选项的出栈顺序是不合理的。

第8题：

答案：C

解析：

栈的特点是先进后出的，如下图所示，且每个元素进栈、出栈各1次，经分析d第一个出栈的话，后面只能跟c，不可能跟a。所以C选项的出栈顺序是不合理的。

第9题：

第10题：

假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。

第11题：

设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈的容量至少应该是（）。

第12题：

第13题：

第14题：

第15题：

第16题：

第17题：

第18题：

第19题：

答案：A

解析：

题干要求d第一个出栈，所以入栈的次序为a,b,c,d，栈的特点是先进后出的，如下图所示，且每个元素进栈、出栈各1次，所以出栈序列为d,c,b,a。

第20题：

第21题：

第22题：

栈的特点是（），队列的特点是（），栈和队列都是（）。若进栈序列为1，2，3，4 则（）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1，2，3，4 则（）是一个出队列序列。

第23题：