简答题

1. 栈是_______的线性表，其运算遵循_______的原则
   操作受限（或限定仅在表尾进行插入和删除操作）后进先出
2. 在作进栈运算时应先判别栈是否____;在作退栈运算时应先判别栈是否____；当栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大容量为____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出
   满 空 n 栈底 两栈顶指针相邻（即值之差的绝对值为1）
3. 用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S和 X 的操作串为_______
   S×SS×S××
4. 顺序栈用 data[1..n]存储数据，栈顶指针是 top,则值为 x 的元素入栈的操作是_______
   data[++top]=x
5. 循环队列的引入，目的是为了克服_______
   假溢出时大量移动数据元素
6. ________又称作先进先出表
   队列
7. 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是_______
   s(LinkedList)malloc(sizeof(LNode))；s->data=x;s->next=r->next；r->next=s；r=s；
8. 区分循环队列的满与空，只有两种方法，它们是______和______
   牺牲一个存储单元设标记
9. 设循环队列用数组 A[1..M]表示，队首、队尾指针分别是 FRONT 和 TAIL，判定队满的条件为_______
   (TAIL+1)MOD M=FRONT
10. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件
    设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置,rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
11. 利用两个栈 sl,s2 模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。
    栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。（1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1 栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元 素），则不能入队。（2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1 栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空， 队列空，不能出队。（3）判队空若栈s1为空并且s2也为空，才是队列空。
12. 名词解释：栈
    栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。
13. 名词解释：队列
    队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。
14. 什么是循环队列
    用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。