数据结构考研分类复习真题 第三章 答案[4]

四应用题

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

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

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

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

（）可以得到相同的输出元素序列例如输入元素为ABC则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC对于合法序列ABC我们使用本题约定的S×S×S×操作序列对于合法序列BAC我们使用SS××S×操作序列

三个CDEBACDBEACDBAE

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []