第三章 栈和队列

栈和队列是两种重要的抽象数据类型，是一类操作受限制的线性表，其特殊性在于限制了插入和删除等位置的操作。

栈和队列的共同特点是在线性表端点进行操作，从数据结构角度看，他们都是线性结构。

栈：用户只能在指定的一端插入和删除元素，具有先进后出的特点

队列：用户只能在一端插入元素，而在另一端删除元素，具有先进先出的特点

一、选择题

1.所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。（F）

为充分利用向量空间，克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

循环队列是一种数据结构，而单向循环链表和循环数组都是具体的实现方法并不是数据结构的本身。

2.?在用数组表示的循环队列中，front值一定小于等于rear值。（F）

1.在顺序队列中，当队尾指针已经到数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫做“假溢出”，解决假溢出的途径--?采用循环队列。

2.消除假溢出就是当队尾指针rear和队头指针front到达存储空间最大值N，让队尾指针自动转化为存储空间的最小值0.

3.?front = (rear +1)%N

入队元素的总个数>数组大小的个数

用数组表示的循环队列中，front值一定小于等于rear值的原因是为了区分队列为空和队列为满的情况。

当队列为空时，front和rear的值都为0，表示队列中没有元素。

当队列为满时，rear的值指向最后一个元素，而front的值指向第一个元素的前一个位置。这样做的目的是为了区分队列为空和队列为满的情况，以便正确判断队列的状态。

如果front的值大于rear的值，表示队列为空。

如果front的值等于rear的值，表示队列中只有一个元素。

如果front的值小于rear的值，表示队列中有多个元素。

因此，在用数组表示的循环队列中，front值一定小于等于rear值。

3.若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列(T)

A．1 2 3 4 5
B．5 4 3 2 1
C．2 3 4 5 1
D．4 1 2 3 5

由于栈的特点是：先进后出

A.1进1出 2进2出 3进3出 4进4出 5进5出

B.1进 2进 3进 4 进 5进 5出 4出 3出 2出 1出

C.1进 2进 2出 3进3出 4进4出 5进5出 1出

D.1进 2进 3进 4进 4出 5进 1出 2 出 3出 5出（因为1先进所以1应该在2后面出）

1进 2进 3进 3出 4进4出 1出? 2出 5进5出 （1应该在2的后面出）

4.?栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。（T）

栈有两种基本的存储结构：顺序存储结构和链式存储结构

队列也有两种春初表示：顺序表示和链式表示

5.?栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。（T）

6.通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。(F)

栈的特点：先进后出

push 【1,2】

pop? ?2

push? 【1,3】

pop? ?3

push? ?【1】

pop? ?1

栈为空

所以输出的序列应为：2 3 1

二、判断题

1.假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：（C）

A.2

B.3

C.4

D.5

栈中元素【1,2,3】

再让3出栈

pop 3

栈中元素【1,2,4,5】

pop 5 4 2 1

即：出栈顺序为3 5 4 2 1 所以，堆栈大小至少应为4

2.?若栈采用顺序存储方式存储，现两栈共享空间V[m]：top[i]代表第i（i=1或2）个栈的栈顶；栈1的底在V[0]，栈2的底在V[m-1]，则栈满的条件是：(D)

A.|top[2]-top[1]|==0

B.top[1]+top[2]==m

C.top[1]==top[2]

D.top[1]+1==top[2]

?两个栈的共享技术，即双端栈，主要利用了栈的“栈底位置不变，而栈顶位置动态变化”特性，由于两个栈顶是动态变化的，这样可以形成互补。即栈满的条件是top[1]+1=top[2]

?3.若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？(A)

A.2和0

B.2和2

C.2和4

D.2和6

在队列中，允许插入的一端称为队尾（rear）,允许删除的一端则为队头（front）

循环队列中， 进队，队尾指针变化rear=(rear+1)mod maxsize

? ? ? ? ? ? ? ? ? ? ? 出队，队头指针变化front=(front+1)mod maxsize

即：删除两个元素，出队，队头front=2%6=2

? ? ? ?加入两个元素，进队，队尾rear=(4+2)%6=0;

?4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：(D)

A.b a c d e

B.d b a c e

C.e c b a d

D.d b c a e

设L代表左端入队，R代表从右端入队 ，出队都是从左边出队

A.a(L)??

5.如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为：（D）

A.front+size

B.front+size-1

C.(front+size)%m

D.(front+size-1)%m

1.空?front=rear

2.满 （rear+1%m=front

3.求循环队列长度 （rear-front+maxsize）%m;

4.rear:(front+size-1)%m;