跳至主要內容

队列与栈

2026/9/15大约 4 分钟

队列与栈

1. 考点：队列与栈的基本特点

4yQwqS

2. 考点：循环队列

Wy1tZ3

2.1 基本概念

  • 循环队列​：通过数组实现并通过整数取余运算来实现首尾相连的环形队列，从而解决普通队列假溢出问题。
  • 最大优点​：相比普通队列，入队和出队操作都​不需要移动队列中的其他元素。

2.2 核心公式与条件（假设队列总容量为 ​size）

  • 队空条件：

    head=tail\text{head} = \text{tail}

  • 队满条件：

    (tail+1)%size=head(\text{tail} + 1) \% \text{size} = \text{head}

(注：通常会浪费一个存储单元来区分队空和队满)

  • 队列长度计算公式：

    (tail−head+size)%size(\text{tail} - \text{head} + \text{size}) \% \text{size}

3. 经典例题

3.1 题目一

题目： 设有栈 SS 和队列 QQ 初始状态为空，数据元素序列 a,b,c,d,e,fa, b, c, d, e, f 依次通过栈 SS，且多个元素从 SS 出栈后立即进入队列 QQ，若出队的序列是 b,d,f,e,c,ab, d, f, e, c, a，则 SS 中的元素最多时，栈底到栈顶的元素依次为（ C ）。

  • A. a,b,ca, b, c
  • B. a,c,da, c, d
  • C. a,c,e,fa, c, e, f
  • D. a,d,f,ea, d, f, e

详细解析：

  1. 明确队列的进出规律：

    • 队列 QQ 是先进先出（FIFO）的。既然题目给出的最终出队序列是 b,d,f,e,c,ab, d, f, e, c, a，说明元素进入队列 QQ 的顺序必然也是 ​**b,d,f,e,c,ab, d, f, e, c, a**。
    • 因为元素是从栈 SS 出栈后立即进入队列 QQ 的，所以元素从栈 SS 出栈的顺序也必须是：​**b→d→f→e→c→ab \rightarrow d \rightarrow f \rightarrow e \rightarrow c \rightarrow a**。

  2. 模拟进栈与出栈过程：
    我们要按照上述出栈顺序，配合输入序列 a,b,c,d,e,fa, b, c, d, e, f 来推导栈 SS 的变化状态：

    • 目标 1：先出栈 bb

      • 必须先将 aa 入栈，再将 bb 入栈。
      • 此时栈 SS（栈底到栈顶）：[a,b][a, b]
      • 出栈 bb（进入队列 QQ）。此时栈 SS 剩：[a][a]

    • 目标 2：接着出栈 dd

      • 必须先将 cc 入栈，再将 dd 入栈。
      • 入栈 cc 后，栈 SS：[a,c][a, c]
      • 入栈 dd 后，栈 SS：[a,c,d][a, c, d]
      • 出栈 dd（进入队列 QQ）。此时栈 SS 剩：[a,c][a, c]

    • 目标 3：接着出栈 ff

      • 必须先将 ee 入栈，再将 ff 入栈。
      • 入栈 ee 后，栈 SS：[a,c,e][a, c, e]
      • 入栈 ff 后，栈 SS：[a,c,e,f][a, c, e, f] （​此时栈中元素最多，共 44 个）
      • 出栈 ff（进入队列 QQ）。此时栈 SS 剩：[a,c,e][a, c, e]

    • 后续出栈（验证）：

      • 依次出栈 ee →\rightarrow 栈 SS 剩：[a,c][a, c]
      • 依次出栈 cc →\rightarrow 栈 SS 剩：[a][a]
      • 依次出栈 aa →\rightarrow 栈 SS 为空。

正确答案：C. a,c,e,fa, c, e, f 。

3.2 题目二

题目： 双端队列是指在队列的两个端口都可以加入和删除元素，如下图所示。现在要求元素进队列和出队列必须在同一端口，即从 A 端进队的元素必须从 A 端出，从 B 端进队的元素必须从 B 端出。则对于 4 个元素的序列 a,b,c,da, b, c, d，若要求前 2 个元素（a,ba, b）从 A 端口按次序全部进入队列，后两个元素（c,dc, d）从 B 端口按次序全部进入队列，则不可能得到的出列序列是（ A ）。

  • A. d,a,b,cd, a, b, c
  • B. d,c,b,ad, c, b, a
  • C. b,a,d,cb, a, d, c
  • D. b,d,c,ab, d, c, a

详细解析：

  1. 理解题目规则（等效模型）：

    • 元素 a,ba, b 从 A 端进，也必须从 A 端出 —— 这相当于一个​独立的栈 SAS_A（只能对 a,ba, b 进行进栈和出栈操作）。
    • 元素 c,dc, d 从 B 端进，也必须从 B 端出 —— 这相当于另一个​独立的栈 SBS_B（只能对 c,dc, d 进行进栈和出栈操作）。
    • 因此，整个结构被拆分成了两个互不干涉的独立栈：栈 **SAS_A**​ （管理 a,ba, b​ ） 和 ​栈 **SBS_B**​ （管理 **c,dc, d**​ ） 。

  2. 分析两个栈的内部出栈规律：

    • 对于 ​栈 SAS_A（元素 a,ba, b 依次入栈）：其合法的出栈顺序只能是 ​**b,ab, a**。
    • 对于 ​栈 SBS_B（元素 c,dc, d 依次入栈）：其合法的出栈顺序只能是 ​**d,cd, c**。
    • 核心约束​：最终的全局出栈序列，必须是这两个独立子序列交织（归并）的结果，但​绝对不能破坏各自内部原有的相对先后顺序（即 aa 必须在 bb 之后出栈，cc 必须在 dd 之后出栈）。

  3. 逐项验证选项：

    • 选项 A：​**d,a,b,cd, a, b, c**

      • 检查 aa 和 bb 的相对顺序：在序列中 aa 在 bb 前面（aa 先出栈，bb 后出栈），这违背了栈 SAS_A 必须先出 bb 再出 aa 的原则。因此该序列​不可能得到（正确答案）。

    • 选项 B：​**d,c,b,ad, c, b, a**

      • c,dc, d 的顺序是 dd 在 cc 前（符合 SBS_B）；a,ba, b 的顺序是 bb 在 aa 前（符合 SAS_A）。合法。

    • 选项 C：​**b,a,d,cb, a, d, c**

      • a,ba, b 的顺序是 bb 在 aa 前（符合 SAS_A）；c,dc, d 的顺序是 dd 在 cc 前（符合 SBS_B）。合法。

    • 选项 D：​**b,d,c,ab, d, c, a**

      • a,ba, b 的相对顺序中 bb 先出；c,dc, d 的相对顺序中 dd 先出。合法。

正确答案：A. d,a,b,cd, a, b, c 。

‍

最近更新:
贡献者: 黄炼