3.2 队列·习题

教材导航 · 返回本节知识

复习入口

3.2 队列 · 3.2.1 队列的基本概念 · 3.2.2 队列的顺序存储结构 · 3.2.2.1 循环队列 · 3.2.3 队列的链式存储结构 · 3.2.4 双端队列

本节共28题:选择题24题,综合应用题4题。每题答案紧接题目折叠显示。

文字转录进度:28/28题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P81 · 解析P84 · 目视转录

栈和队列的主要区别在于( )。

A. 它们的逻辑结构不一样

B. 它们的存储结构不一样

C. 所包含的元素不一样

D. 插入、删除操作的限定不一样

查看答案与解析

答案:D。

栈和队列的逻辑结构都是线性结构,都可以采用顺序存储或链式存储,选项 C 显然也错误。只有选项 D 才是栈和队列的本质区别,限定表中插入和删除操作位置的不同。

单项选择题 02

原书题目P81 · 解析P84 · 目视转录

队列的“先进先出”特性是指( )。

Ⅰ. 最后插入队列中的元素总是最后被删除

Ⅱ. 当同时进行插入、删除操作时,总是插入操作优先

Ⅲ. 每当有删除操作时,总要先做一次插入操作

Ⅳ. 每次从队列中删除的总是最早插入的元素

A. Ⅰ

B. Ⅰ和Ⅳ

C. Ⅱ和Ⅲ

D. Ⅳ

查看答案与解析

答案:B。

队列“先进先出”的特性表现在:先入队列的元素先出队列,后入队列的元素后出队列。入队对应的是插入操作,出队对应的是删除操作。选项Ⅰ和Ⅳ均正确。

单项选择题 03

原书题目P82 · 解析P84 · 目视转录

允许对队列进行的操作有( )。

A. 对队列中的元素排序

B. 取出最近入队的元素

C. 在队列元素之间插入元素

D. 删除队首元素

查看答案与解析

答案:D。

删除队首元素即出队,是队列的基本操作之一,所以选择选项 D。

单项选择题 04

原书题目P82 · 解析P84 · 目视转录

一个队列的入队顺序是 1、2、3、4,则出队的输出顺序是( )。

A. 4、3、2、1

B. 1、2、3、4

C. 1、4、3、2

D. 3、2、4、1

查看答案与解析

答案:B。

队列的入队顺序和出队顺序是一致的,这是和栈不同的。

单项选择题 05

原书题目P82 · 解析P84 · 目视转录

循环队列存储在数组 A[0…n] 中,入队时的操作为( )。

A. rear=rear+1

B. rear=(rear+1) mod (n-1)

C. rear=(rear+1) mod n

D. rear=(rear+1) mod (n+1)

查看答案与解析

答案:D。

数组下标范围为 0∼n0\sim n,因此数组容量为 n+1n+1。循环队列中元素入队的操作是 rear=(rear+1) mod maxsize,题中 maxsize=n+1。因此入队操作应为 rear=(rear+1) mod (n+1)。

单项选择题 06

原书题目P82 · 解析P84 · 目视转录

已知循环队列的存储空间为数组 A[21],front 指向队首元素的前一个位置,rear 指向队尾元素,假设当前 front 和 rear 的值分别为 8 和 3,则该队列的长度为( )。

A. 5

B. 6

C. 16

D. 17

查看答案与解析

答案:C。

队列的长度为 (rear-front+maxsize)%maxsize=(rear-front+21)%21=16。这种情况和 front 指向当前元素,rear 指向队尾元素的下一个元素的计算是相同的。

注意:数组 A[n] 的下标范围为 0∼n−10\sim n-1。若写成 A[0…n],则说明下标范围为 0∼n0\sim n。

单项选择题 07

原书题目P82 · 解析P85 · 目视转录

若用数组 A[0…5] 实现循环队列,且当前 rear 和 front 的值分别为 1 和 5,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为( )。

A. 3 和 4

B. 3 和 0

C. 5 和 0

D. 5 和 1

查看答案与解析

答案:B。

循环队列中,每删除一个元素,队首指针 front=(front+1)%6,每插入一个元素,队尾指针 rear=(rear+1)%6。上述操作后,front=0,rear=3。

单项选择题 08

原书题目P82 · 解析P85 · 目视转录

假设用数组 Q[MaxSize] 实现循环队列,队首指针 front 指向队首元素的前一位置,队尾指针 rear 指向队尾元素,则判断该队列为空的条件是( )。

A. Q.rear==(Q.front+1)%MaxSize

B. (Q.rear+1)%MaxSize==Q.front+1

C. (Q.rear+1)%MaxSize==Q.front

D. Q.rear==Q.front

查看答案与解析

答案:D。

当队列中只有一个元素时,front 指向该元素的前一个位置,rear 指向该元素,因此当队列为空时,队首指针等于队尾指针,这样第一个元素入队后,才能符合题目要求。

单项选择题 09

原书题目P82 · 解析P85 · 目视转录

假设循环队列 Q[MaxSize] 的队首指针为 front,队尾指针为 rear,队列的最大容量为 MaxSize,此外,该队列再没有其他数据成员,则判断该队列已满是条件( )。

A. Q.front==Q.rear

B. Q.front+Q.rear>=MaxSize

C. Q.front==(Q.rear+1)%MaxSize

D. Q.rear==(Q.front+1)%MaxSize

查看答案与解析

答案:C。

既然不能附加任何其他数据成员,只能采用牺牲一个存储单元的方法来区分是队空还是队满,约定以“队列头指针在队尾指针的下一位置作为队满的标志”,因此选择选项 C。选项 A 是判断队列是否为空的条件,选项 B 和 D 都是干扰项。

注意:对于这类具体问题,举一些特例判断往往比直接思考问题能更快得到答案。

单项选择题 10

原书题目P82 · 解析P85 · 目视转录

假设用 A[0…n] 实现循环队列,front、rear 分别指向队首元素的前一个位置和队尾元素。若用 (rear+1)%(n+1)==front 作为队满标志,则( )。

A. 可用 front==rear 作为队空标志

B. 队列中最多可有 n+1n+1 个元素

C. 可用 front>rear 作为队空标志

D. 可用 (front+1)%(n+1)==rear 作为队空标志

查看答案与解析

答案:A。

若用 (rear+1)%(n+1)==front 作为队满标志,则说明题目采用了牺牲一个存储单元的方法来区分队空和队满,因此可用 front==rear 作为队空标志。

单项选择题 11

原书题目P82 · 解析P85 · 目视转录

与顺序队列相比,链式队列的( )。

A. 优点是队列的长度不受限制

B. 优点是入队和出队时间效率更高

C. 缺点是不能进行顺序访问

D. 缺点是不能根据队首指针和队尾指针计算队列的长度

查看答案与解析

答案:D。

虽然链式队列采用动态分配方式,但其长度也受内存空间的限制,不能无限制增长。顺序队列和链式队列的入队和出队时间复杂度均为 O(1)O(1)。顺序队列和链式队列都可以进行顺序访问。对于顺序队列,可通过队首指针和队尾指针计算队列中的元素个数,而链式队列则不能。

单项选择题 12

原书题目P82 · 解析P85 · 目视转录

下列描述的几种链表中,最适合用作队列的是( )。

A. 带队首指针和队尾指针的循环单链表

B. 带队首指针和队尾指针的非循环单链表

C. 只带队首指针的非循环单链表

D. 只带队首指针的循环单链表

查看答案与解析

答案:B。

因为队列需在双端进行操作,所以选项 C 和 D 的链表显然不太适合链队。对于选项 A,链表在完成入队和出队后还要修改为循环的,对于队列来说这是多余的(画蛇添足)。对于选项 B,因为有首指针,所以适合删除首结点;因为有尾指针,所以适合在其后插入结点。

单项选择题 13

原书题目P83 · 解析P85 · 目视转录

下列描述的几种链表中,最不适合用作链式队列的是( )。

A. 只带队首指针的非循环双链表

B. 只带队首指针的循环双链表

C. 只带队尾指针的循环双链表

D. 只带队尾指针的循环单链表

查看答案与解析

答案:A。

因为非循环双链表只带队首指针,所以在执行入队操作时需要修改队尾结点的指针域,而查找队尾结点需要 O(n)O(n) 的时间。选项 B、C 和 D 均可在 O(1)O(1) 的时间内找到队首和队尾。

单项选择题 14

原书题目P83 · 解析P85 · 目视转录

在用单链表实现队列时,队头设在链表的( )位置。

A. 链头

B. 链尾

C. 链中

D. 以上都可以

查看答案与解析

答案:A。

因为在队头做出队操作,为便于删除队首元素,所以总是选择链头作为队头。

单项选择题 15

原书题目P83 · 解析P85 · 目视转录

用链式存储方式的队列进行删除操作时需要( )。

A. 仅修改头指针

B. 仅修改尾指针

C. 头尾指针都要修改

D. 头尾指针可能都要修改

查看答案与解析

答案:D。

队列用链式存储时,删除元素从表头删除,通常仅需修改头指针,但若队列中仅有一个元素,则队尾指针也需要被修改,当仅有一个元素时,删除后队列为空,需修改队尾指针为 rear=front。

单项选择题 16

原书题目P83 · 解析P85 · 目视转录

在一个链式队列中,假设队首指针为 front,队尾指针为 rear,xx 所指向的元素需要入队,则需要执行的操作为( )。

A. front=x, front=front->next

B. x->next=front->next, front=x

C. rear->next=x, rear=x

D. rear->next=x, x->next=NULL, rear=x

查看答案与解析

答案:D。

插入操作时,先将结点 xx 插入到链表尾部,再让 rear 指向这个结点 xx。选项 C 的做法不够严密,因为是队尾,所以队尾 x->next 必须置为空。

单项选择题 17

原书题目P83 · 解析P86 · 目视转录

假设循环单链表表示的队列长度为 nn,队头固定在链表尾,若只设头指针,则入队操作的时间复杂度为( )。

A. O(n)O(n)

B. O(1)O(1)

C. O(n2)O(n^2)

D. O(nlog⁡2n)O(n\log_2 n)

查看答案与解析

答案:A。

依题意,入队操作是在队尾进行,即链表表头。题中已明确说明链表只设头指针,即没有头结点和尾指针,入队后,循环单链表必须保持循环的性质,在只带头指针的循环单链表中寻找表尾结点的时间复杂度为 O(n)O(n),所以入队的时间复杂度为 O(n)O(n)。

单项选择题 18

原书题目P83 · 解析P86 · 目视转录

假设输入序列为 1、2、3、4、5,利用两个队列进行出入队操作,不可能输出的序列是( )。

A. 1、2、3、4、5

B. 5、2、3、4、1

C. 1、3、2、4、5

D. 4、1、5、2、3

查看答案与解析

答案:B。

此类题可对各选项进行模拟,假设队列为 Q1Q_1 和 Q2Q_2。对于选项 A,元素依次入队 Q1Q_1,然后依次出队。对于选项 B,5 最先出队,只可能是 1、2、3、4 入队 Q1Q_1,5 入队 Q2Q_2,然后 5 出队,只能得到 5、1、2、3、4。对于选项 C,1、2、5 入队 Q1Q_1,3、4 入队 Q2Q_2,然后按要求出队。选项 D 的分析同选项 C。

单项选择题 19

原书题目P83 · 解析P86 · 目视转录

若以 1、2、3、4 作为双端队列的输入序列,则既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列是( )。

A. 1、2、3、4

B. 4、1、3、2

C. 4、2、3、1

D. 4、2、1、3

查看答案与解析

答案:C。

使用排除法。先看可由输入受限的双端队列产生的序列:设右端输入受限,1、2、3、4 依次左入,则依次左出可得 4、3、2、1,排除选项 A;左出、右出、左出、左出可得到 4、1、3、2,排除选项 B;再看可由输出受限的双端队列产生的序列:设右端输出受限,1、2、3、4 依次左入、左入、右入、左入,依次左出可得到 4、2、1、3,排除选项 D。

转录核对:原书第一种排除示例写成 4、3、2、1,与选项 A 的 1、2、3、4 不符。A 实际可由 1、2、3、4 依次左入后依次右出得到。

单项选择题 20

原书题目P83 · 解析P86 · 目视转录

【2010 统考真题】某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作,则不可能得到的出队序列是( )。

A. b、a、c、d、e

B. d、b、a、c、e

C. d、b、c、a、e

D. e、c、b、a、d

查看答案与解析

答案:C。

本题的队列实际上是一个输出受限的双端队列。A 操作:a 左入(或右入)、b 左入、c 右入、d 右入、e 右入。B 操作:a 左入(或右入)、b 左入、c 右入、d 左入、e 右入。D 操作:a 左入(或右入)、b 左入、c 左入、d 右入、e 左入。C 操作:a 左入(或右入)、b 右入,因为 d 未出,此时只能入队,c 怎么进都不可能在 b 和 a 之间。

【另解】初始时队列为空,第 1 个元素 a 左入(或右入)后,第 2 个元素 b 无论是左入还是右入都必与 a 相邻,而选项 C 中 a 与 b 不相邻,不合题意。

单项选择题 21

原书题目P83 · 解析P86 · 目视转录

【2011 统考真题】已知循环队列存储在一维数组 A[0…n-1] 中,且队列非空时 front 和 rear 分别指向队首元素和队尾元素。若初始时队列为空,且要求第一个进入队列的元素存储在 A[0] 处,则初始时 front 和 rear 的值分别是( )。

A. 0、0

B. 0、n−1n-1

C. n−1n-1、0

D. n−1n-1、n−1n-1

查看答案与解析

答案:B。

根据题意,第一个元素进入队列后存储在 A[0] 处,此时 front 和 rear 值都为 0。入队时因为要执行 (rear+1)%n 操作,所以若入队后指针指向 0,则 rear 初值为 n−1n-1,而因为第一个元素在 A[0] 中,插入操作只改变 rear 指针,所以 front 为 0 不变。

注意:①循环队列是指顺序存储的队列,而不是指逻辑上的循环,如循环单链表表示的队列不能称循环队列。②front 和 rear 的初值并不是固定的。

单项选择题 22

原书题目P83 · 解析P86 · 目视转录

【2014 统考真题】循环队列放在一维数组 A[0…M-1] 中,end1 指向队首元素,end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳 M−1M-1 个元素。初始时为空。下列判断队空和队满的条件中,正确的是( )。

A. 队空:end1==end2;队满:end1==(end2+1) mod M

B. 队空:end1==end2;队满:end2==(end1+1) mod (M-1)

C. 队空:end2==(end1+1) mod M;队满:end1==(end2+1) mod M

D. 队空:end1==(end2+1) mod M;队满:end2==(end1+1) mod (M-1)

查看答案与解析

答案:A。

end1 指向队首元素,可知出队操作是先从 A[end1] 读数,然后 end1 再加 1。end2 指向队尾元素的后一个位置,可知入队操作是先存数到 A[end2],然后 end2 再加 1。

若用 A[0] 存储第一个元素,则队列初始时,入队操作先把数据放到 A[0] 中,然后 end2 自增,即 end2 初值为 0;而 end1 指向的是队首元素,队首元素在数组 AA 中的下标为 0,所以得知 end1 的初值也为 0,可知队空条件为 end1==end2。

然后考虑队列满时,因为队列最多能容纳 M−1M-1 个元素,假设队列存储在下标为 0 到 M−2M-2 的 M−1M-1 个区域,队头为 A[0],队尾为 A[M-2],此时队列满,考虑在这种情况下 end1 和 end2 的状态,end1 指向队首元素,可知 end1=0,end2 指向队尾元素的后一个位置,可知 end2=M−2+1=M−1M-2+1=M-1,所以队满条件为 end1==(end2+1) mod M。

单项选择题 23

原书题目P83 · 解析P86 · 目视转录

【2018 统考真题】现有队列 Q 与栈 S,初始时 Q 中的元素依次是 1、2、3、4、5、6(1 在队头),S 为空。若仅允许下列 3 种操作:①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素,则不能得到的输出序列是( )。

A. 1、2、5、6、4、3

B. 2、3、4、5、6、1

C. 3、4、5、6、1、2

D. 6、5、4、3、2、1

查看答案与解析

答案:C。

选项 A 的操作顺序为①①②②①①③③。选项 B 的操作顺序为②①①①①①③。选项 D 的操作顺序为②②②②②①③③③③③。对于选项 C:首先输出 3,说明 1 和 2 必须先依次入栈,而此后 2 肯定比 1 先输出,因此无法得到 1、2 的输出顺序。

单项选择题 24

原书题目P84 · 解析P87 · 目视转录

【2021 统考真题】初始为空的队列 Q 的一端仅能进行入队操作,另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5,则不能得到的出队序列是( )。

A. 5、4、3、1、2

B. 5、3、1、2、4

C. 4、2、1、3、5

D. 4、1、3、2、5

查看答案与解析

答案:D。

假设队列左端允许入队和出队,右端只能入队。对于选项 A,依次从右端入队 1、2,再从左端入队 3、4、5。对于选项 B,从右端入队 1、2,然后从左端入队 3,再从右端入队 4,最后从左端入队 5。对于选项 C,从左端入队 1、2,然后从右端入队 3,再从左端入队 4,最后从右端入队 5。无法验证选项 D 的序列。

综合应用题

综合应用题 01

原书题目P84 · 解析P87 · 目视转录

若希望循环队列中的元素都能得到利用,则需设置一个标志域 tag,并以 tag 的值为 0 或 1 来区分队首指针 front 和队尾指针 rear 相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队和出队算法。

查看答案与解析

在循环队列的类型结构中,增设一个整型变量 tag,入队时置 tag 为 1,出队时置 tag 为 0(因为只有入队操作可能导致队满,也只有出队操作可能导致队空)。队列 Q 初始时,置 tag=0、front=rear=0。这样队列的 4 要素如下:

  • 队空条件:Q.front==Q.rear 且 Q.tag==0。
  • 队满条件:Q.front==Q.rear 且 Q.tag==1。
  • 入队操作:Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MaxSize; Q.tag=1;
  • 出队操作:x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; Q.tag=0;

1)设“tag”法的循环队列入队算法:

int EnQueue1(SqQueue &Q,ElemType x){
    if(Q.front==Q.rear&&Q.tag==1)
        return 0;                    // 两个条件都满足时则队满
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    Q.tag=1;                          // 可能队满
    return 1;
}

2)设“tag”法的循环队列出队算法:

int DeQueue1(SqQueue &Q,ElemType &x){
    if(Q.front==Q.rear&&Q.tag==0)
        return 0;                    // 两个条件都满足时则队空
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    Q.tag=0;                          // 可能队空
    return 1;
}

综合应用题 02

原书题目P84 · 解析P87 · 目视转录

Q 是一个队列,S 是一个空栈,实现将队列中的元素逆置的算法。

查看答案与解析

本题主要考查大家对队列和栈的特性与操作的理解。因为对队列的一系列操作不可能将其中的元素逆置,而栈可以将入栈的元素逆序提取出来,所以我们可以让队列中的元素逐个地出队、入栈;全部入栈后再逐个出栈、入队。

void Inverser(Stack &S,Queue &Q){
    // 本算法实现将队列中的元素逆置
    while(!QueueEmpty(Q)){
        x=DeQueue(Q);                 // 队列中全部元素依次出队
        Push(S,x);                    // 元素依次入栈
    }
    while(!StackEmpty(S)){
        Pop(S,x);                     // 栈中全部元素依次出栈
        EnQueue(Q,x);                 // 再入队
    }
}

综合应用题 03

原书题目P84 · 解析P88 · 目视转录

利用两个栈 S1 和 S2 来模拟一个队列,已知栈的 4 个运算定义如下。

Push(S,x);          // 元素x入栈S
Pop(S,x);           // S出栈并将出栈的值赋给x
StackEmpty(S);      // 判断栈是否为空
StackOverflow(S);   // 判断栈是否为满

如何利用栈的运算来实现该队列的 3 个运算(形参由读者根据要求自己设计)?

Enqueue;            // 将元素x入队
Dequeue;            // 出队,并将出队元素存储在x中
QueueEmpty;         // 判断队列是否为空
查看答案与解析

利用两个栈 S1 和 S2 来模拟一个队列,当需要向队列中插入一个元素时,用 S1 来存放已输入的元素,即 S1 执行入栈操作。当需要出队时,则对 S2 执行出栈操作。因为从栈中取出元素的顺序是原顺序的逆序,所以必须先将 S1 中的所有元素全部出栈并入栈到 S2 中,再在 S2 中执行出栈操作,即可实现出队操作,而在执行此操作前必须判断 S2 是否为空,否则会导致顺序混乱。当栈 S1 和 S2 都为空时队列为空。

总结如下:

1)对 S2 的出栈操作用作出队,若 S2 为空,则先将 S1 中的所有元素送入 S2。

2)对 S1 的入栈操作用作入队,若 S1 满,必须先保证 S2 为空,才能将 S1 中的元素全部插入 S2 中。

入队算法:

int EnQueue(Stack &S1,Stack &S2,ElemType e){
    if(!StackOverflow(S1)){
        Push(S1,e);
        return 1;
    }
    if(StackOverflow(S1)&&!StackEmpty(S2)){
        printf("队列为满");
        return 0;
    }
    if(StackOverflow(S1)&&StackEmpty(S2)){
        while(!StackEmpty(S1)){
            Pop(S1,x);
            Push(S2,x);
        }
    }
    Push(S1,e);
    return 1;
}

出队算法:

void DeQueue(Stack &S1,Stack &S2,ElemType &x){
    if(!StackEmpty(S2)){
        Pop(S2,x);
    }
    else if(StackEmpty(S1)){
        printf("队列为空");
    }
    else{
        while(!StackEmpty(S1)){
            Pop(S1,x);
            Push(S2,x);
        }
        Pop(S2,x);
    }
}

判断队列为空的算法:

int QueueEmpty(Stack S1,Stack S2){
    if(StackEmpty(S1)&&StackEmpty(S2))
        return 1;
    else
        return 0;
}

综合应用题 04

原书题目P84 · 解析P89 · 目视转录

【2019 统考真题】请设计一个队列,要求满足:①初始时队列为空;②入队时,允许增加队列占用空间;③出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减;④入队操作和出队操作的时间复杂度始终保持为 O(1)O(1)。请回答:

  1. 该队列是应该选择链式存储结构,还是应该选择顺序存储结构?
  2. 画出队列的初始状态,并给出判断队空和队满的条件。
  3. 画出第一个元素入队后的队列状态。
  4. 给出入队操作和出队操作的基本过程。
查看答案与解析

1)顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析:要求①容易满足;链式存储方便开辟新空间,要求②容易满足;对于要求③,让出队后的结点并不真正释放,用队首指针指向新的队头结点,新元素入队时,有空余结点则无须开辟新空间,赋值到队尾后的第一个空结点即可,然后用队尾指针指向新的队尾结点,这就需要设计成一个首尾相接的循环单链表,类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为 O(1)O(1),要求④可以满足。

因此,采用链式存储结构(两段式单向循环链表),队首指针为 front,队尾指针为 rear。

2)该循环链式队列的实现可以参考循环队列,不同之处在于循环链式队列可以方便地增加空间,出队的结点可以循环利用,入队时空间不够也可以动态增加。同样,循环链式队列也要区分队满和队空的情况,这里参考循环队列牺牲一个单元来判断。初始时,创建只有一个空结点的循环单链表,头指针 front 和尾指针 rear 均指向空结点。

front ─┐
       ↓
     [空结点] ─┐
       ↑      │
rear ──┘      │
       ↑______┘  (next指向自身)

队空的判定条件:front==rear。

队满的判定条件:front==rear->next。

3)插入第一个元素后的状态:

front → [第一个元素] → [空结点] ← rear
             ↑_____________│

其中 front 指向队首元素,rear 指向下一个可写的空结点。

4)操作的基本过程如下:

入队操作:

若 (front==rear->next)                  // 队满
    则在rear后面插入一个新的空闲结点;
入队元素保存到rear所指结点中;rear=rear->next;返回。

出队操作:

若 (front==rear)                        // 队空
    则出队失败,返回;
取front所指结点中的元素;front=front->next;返回。