栈、队列应用题

1、名词解释：栈。

        答：栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。

2、名词解释：队列。

        答：队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先删除，故队列也常常称先进先出（FIFO）表。

3、什么是循环队列？

        答：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种办法。通常把一位数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“做标记”的办法解决“队满”和“队空”的判定问题。

4、假设以s和x分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由s和x组成的序列表示（如SXSX）。

        ①试指出判别给定序列是否合法的一般规则。

        答：通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于x的个数。

        ②两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举例说明。

        此题对“同一输入序列”有两种理解，因此有两种答案。

        理解一：输入序列的元素相同，但元素之间的顺序可以不同

        答一：可以得到相同的输出元素序列。例如，输入元素为A,B,C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于BAC，我们使用SSXXSX操作序列。

        理解二：输入序列的元素相同且元素之间的顺序也相同

答案二：如下图所示