LogicLab

Appearance

1.3节后习题 ​

题目要求 ​

1. 假设用长度为11的数组作为顺序队列，初始为空。分别绘出做完下列操作后的队列示意图。若有元素不能入队，说明理由。操作序列如下：

  1. A、B、C、D、E 依次入队；
  2. A、B 依次出队；
  3. F、G、H、I、J 依次入队；
  4. O、P、Q、R 依次入队。

2. 利用两个顺序栈 S1 和 S2 模拟一个队列。实现入队和出队操作，并说明基本思路。

操作序列/关键信息：

  1. 循环队列的 front、rear 变化及存储示意；
  2. 两栈入队直接压入 S1，出队时 S2 不空则弹出，否则将 S1 内容逆序压入 S2。

参考答案与解析 ​

参考答案 - 顺序循环队列操作示意图

一、顺序循环队列操作示意图 ​

操作frontrear队列内容
初始00[-, -, -, -, -, -, -, -, -, -, -]
入队 A,B,C,D,E05[A, B, C, D, E, -, -, -, -, -, -]
出队 A,B25[A, B, C, D, E, -, -, -, -, -, -] （实际存储 C,D,E 在索引2-4）
入队 F,G,H,I,J210[A, B, C, D, E, F, G, H, I, J, -]
入队 O,P21[O, P, C, D, E, F, G, H, I, J, -] （Q,R 无法入队，队满）

注：循环队列满条件为 (rear + 1) % 11 == front。最多存储 10 个元素。

参考答案 - 两栈模拟队列

二、两栈模拟队列 ​

基本思路：

  • 入队（enqueue）：直接将元素压入 S1。
  • 出队（dequeue）：若 S2 非空，直接弹出 S2 顶；否则将 S1 所有元素依次弹出并压入 S2，再弹出 S2 顶。
cpp
#include <iostream>
#include <stack>
#include <stdexcept>

class QueueUsingStacks {
private:
    std::stack<int> S1;
    std::stack<int> S2;
public:
    void enqueue(int x) {
        S1.push(x);
    }
    int dequeue() {
        if (!S2.empty()) {
            int v = S2.top(); S2.pop(); return v;
        } else if (!S1.empty()) {
            while (!S1.empty()) {
                S2.push(S1.top()); S1.pop();
            }
            int v = S2.top(); S2.pop(); return v;
        } else {
            throw std::runtime_error("Queue is empty");
        }
    }
};

核心知识点 ​

循环队列 ​

  1. 队空条件：front == rear。
  2. 队满条件：(rear + 1) % maxsize == front。

两栈模拟队列 ​

  1. 栈的后进先出（LIFO）特性。
  2. 入队效率：O(1)；出队效率：均摊 O(1)（摊销分析）。