数据结构之队列

选择题

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

A. 它们的逻辑结构不一样
B. 它们的存储结构不一样
C. 所包含的元素不一样
D. 插入、删除操作的限定不一样

答案：D
解释： 栈和队列的逻辑结构都是线性结构，都可以采用顺序存储或链式存储。它们的主要区别在于插入和删除操作的位置：栈是“后进先出”（LIFO），而队列是“先进先出”（FIFO）。

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

I. 最后插入队列中的元素总是最后被删除
II. 当同时进行插入、删除操作时，总是插入操作优先
III. 每当有删除操作时，总要先做一次插入操作
IV. 每次从队列中删除的总是最早插入的元素

A. I
B. I 和 IV
C. II 和 III
D. IV

答案：B
解释： 队列的“先进先出”特性体现在：最早进入队列的元素最先被删除，因此 I 和 IV 是正确的。 II 和 III 的描述不符合队列的基本特性。

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

A. 对队列中的元素排序
B. 取出最近进队的元素
C. 在队列元素之间插入元素
D. 删除队头元素

答案：D
解释： 删除队头元素即出队，是队列的基本操作之一。选项 A、B、C 都不是队列的基本操作。

04. 一个队列的入队顺序是 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
解释： 在队列中，元素是先进先出（FIFO）的。由于入队顺序是 1, 2, 3, 4，因此出队顺序也会是 1, 2, 3, 4。

05. 循环队列存储在数组 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)

答案：C
解释： 在循环队列中，入队操作是通过计算新的 rear 指针位置来实现的。在数组下标范围为 0 到 n，因此数组的有效大小是 n，入队操作应为 rear = (rear + 1) mod n。

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

A. 5
B. 6
C. 16
D. 17

答案：C
解释： 在循环队列中，队列的长度可以通过公式 $(rear - front + MaxSize) \mod MaxSize$ 计算。当前队列长度为 $(3 - 8 + 21) \mod 21 = 16$。

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

A. 3 和 4
B. 3 和 0
C. 5 和 0
D. 5 和 1

答案：B
解释： 在循环队列中，删除元素时 front 指针向前移动一位，插入元素时 rear 指针向前移动一位。初始状态为 front = 5，rear = 1，删除一个元素后 front 变为 0。接着加入两个元素，rear 先变为 2，再变为 3。所以最终 front = 0，rear = 3。

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

A. Q.front == Q.rear
B. Q.front + Q.rear >= MaxSize
C. Q.front == (Q.rear + 1) mod MaxSize
D. Q.rear = (2.front + 1) mod MaxSize

答案：C
解释： 在循环队列中，队列满的条件是 front 指向 rear 的前一个位置，因此使用 (Q.rear + 1) mod MaxSize == Q.front 判断队列是否满。选项 A 是判断队列是否为空的条件，选项 B 和 D 均为干扰项。

09. 最适合用作链队的链表是()。

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

答案：B
解释： 带队首指针和队尾指针的非循环单链表适合链队，因为可以在 O(1) 时间内完成队首出队和队尾入队操作。而其他选项可能会导致在操作过程中需要遍历链表，降低效率。

10. 最不适合用作链式队列的链表是()。

A. 只带队首指针的非循环双链表
B. 只带队尾指针的循环双链表
C. 只带队首指针的循环双链表
D. 只带队尾指针的循环单链表

答案：A
解释： 只带队首指针的非循环双链表在执行入队操作时需要修改队尾结点的指针域，而查找队尾结点需要 O(n) 的时间，这样会影响操作效率。选项 B、C 和 D 都可以在 O(1) 的时间内找到队首和队尾，适合用作链式队列。

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

A. 链头
B. 链尾
C. 链中
D. 以上都可以

答案：A
解释： 在使用单链表实现队列时，为了便于进行出队操作，通常将队头指针设在链头位置，这样可以在 O(1) 时间内删除队头元素。

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

A. 仅修改头指针
B. 仅修改尾指针
C. 头尾指针都要修改
D. 头尾指针可能都要修改

答案：D
解释： 在链式存储方式的队列中，删除操作通常只需要修改头指针，但如果队列中仅有一个元素，删除后队列为空，此时需要同时修改尾指针。因此，正确答案是 D。

13. 在一个链队列中，假设队头指针为 front，队尾指针为 rear，x 所指向的元素需要入队，则需要执行的操作为()。

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
解释： 在链队列中，插入操作需要将新结点 x 插入到队尾，并将其 next 指针指向 null，然后将 rear 指针指向新插入的结点 x。选项 C 不够严密，因为没有将 x->next 设置为 null，这可能导致链表结构不正确。

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

A. $O(n) $ B. $O(1) $ C. $O(n^2) $ D. $O(n log n) $

答案：A
解释： 在循环单链表中，如果只设头指针，没有尾指针，进队操作时必须遍历整个链表找到尾结点，然后将新结点插入，时间复杂度为 O(n)。

15. 若以 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
解释： 通过排除法可以分析双端队列的特性：

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

16. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 $ 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：无法从队列中得到 $ d, b, c, a, e $ 这种顺序。

因此，选项 C 是不可能得到的出队序列。

17. 已知循环队列存储在一维数组 $ A[0...n-1] $ 中，且队列非空时 `front` 和 `rear` 分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在 $ A[0] $ 处，则初始时 `front` 和 `rear` 的值分别是()

A. $ 0, 0 $
B. $ 0, n-1 $
C. $ n-1, 0 $
D. $ n-1, n-1 $

答案： B

队列的初始化：
- 初始时，队列为空。
- 为了满足题意，首先需要让第一个元素（例如 $ a $）存储在 $ A[0] $。
指针的初始值：
- 在循环队列中，front 通常指向队头元素，而 rear 通常指向队尾元素的后一个位置。
- 因此，当队列为空时，front 和 rear 的初始化值通常是相同的，这里可以设为 0。
入队操作：
- 当第一个元素进入队列后，rear 进行 rear = (rear + 1) % n 操作。
- 如果 rear 的初始值是 $ n-1 $，那么进行上述操作后，rear 将指向 $ 0 $。
- 而此时 front 仍指向 $ 0 $（队头元素）。
总结：
- 初始时，front 和 rear 应该分别为 $ 0 $ 和 $ n-1 $。
- 经过第一次入队操作后，front 仍然指向队头元素，而 rear 被更新为 $ 0 $，但在指向第一个元素时，front 仍然指向 $ 0 $。

因此，正确答案应为 B. $ 0, n-1 $，表示队头指向第一个元素，而队尾指向最后一个位置的后一个位置。

18. 循环队列放在一维数组 $ A[0..M-1] $ 中，`end1` 指向队头元素，`end2` 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 $ M-1 $ 个元素。初始时为空。下列判断队空和队满的条件中，正确的是()

end1 == end2,(end2 + 1) \mod M == end1。

解释：

队空条件：end1 == end2，当指向相同位置时，队列为空。
队满条件：根据题意，队列最多能容纳 $ M-1 $ 个元素，因此当队列满时，end2 的下一个位置就是 end1，即 (end2 + 1) \mod M == end1。
综上所述，选项 A 是正确的，其他选项不满足队空和队满的条件。

19. 设有如下图所示的火车车轨，入口到出口之间有 $ n $ 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1~9 的 9 列列车，驶入的次序依次是 8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为 1~9，则 $ n $ 至少是( )。

A. 2
B. 3
C. 4
D. 5

答案： C.4

为了实现从 8, 4, 2, 5, 3, 9, 1, 6, 7 中按顺序输出 1 到 9 的目标，我们需要分析不同轨道的使用情况。

进入顺序和期望出序：
- 进入顺序：8, 4, 2, 5, 3, 9, 1, 6, 7
- 期望出序：1, 2, 3, 4, 5, 6, 7, 8, 9
通过轨道的排列实现出序：
- 列车在进入轨道后会按顺序停放，后续进入的列车可能会被迫停放在前面的列车后面。
- 由于车轨只能在一边出，后进入的列车会被限制在前面的列车后面，因此必须保证可以自由地从各个轨道中选出列车。
分析轨道数量：
- 假设 nnn 条轨道不够，可能出现后进的列车无法按顺序出轨的情况。为满足从 1 到 9 的输出顺序，必须至少有足够的轨道来安排它们的顺序。
- 具体分析：
  - 列车 8 进入后无法直接输出，必须先容纳后续列车。
  - 列车 4、2、5、3 等相继进入后，较小编号的列车（如 1、2、3、4）无法在没有额外轨道的情况下正确输出。
确认轨道数量：
- 需要至少 4 条轨道来有效安排这些列车的进出，以避免阻塞。
  - 例如：
    - 轨道 1：8
    - 轨道 2：4
    - 轨道 3：2
    - 轨道 4：5、3、9、1、6、7

由此可见，至少需要 4 条轨道来保证在进入顺序与输出顺序之间能够顺利进行。因此，答案为 C. 4。

20.题目：现有队列 $ 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. 3, 4, 5, 6, 1, 2

解释

操作分析：
- 通过允许的操作，我们可以先将元素出队到栈 $ S $，然后再从栈中出栈输出元素。
- 栈的特性是后进先出 (LIFO)，这会影响我们能否得到某些输出顺序。
逐一验证选项：
- A. 1, 2, 5, 6, 4, 3：
  - 先出队 1, 2, 5, 6；再出队 4, 3 可行。
- B. 2, 3, 4, 5, 6, 1：
  - 先出队 2, 3；再将 4, 5, 6 进入栈，最后将 1 出队可行。
- C. 3, 4, 5, 6, 1, 2：
  - 先出队 3 进入栈，然后无法在栈中有序地输出 4, 5, 6 后再输出 1, 2，因此不可行。
- D. 6, 5, 4, 3, 2, 1：
  - 将所有元素出队到栈，再反向出栈可行。

因此，选项 C 是不能得到的输出序列。

21. 初始为空的队列 $ 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

操作机制分析：
- 一端可以入队，另一端可以进行入队和出队。
- 入队序列为 1, 2, 3, 4, 5。
- 我们需要分析每个选项是否可以通过允许的操作顺序得到。
逐一验证选项：
- A. 5, 4, 3, 1, 2：
  - 可以通过先从另一端入队 1, 2，随后入队 3, 4, 5，再出队 5, 4, 3，最后出队 1, 2，达到此顺序。
- B. 5, 3, 1, 2, 4：
  - 可以先将 1, 2 入队，然后再入队 3, 4, 5，出队 5, 3, 1, 2，最后出队 4，达到此顺序。
- C. 4, 2, 1, 3, 5：
  - 可以先入队 1, 2，接着入队 3, 4，出队 4, 2, 1，最后出队 3, 5，达到此顺序。
- D. 4, 1, 3, 2, 5：
  - 不可行。若 4 首先出队，意味着 4 必须在入队过程中已准备好出队，这需要先将 1, 2 入队，然而在出队 1 和 2 之前，4 无法在出队顺序中首先出现，因为这样会违背队列的特性。

综合应用题

题目 1：循环队列的入队和出队算法

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

解答：

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

队空条件: Q.front==Q.rear 且 Q.tag==0。
队满条件: Q.front==Q.rear 且 Q.tag==1。

进队操作算法：

int EnQueue(SqQueue &Q, ElemType x) {
    // 检查队列是否满
    if (Q.front == Q.rear && Q.tag == 1)
        return 0; // 队满

    Q.data[Q.rear] = x; // 将元素 x 插入队列
    Q.rear = (Q.rear + 1) % MaxSize; // 更新 rear 指针
    Q.tag = 1; // 可能队满
    return 1; // 成功入队
}

出队操作算法：

int DeQueue(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; // 更新 front 指针
    Q.tag = 0; // 可能队空
    return 1; // 成功出队
}

题目 2：利用栈实现队列的操作

利用两个栈 s1 和 s2 来模拟一个队列，已知栈的四个运算定义如下：

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

请设计相应的队列操作。

解答：

入队算法：

int EnQueue(Stack &s1, Stack &s2, ElemType e) {
    // 判断栈 s1 是否满
    if (!StackOverflow(s1)) {
        Push(s1, e); // 将元素 e 入栈 s1
        return 1; // 成功入队
    }

    // 若 s1 满且 s2 不为空
    if (StackOverflow(s1) && !StackEmpty(s2)) {
        printf("队列满\n");
        return 0; // 队列满
    }

    // 若 s1 满且 s2 为空，先将 s1 中元素转移到 s2
    if (StackOverflow(s1) && StackEmpty(s2)) {
        while (!StackEmpty(s1)) {
            ElemType x;
            Pop(s1, x); // 从 s1 出栈
            Push(s2, x); // 入栈到 s2
        }
    }

    Push(s1, e); // 将元素 e 入栈 s1
    return 1; // 成功入队
}

出队算法：

void DeQueue(Stack &s1, Stack &s2, ElemType &x) {
    // 若 s2 不为空，直接出栈
    if (!StackEmpty(s2)) {
        Pop(s2, x); // 从 s2 出栈
        return; // 成功出队
    } else if (StackEmpty(s1)) {
        printf("队列为空\n"); // 队列为空
        return;
    }

    // 将 s1 中所有元素转移到 s2
    while (!StackEmpty(s1)) {
        ElemType y;
        Pop(s1, y); // 从 s1 出栈
        Push(s2, y); // 入栈到 s2
    }

    // 现在 s2 中有元素，可以出栈
    Pop(s2, x); // 从 s2 出栈
}

判断队列是否为空的算法：

int QueueEmpty(Stack &s1, Stack &s2) {
    // 判断 s1 和 s2 是否均为空
    if (StackEmpty(s1) && StackEmpty(s2))
        return 1; // 队列为空
    else
        return 0; // 队列不为空
}

题目三：设计一个队列，要求满足以下条件：

初始时队列为空。
入队时，允许增加队列占用空间。
出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减。
入队操作和出队操作的时间复杂度始终保持为 $O(1)$。

请回答下列问题：

该队列应选择链式存储结构，还是顺序存储结构？
画出队列的初始状态，并给出判断队空和队满的条件。
画出第一个元素入队后的队列状态。
给出入队操作和出队操作的基本过程。

1) 存储结构选择

选择链式存储结构（循环链式队列），原因如下：

动态扩展：链式存储结构允许在入队时动态增加空间，符合题目中“入队时，允许增加队列占用空间”的要求。
空间重用：出队后，结点所占用的空间可以被重新利用，无需真正释放，适合题目中“出队元素所占用的空间可重复使用”的要求。
时间复杂度：链式存储结构的入队和出队操作可以通过维护头指针和尾指针实现，时间复杂度为 $O(1)$。

2) 队列的初始状态及判断条件

队列初始状态：

初始时，队列为空，头指针 front 和尾指针 rear 均指向一个空闲结点（即一个哨兵节点）。

1	front → [空闲结点] ← rear

判断条件：

队空条件：front == rear，即头指针与尾指针相等，表示队列为空。
队满条件：由于采用循环链式队列，如果 rear->next == front，则表示队列满。

3) 第一个元素入队后的队列状态

插入第一个元素后的状态：

在入队操作后，假设插入的元素为 A，状态如下：

1	front → [A] → rear

此时，front 和 rear 指向相同的节点，但 rear 仍然指向队列的尾部，front 移动到下一个节点。

4) 入队操作和出队操作的基本过程

入队操作：

检查队满条件：if (rear->next == front)，若队满则无法入队，返回失败。
在 rear 后面插入一个新的空闲结点。
将待入队元素保存到 rear 所指结点中。
更新 rear 指针：rear = rear->next。

出队操作：

检查队空条件：if (front == rear)，若队空则无法出队，返回失败。
取 front 所指结点中的元素 e。
更新 front 指针：front = front->next。
返回出队元素 e。