3. 栈与队列

ABSTRACT · 本节范围 本笔记逐题覆盖原 PDF 的 5 道代码题：空栈辅助队列逆置、带头单链表中心对称、两栈共享数组、圆括号匹配、S/H 序列重排。所有实现统一采用 C++17，可直接编译；原稿中的边界与语法错误已在对应位置订正。

0. 公共约定

#include <array>
#include <cstddef>
#include <queue>
#include <stack>
#include <string>
#include <string_view>

struct LNode {
    char data{};
    LNode* next = nullptr;
};

• 栈顶元素通过 top() 读取，pop() 只负责删除；队头元素通过 front() 读取，pop() 负责出队。
• 除共享栈实现题外，优先使用抽象栈、队列操作，不把底层数组下标混入算法逻辑。
• 设待处理元素数为 $n$。若题目给定“辅助栈为空”，算法结束时也应恢复为空。

1. 用空栈逆置队列

1.1 题目

队列 $Q$ 中已有若干元素，栈 $S$ 为空。编写算法，利用 $S$ 将 $Q$ 中的元素逆置。

1.2 核心思路

设队头到队尾依次为

$$ a_1,a_2,\ldots,a_n. $$

先依次出队并压栈，栈顶到栈底便为 $a_n,a_{n-1},\ldots,a_1$；再依次出栈并入队，队列顺序即被逆置。

1.3 可运行实现

void reverseQueue(std::queue<int>& q, std::stack<int>& s) {
    // 前置条件：s 为空。
    while (!q.empty()) {
        s.push(q.front());
        q.pop();
    }

    while (!s.empty()) {
        q.push(s.top());
        s.pop();
    }
}

1.4 正确性与复杂度

• 第一阶段保持不变式：已经离开队列的元素按原顺序自栈底向栈顶排列。
• 第一阶段结束后，原队尾元素位于栈顶；第二阶段按栈的后进先出次序重新入队，因此结果恰为原序列的逆序。
• 每个元素恰好入栈、出栈、入队、出队各一次，时间复杂度为 $O(n)$。
• 辅助空间为 $O(n)$；空队列和单元素队列无需特殊分支。

WARNING · 易错点 若自行实现循环队列，不能只写 front != rear 就默认所有队列约定都相同；必须先明确空队列、满队列以及 front、rear 分别指向什么位置。

2. 判断带头单链表是否中心对称

2.1 题目

带头结点的单链表依次存放 $n$ 个字符，判断该字符序列是否中心对称，即是否为回文串。

2.2 核心思路

1. 从首元结点开始遍历，求表长 $n$。
2. 将前 $\lfloor n/2\rfloor$ 个字符依次压栈，此时指针位于后半部分之前。
3. 若 $n$ 为奇数，跳过唯一的中间结点。
4. 一边遍历后半部分，一边弹出前半部分字符比较；全部相等才是回文。

例如 abcba：栈中依次压入 a、b，跳过 c，再用栈顶 b、a 与后半段比较。

2.3 可运行实现

bool isPalindrome(const LNode* head) {
    // 题设为带头结点链表；空指针也按空序列处理。
    if (head == nullptr) {
        return true;
    }

    std::size_t length = 0;
    for (const LNode* p = head->next; p != nullptr; p = p->next) {
        ++length;
    }

    std::stack<char> firstHalf;
    const LNode* p = head->next;
    for (std::size_t i = 0; i < length / 2; ++i) {
        firstHalf.push(p->data);
        p = p->next;
    }

    if (length % 2 == 1) {
        p = p->next;  // 奇数长度时跳过中间结点。
    }

    while (p != nullptr) {
        if (firstHalf.empty() || firstHalf.top() != p->data) {
            return false;
        }
        firstHalf.pop();
        p = p->next;
    }
    return firstHalf.empty();
}

2.4 正确性与复杂度

• 栈顶始终是“前半部分中尚未比较、且最靠近中心”的字符，恰好对应后半部分当前字符。
• 偶数长度直接比较两半；奇数长度必须跳过中点，因为中点不影响回文性。
• 求长度、压栈和比较均为线性过程，总时间 $O(n)$；栈最多保存 $\lfloor n/2\rfloor$ 个字符，辅助空间 $O(n)$。

DANGER · 原稿错误 奇数判断应为 length % 2 == 1。原稿的 length * 2 == 1 对非负整数长度永远不成立，因此奇数长度链表会错位比较。

3. 两栈共享一个顺序存储区

3.1 题目

两个栈 $s_0,s_1$ 共用数组 data[0...MAX_SIZE-1]。$s_0$ 从低地址向高地址增长，$s_1$ 从高地址向低地址增长，设计入栈和出栈操作。

3.2 状态与判定

constexpr int MAX_SIZE = 100;

struct SharedStack {
    std::array<int, MAX_SIZE> data{};
    int top[2] = {-1, MAX_SIZE};
};

两栈共用唯一的空闲区，因此统一判满条件为

$$ top[0]+1=top[1]. $$

3.3 入栈与出栈

bool push(SharedStack& s, int which, int value) {
    if (which < 0 || which > 1) {
        return false;
    }
    if (s.top[0] + 1 == s.top[1]) {
        return false;  // 整个共享数组已满。
    }

    if (which == 0) {
        s.data[++s.top[0]] = value;
    } else {
        s.data[--s.top[1]] = value;
    }
    return true;
}

bool pop(SharedStack& s, int which, int& value) {
    if (which < 0 || which > 1) {
        return false;
    }

    if (which == 0) {
        if (s.top[0] == -1) {
            return false;
        }
        value = s.data[s.top[0]--];
    } else {
        if (s.top[1] == MAX_SIZE) {
            return false;
        }
        value = s.data[s.top[1]++];
    }
    return true;
}

这里用布尔返回值区分“操作成功”和“栈满、栈空或编号非法”，避免把 -1 同时当作合法数据和错误标志。

3.4 正确性与复杂度

• 两个栈顶始终从数组两端向中间逼近；区间 top[0]+1 ... top[1]-1 是全部剩余空间。
• 当两个栈顶相邻时，剩余空间长度为 0，故必须拒绝任一栈继续入栈。
• 入栈和出栈都只进行常数次判断、赋值和下标移动，时间复杂度均为 $O(1)$；结构本身占用 $O(\text{MAX_SIZE})$。

DANGER · 原稿错误 原稿的两条入栈语句只计算了数组位置，却没有执行 = value；栈 1 的判空也不应写成 top[1] != -MAX_SIZE。正确空状态是初始化值 top[1] == MAX_SIZE。

4. 判断圆括号是否匹配

4.1 题目

判断一个表达式中的圆括号是否配对。表达式中的非括号字符不参与匹配。

4.2 可运行实现

bool parenthesesMatched(std::string_view expression) {
    std::stack<char> leftParentheses;

    for (char ch : expression) {
        if (ch == '(') {
            leftParentheses.push(ch);
        } else if (ch == ')') {
            if (leftParentheses.empty()) {
                return false;  // 右括号没有可匹配的左括号。
            }
            leftParentheses.pop();
        }
    }
    return leftParentheses.empty();
}

4.3 两种失败情形

1. 扫描过程中遇到右括号而栈为空，例如 a+b)。
2. 扫描结束后栈仍非空，例如 (a+b。

算法对每个字符只访问一次，时间复杂度为 $O(n)$；最坏情况下全部是左括号，辅助空间为 $O(n)$。

TIP · 扩展到三类括号 若还包含 [] 和 {}，遇到右括号时不仅要先判空，还要检查栈顶左括号类型是否对应；任何一次类型不符都应立即返回 false。

DANGER · 原稿错误 左圆括号应压入 '('，不能压入 'C'；处理右括号前必须先判空。原稿还存在 return false' 等语法错误。

5. 将所有 S 移到 H 之前

5.1 题目

给定只含字符 S 和 H 的序列 HSSHHHS，利用栈将所有 S 移到所有 H 之前，得到 SSSHHHH。

5.2 核心思路

• 从左到右扫描：S 直接追加到结果，H 压入辅助栈。
• 扫描结束后，将栈中的所有 H 依次弹出并追加到结果。
• 由于题目中的 H 完全相同，出栈造成的逆序不可见；若元素还带有不同载荷，这一方法不保证 H 组内部稳定。

5.3 可运行实现

std::string moveSBeforeH(std::string_view input) {
    std::stack<char> hStack;
    std::string result;
    result.reserve(input.size());

    for (char ch : input) {
        if (ch == 'S') {
            result.push_back(ch);
        } else if (ch == 'H') {
            hStack.push(ch);
        }
    }

    while (!hStack.empty()) {
        result.push_back(hStack.top());
        hStack.pop();
    }
    return result;
}

5.4 正确性与复杂度

• 扫描结束时，结果串恰含输入中的全部 S，栈恰含输入中的全部 H。
• 清空栈后，结果串前段全是 S、后段全是 H，且两类字符的数量均与输入相同。
• 每个字符至多入栈、出栈或追加一次，时间复杂度 $O(n)$，辅助空间 $O(n)$。

WARNING · C++ 字符串边界 对空 std::string 直接写 result[j++] = ch 会越界；应使用 push_back 或先调整字符串长度。原稿还把已初始化的栈变量名和类型名混用，均已修正。

6. 源稿纠错汇总

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：链表代码 · 下一篇：二叉树代码
• 关联专题：栈与队列原理

7. 本节复盘

• 队列逆置依赖“队列保持次序、栈反转次序”的组合。
• 回文判断要区分奇偶长度：奇数跳过中点，偶数直接比较两半。
• 共享栈只有一个总判满条件，但两个栈各有自己的判空条件。
• 括号匹配既要防止“提前出现右括号”，又要检查“结束后仍有左括号”。
• 写代码题时必须同时交代初始化、边界条件、操作失败的表示方式、时间复杂度与空间复杂度。