第三章栈和队列

一、栈（Stack）

1.1 括号匹配：问题引入与算法思想

引入问题：编译器遇到括号不匹配的代码会报错（如 error: expected '}'），核心问题是"编译器如何快速定位括号匹配错误"。
括号匹配规则：从左往右遍历序列，当遇到右括号时，必须存在一个最近的、未闭合的左括号，且两者类型相同；当遍历完整个序列，必须不存在未闭合的左括号。
示例：正确 ()[{}]；错误 ([)]、(()。
能否只靠左右括号数量判断？不能。仅数量相等不足以判断：() {} 数量相等且正确，但 (}{)（或 ([)]）数量相等却错误。不仅要关注数量，还需要关注位置。
核心思路：每次看到一个右括号时，向左扫描之前最近的左括号是否匹配；一个左括号只能匹配一个右括号；所有左括号都必须被匹配。

括号匹配算法（容器操作抽象）

需要一种容器来存储左括号，并执行以下操作：
- 遇到左括号：存入容器。
- 遇到右括号：取出最后存入的元素进行检查；匹配则取出该元素，不匹配则报错并结束。
- 遍历结束：容器为空则配对成功，否则报错。
该容器所需的特性即"后进先出"，这正是栈。
执行轨迹示例（输入 (()[])，容器即栈，自栈底到栈顶书写）：读 ( → Push（容器 (）；读 ( → Push（容器 ( (）；读 ) → 取最后存入的 ( 匹配成功，Pop（容器 (）；读 [ → Push（容器 ( [）；读 ] → 取最后存入的 [ 匹配成功，Pop（容器 (）；读 ) → 取最后存入的 ( 匹配成功，Pop（容器空）；遍历结束容器为空 → 配对成功。

括号匹配的 C++ 实现（使用标准库栈 `std::stack`）

代码

#include <stack>
#include <string>
#include <iostream>
using namespace std;

class BracketChecker {
public:
    bool check(const string& str);
};

bool BracketChecker::check(const string& str) {
    stack<char> stack;
    for (char c : str) {
        if (c == '(' || c == '[' || c == '{') {   // 左括号入栈
            stack.push(c);
        }
        else if (c == ')' || c == ']' || c == '}') {
            if (stack.empty()) return false;       // 栈空，匹配失败
            char top = stack.top();                // 取栈顶做匹配检测
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
            stack.pop();                           // 匹配成功，出栈
        }
    }
    return stack.empty();   // 最终栈空才算匹配成功
}

时间复杂度： $T(N)=O(N)$ （遍历序列一遍，每个字符常数次栈操作）。
测试用例与输出（1 表示匹配成功，0 表示失败）：()[]{}→1；([{}])→1；([)]→0；{[]}→1；(→0。

1.2 栈的定义、术语与抽象数据类型

栈（Stack / 堆栈）：具有一定操作约束的线性表，只在表尾一端（称为栈顶）做插入、删除。
- 插入数据：入栈（Push）；删除数据：出栈（Pop）。
- 关键特性：后进先出（Last In First Out, LIFO）。
基本操作：Push（入栈，将元素加到栈顶）、Pop（出栈，移除并返回栈顶元素）、Top（查看栈顶，返回栈顶元素但不移除）、isEmpty（判空，检查栈是否为空）。

栈相关术语

栈底（bottom）：栈的首部，即元素最早到达的部分。栈顶（top）：栈的尾部，即元素最晚到达的部分。
为保证先进后出/后进先出，元素的插入和删除都必须在栈顶进行：从栈顶删除元素称出栈/弹栈（pop）；在栈顶插入元素称进栈/压栈（push）。
取栈顶内容（top）：读取栈顶元素数据值但不修改栈。
空栈：栈中元素个数为零时。

抽象数据类型描述（ADT）

类型名称：栈（Stack）；数据对象集：一个有 0 个或多个元素的有穷线性表。

操作	前提条件	结果	时间复杂度
`initialize()`	无	创建空栈	$O(1)$
`isEmpty()`	无	返回栈是否为空（True/False）	$O(1)$
`top()`	栈非空	返回栈顶元素（不修改栈）	$O(1)$
`push(x)`	栈未满，元素 x 已知	x 入栈成为新栈顶	$O(1)$
`pop()`	栈非空	移除栈顶元素	$O(1)$
`destroy()`	无	释放栈内存空间	$O(n)$

注：抽象 ADT 表将 destroy() 记为 $O(n)$ ；具体实现页中，顺序栈析构按本页标为 $O(1)$ ，链式栈析构为 $O(N)$ 。

出栈序列辨析（课堂练习）

push(A), push(B), push(C), pop, pop, pop → 输出 CBA。
push(A), pop, push(B), push(C), pop, pop → 输出 ACB。
结论：若三字符按 A、B、C 顺序压栈，并非所有排列都是合法出栈序列；例如无法产生 CAB 序列。
原因（由 LIFO 一步推得）：C 先出栈意味着 A、B 此前都已入栈且 A 在 B 之下，故 A 不可能早于 B 出栈，因而 CAB 不是合法出栈序列。

1.3 顺序栈（seqStack）

定义：用连续空间存储栈中元素；栈底放在数组 0 下标位置，进栈和出栈总在同一端（栈顶）进行。这样存储的栈称顺序栈。
关键约定：
- bottom 总是 0，不需要记忆；
- 栈空标志：top = -1；
- 栈满标志：top = maxSize - 1；
- 为防止栈满，可用一个私有成员函数实现自动扩容。

类的定义（动态数组实现）

代码

template <class elemType>
class seqStack {
private:
    elemType *elem;       // 元素存储数组（动态数组首地址）
    int top_p;            // 栈顶指针（-1 表示空）
    int maxSize;          // 当前最大容量
    void doubleSpace();   // 扩容：空间翻倍（私有，用户不调用）
public:
    seqStack(int initSize = 10); // 构造
    ~seqStack();                 // 析构
    bool isEmpty() const;        // 判空
    void push(const elemType &x);// 入栈（自动扩容）
    elemType pop();              // 弹栈（需非空）
    elemType top() const;        // 取顶（需非空）
};

私有变量：指向动态数组首地址的指针 *elem、表示栈顶位置的整型 top_p、表示数组规模的整型 maxSize。doubleSpace() 用于扩展空间，无需用户调用，故为私有成员函数。

构造、析构

代码

template <class elemType>
seqStack<elemType>::seqStack(int initSize) {
    elem = new elemType[initSize];
    maxSize = initSize;
    top_p = -1;            // 初始化栈顶指针为 -1，表示栈为空
}

template <class elemType>
seqStack<elemType>::~seqStack() {
    delete[] elem;         // 释放分配的内存
}

构造函数 $T(N)=O(1)$ ，析构函数 $T(N)=O(1)$ （按本页所标）。

自动扩容 `doubleSpace()`

代码

template <class elemType>
void seqStack<elemType>::doubleSpace() {
    elemType *tmp = elem;                 // 保存旧数组
    elem = new elemType[2 * maxSize];     // 分配两倍容量的新数组
    for (int i = 0; i < maxSize; ++i)
        elem[i] = tmp[i];                 // 复制元素
    maxSize *= 2;                         // 更新容量
    delete[] tmp;                         // 释放旧数组
}

时间复杂度 $O(N)$ 。每次扩容把容量翻倍以减少扩容次数。
若不实现自动扩容，则需实现判满函数 isFull()。

入栈、出栈

代码

template <class elemType>
void seqStack<elemType>::push(const elemType &x) {
    if (top_p == maxSize - 1) doubleSpace();  // 栈满则扩容
    elem[++top_p] = x;                        // 元素入栈
}

template <class elemType>
elemType seqStack<elemType>::pop() {
    return elem[top_p--];                     // 返回并移除栈顶
}

push 中可能触发 doubleSpace()（单次 $O(N)$ ），但分摊到单次入栈后，入栈操作仍为 $O(1)$ ——这种分析方法称均摊法（均摊分析）。出栈操作 $O(1)$ 。

判空、取栈顶

代码

template <class elemType>
bool seqStack<elemType>::isEmpty() const {
    return top_p == -1;     // 栈顶指针为 -1 时栈空
}

template <class elemType>
elemType seqStack<elemType>::top() const {
    return elem[top_p];     // 返回栈顶元素
}

两者时间复杂度均为 $O(1)$ ；二者不修改成员变量，故用 const 修饰。

1.4 链式栈（linkStack）

定义：用不连续的空间和附加指针来存储元素及元素间关系；栈顶指针 top 指向栈顶结点，即单链表中的首结点。

类的定义（单链表实现）

代码

template <class elemType>
class linkStack {
private:
    struct node {
        elemType data;            // 数据
        node *next;               // 后继指针
        node(const elemType &x, node *N = NULL) { data = x; next = N; }
        node() : next(NULL) {}
        ~node() {}
    };
    node *top_p;              // 指向栈顶的指针
public:
    linkStack();
    ~linkStack();
    bool isEmpty() const;
    void push(const elemType &x);
    elemType pop();
    elemType top() const;
};

用单链表实现链式栈；结点类不会被用户使用，故设为私有的内嵌类。

构造、析构

代码

template <class elemType>
linkStack<elemType>::linkStack() {
    top_p = NULL;
}

template <class elemType>
linkStack<elemType>::~linkStack() {
    node *tmp;
    while (top_p != NULL) {       // 逐结点释放
        tmp = top_p;
        top_p = top_p->next;
        delete tmp;
    }
}

构造函数 $T(N)=O(1)$ ，析构函数 $T(N)=O(N)$ （需逐个释放结点）。

入栈、出栈、判空、取栈顶

代码

template <class elemType>
void linkStack<elemType>::push(const elemType &x) {
    top_p = new node(x, top_p);   // 一行完成：建结点、新结点指向原栈顶、top_p 指向新结点
}

template <class elemType>
elemType linkStack<elemType>::pop() {
    node *tmp = top_p;            // 临时指针指向栈顶
    elemType x = tmp->data;       // 取栈顶值
    top_p = top_p->next;          // 栈顶后移
    delete tmp;                   // 释放原栈顶空间
    return x;
}

template <class elemType>
bool linkStack<elemType>::isEmpty() const {
    return top_p == NULL;
}

template <class elemType>
elemType linkStack<elemType>::top() const {
    return top_p->data;
}

入栈、出栈、判空、取栈顶时间复杂度均为 $O(1)$ 。

1.5 栈的应用：表达式求值

三种表达式形式

目的：消除优先级和括号的歧义，方便计算机处理。对比：中缀 (1+2)*3 vs. 后缀 1 2 + 3 *。
中缀表达式：运算符在操作数中间，如 3 + 4 * 2；符合人类习惯，但不符合计算机处理逻辑。
后缀表达式（逆波兰式）：运算符在操作数后，如 3 4 2 * +；符合计算机处理逻辑，不需要括号运算符。
前缀表达式（波兰式）：运算符在操作数前，如 + 3 * 4 2。
转换示例：中缀 (3+4)*2 → 后缀 3 4 + 2 *；中缀 3 + 4 * 2 → 后缀 3 4 2 * +。运算数顺序不变，按运算优先级把运算符后移。
表达式计算的两方面工作：① 中缀式转换为后缀式；② 后缀式计算。（运算数顺序不变；按优先级调整运算符顺序，先输出优先级更高的；用栈存储"等待中"的运算符，并将当前运算符与栈内最后一个运算符比较。）

中缀式 → 后缀式（算法）

初始化一个空栈（保存运算符）和一个空输出队列。
从左到右扫描中缀表达式：
- 遇操作数：直接加入输出队列；
- 遇左括号 (：入栈；
- 遇右括号 )：弹出栈顶元素到输出队列，直到遇到左括号（左括号出栈但不输出）；
- 遇运算符：通常弹出栈顶优先级 ≥ 当前运算符的元素（到输出队列），再将当前运算符入栈；右结合运算符需例外处理，如本章 calc 中乘方 EXP 直接入栈。
扫描完成后，将栈中剩余运算符依次弹出到输出队列。

易错点：左括号 ( 在入栈时优先级最高（任何运算符都能压在它上面），但已在栈内时优先级最低（只有遇到对应右括号才弹出，普通运算符不会把它弹出）；括号本身不进入后缀式输出。
逐步示例 a * ( b + c ) / d → 后缀 a b c + * d /：a 输出 → * 入栈 → ( 入栈（优先级高于 *）→ b 输出 → + 入栈（在括号内）→ c 输出 → ) 触发弹栈到 ( 为止（弹出 +，括号不输出）→ / 与栈顶 * 比较（* 先入、优先级不低，弹出 *），/ 入栈 → d 输出 → 读完，弹出栈内剩余（/）。
跟踪示例：5*(7-2*3)+8/2 转换为后缀 5 7 2 3 * - * 8 2 / +。

后缀式计算（算法）

初始化一个空栈（保存操作数）。
从左到右扫描后缀表达式：遇操作数入栈；遇运算符弹出栈顶两个元素，计算后将结果入栈。
最终栈顶元素即为结果。

跟踪示例：后缀 5 7 2 3 * - * 8 2 / + 计算结果为 9。
逐步跟踪（运算数栈，自栈底到栈顶）：读 5 → [5]；读 7 → [5 7]；读 2 → [5 7 2]；读 3 → [5 7 2 3]；读 *（弹 2、3，23=6）→ [5 7 6]；读 -（弹 7、6，7-6=1）→ [5 1]；读 *（弹 5、1，51=5）→ [5]；读 8 → [5 8]；读 2 → [5 8 2]；读 /（弹 8、2，8/2=4）→ [5 4]；读 +（弹 5、4，5+4=9）→ [9]，栈顶 9 即为结果。
两步可合并：中缀转后缀与后缀计算这两个步骤可以合并为一次扫描完成。

表达式求值的 C++ 实现（`calc` 类）

token 枚举：enum token { OPAREN, ADD, SUB, MULTI, DIV, EXP, CPAREN, VALUE, EOL };，从左到右依次表示：开括号、加号、减号、乘号、除号、乘方、闭括号、运算数、行结束符。
结合 result 中 opStack.top() >= MULTI 的比较逻辑可知：枚举的声明顺序蕴含了运算符优先级比较关系（此优先级关系并非 s059 直接给出，而是由 s063 的 result() 代码反推得到）；EXP 分支直接入栈，使连续乘方按右结合处理。

代码

class calc {
    char *expression;     // 中缀表达式
    enum token { OPAREN, ADD, SUB, MULTI, DIV, EXP, CPAREN, VALUE, EOL };
    void BinaryOp(token op, seqStack<int> &dataStack); // 执行二元运算
    token getOp(int &value);                           // 取下一个符号/运算数
public:
    calc(const char *s) { expression = new char[strlen(s) + 1]; strcpy(expression, s); }
    ~calc() { delete[] expression; }
    int result();         // 计算结果
};

getOp(int &value)：扫描表达式直到取到一个运算符或运算数；先跳过空格；若是数字则连续读出并转为整型存入 value，返回 VALUE；否则用 switch 按字符返回对应 token；遇 '\0' 返回 EOL，遇非法字符报错退出。
BinaryOp(token op, dataStack)：从运算数栈弹出两个数 num2（右操作数，先弹）、num1（左操作数，后弹）；按 op 执行 + - * / ^（EXP 用 pow），结果压回栈。注意弹出顺序：先弹的是右操作数。
出错处理：两次出栈分别独立判空——第一次 pop（取右操作数 num2）前若 dataStack.isEmpty() 则报 " 缺右运算数！" 并 exit(1)；第二次 pop（取左操作数 num1）前若栈再次为空则报 " 缺左运算数！" 并 exit(1)，两条提示可区分缺失的是右操作数还是左操作数。

代码

int calc::result() {
    token lastOp, topOp = EOL;
    int result_value, CurrentValue;
    seqStack<token> opStack;   // 运算符栈
    seqStack<int> dataStack;   // 运算数栈
    char *str = expression;
    while ((lastOp = getOp(CurrentValue)) != EOL) {
        switch (lastOp) {
        case VALUE:  dataStack.push(CurrentValue); break;
        case OPAREN: opStack.push(OPAREN); break;
        case CPAREN:               // 闭括号：弹到开括号为止
            topOp = EOL;
            while (!opStack.isEmpty() && (topOp = opStack.pop()) != OPAREN)
                BinaryOp(topOp, dataStack);
            if (topOp != OPAREN) { cerr << " 缺左括号 !" << endl; return 0; }
            break;
        case EXP:    opStack.push(EXP); break;            // 乘方直接入栈
        case MULTI: case DIV:      // 乘除：弹出栈顶 >= MULTI 的，再入栈
            while (!opStack.isEmpty() && opStack.top() >= MULTI)
                BinaryOp(opStack.pop(), dataStack);
            opStack.push(lastOp);
            break;
        case ADD: case SUB:        // 加减：弹到空或遇开括号，再入栈
            while (!opStack.isEmpty() && opStack.top() != OPAREN)
                BinaryOp(opStack.pop(), dataStack);
            opStack.push(lastOp);
            break;
        }
    }
    while (!opStack.isEmpty()) {        // 弹出剩余运算符
        topOp = opStack.pop();
        if (topOp == OPAREN) { cout << " 缺右括号 "; return 0; }
        BinaryOp(topOp, dataStack);
    }
    if (dataStack.isEmpty()) { cout << " 无结果 \n"; return 0; }
    result_value = dataStack.pop();
    if (!dataStack.isEmpty()) { cout << " 缺操作符 "; return 0; }
    expression = str;
    return result_value;
}

getOp 和 BinaryOp 被 result 调用，用户无需调用，故设为 calc 类的私有成员函数。
测试与理论输出：3*(1+1)^2^3/(4 - 2) - 10 → 374；3*6/9+5 → 7；6/3*4+1 → 9。

1.6 栈小结

栈是在线性表基础上限制插入、删除位置（只能在同一端点进行）的一种操作受限的线性表。
栈在计算机系统中非常重要：除符号匹配、表达式计算外，系统在函数调用、递归中都以栈结构为基础。
栈的常见操作：进栈、出栈、求栈顶元素、判栈空、判栈满等。
物理实现可用顺序和链式两种存储方式；鉴于操作都在一端进行，顺序存储是栈最常使用的存储方式。

二、队列（Queue）

2.1 队列的引入与定义

生活原型：银行叫号系统，顾客按顺序排队办理业务，要"高效管理先来先服务的请求"。需求：动态增删（顾客随时加入队尾，柜员处理队头请求）、顺序维护（先到的顾客优先被服务）。
更多应用场景：操作系统打印任务队列（按提交顺序执行，避免资源竞争）、电商秒杀请求缓冲（异步处理、防止服务器崩溃）、游戏玩家指令队列（按序执行、避免操作冲突）。
队列（Queue）定义：具有一定操作约束的线性表，只能在一端插入，而在另一端删除。
- 数据插入：入队（enQueue）；数据删除：出队（deQueue）。
- 关键特性：先进先出（First In First Out, FIFO）。

抽象数据类型描述（ADT）

类型名称：队列（Queue）；数据对象集：一个有 0 个或多个元素的有穷线性表。

操作	前提	结果
`initialize`	无	分配空间及初始化
`isEmpty`	无	返回是否为空
`getHead`	队列非空	返回队首元素
`enQueue`	队列非满，有数据	数据加入队尾
`deQueue`	队列非空	移除队首元素
`destroy`	无	释放队列空间

2.2 顺序队列与顺序循环队列（seqQueue）

顺序队列定义：用一组连续的空间存储队列中的元素及元素间关系。元素个数最多 maxSize 个，下标范围 0 到 maxSize-1；用队首指针 Front 指示队首元素，队尾指针 Rear 指示队尾元素，便于进队/出队。

顺序队列的三种组织方式

组织方式	特点	问题/复杂度
队头位置固定	队头固定在下标 0；用一个变量指出队尾位置；队列空时队尾位置为 -1	缺点：出队会引起大量数据移动
队头位置不固定	用 front、rear 两个指针；front 随出队后移	所有操作都是 $O(1)$ ，但浪费空间
循环队列	在"队头不固定"基础上加循环特征，复用空间	解决空间浪费问题（详见下文）

顺序循环队列

核心思想：为防止队列后移造成的空间浪费，给数组附加一个循环特征，称顺序循环队列；指针移动用取模实现。
- 入队操作：rear = (rear + 1) % MaxSize; elem[rear] = x;
- 出队操作：front = (front + 1) % MaxSize;
空/满判定的难题：创建队列时令 front = rear = 0 表示空；多次进出队后 front、rear 都不在 0。仅靠 front == rear 无法区分队空与队满——出队变空时 front == rear，入队变满（rear 绕一圈追上 front）时也满足 front == rear，两者混淆。
解决方案："牺牲"一个单元：规定 front 指向的单元不存储队列元素，只起标志作用，表示其后面一个才是队头元素。
- 队空标志：rear == front。
- 队满标志：(rear + 1) % maxSize == front。

类的定义

代码

template <class elemType>
class seqQueue {
private:
    elemType *elem;
    int maxSize;
    int front, rear;
    void doubleSpace();
public:
    seqQueue(int size = 10);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &x);
    elemType deQueue();
    elemType getHead() const;
};

定义时无法预知数组大小，故采用动态数组；用 doubleSpace() 在队满时扩充。

构造、析构、判空、出队、取队首

代码

template <class elemType>
seqQueue<elemType>::seqQueue(int size) {
    elem = new elemType[size];
    maxSize = size;
    front = rear = 0;                 // 初始化头尾指针
}

template <class elemType>
seqQueue<elemType>::~seqQueue() { delete[] elem; }

template <class elemType>
bool seqQueue<elemType>::isEmpty() const { return front == rear; }

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
    front = (front + 1) % maxSize;    // 头指针前移（先移再取，因 front 单元不存元素）
    return elem[front];
}

template <class elemType>
elemType seqQueue<elemType>::getHead() const {
    return elem[(front + 1) % maxSize];   // 队首是 front 的下一个单元
}

析构函数时间复杂度 $O(N)$ ；构造、判空、出队、取队首均为 $O(1)$ 。

进队与 `doubleSpace()`

代码

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
    if ((rear + 1) % maxSize == front) doubleSpace();  // 队满则扩容
    rear = (rear + 1) % maxSize;
    elem[rear] = x;
}

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
    elemType *tmp = elem;
    elem = new elemType[2 * maxSize];
    for (int i = 1; i < maxSize; ++i)
        elem[i] = tmp[(front + i) % maxSize];  // 按循环顺序复制到新数组
    front = 0;                                 // 重置头指针
    rear = maxSize - 1;                        // 重置尾指针
    maxSize *= 2;
    delete[] tmp;
}

用 (rear + 1) % MaxSize == front 判满，若满则自动扩容。doubleSpace() 时间复杂度 $O(N)$ ；按“牺牲一个单元”的约定，扩容时只复制旧队列中的 maxSize - 1 个有效元素；均摊到每次进队后，进队操作仍为 $O(1)$ 。

2.3 链式队列（linkQueue）

定义：队列也可用链表实现；由于操作只在两端进行，不需双链表，单链表就足够。队首指针 front 指向队首结点、队尾指针 rear 指向队尾结点。
队空条件 front == rear == NULL；链式队列不存在队满情况。

类的定义

代码

template <class elemType>
class linkQueue {
private:
    struct node {
        elemType data;
        node *next;
        node(const elemType &x, node *N = NULL) : data(x), next(N) {}
        node() : next(NULL) {}
        ~node() {}
    };
    node *front, *rear;            // 头尾指针
public:
    linkQueue();
    ~linkQueue();
    bool isEmpty() const;
    void enQueue(const elemType &x);
    elemType deQueue();
    elemType getHead() const;
};

构造、析构

代码

template <class elemType>
linkQueue<elemType>::linkQueue() { front = rear = NULL; }

template <class elemType>
linkQueue<elemType>::~linkQueue() {
    node *tmp;
    while (front != NULL) {        // 沿后继指针逐个释放
        tmp = front;
        front = front->next;
        delete tmp;
    }
}

构造函数 $O(1)$ ；析构函数主体是 while 循环逐个释放结点，时间复杂度 $O(N)$ 。

判空、取队首、入队、出队

代码

template <class elemType>
bool linkQueue<elemType>::isEmpty() const { return front == NULL; }

template <class elemType>
elemType linkQueue<elemType>::getHead() const { return front->data; }

template <class elemType>
void linkQueue<elemType>::enQueue(const elemType &x) {
    if (rear == NULL) {                       // 入队前为空队列
        front = rear = new node(x);
    } else {
        rear = rear->next = new node(x);      // 接到队尾并更新 rear
    }
}

template <class elemType>
elemType linkQueue<elemType>::deQueue() {
    node *tmp = front;
    elemType value = front->data;
    front = front->next;
    if (front == NULL) rear = NULL;           // 出队后变空，需同步置空 rear
    delete tmp;
    return value;
}

判空、取队首、入队、出队四个函数时间复杂度都是 $O(1)$ 。
边界处理要点：入队时若 rear == NULL（空队）需同时设 front 和 rear；出队后若 front == NULL（队空）需同步把 rear 置 NULL。

2.4 优先队列（Priority Queue）

定义：进入队列的元素带优先级（用一个优先数表示，一般优先数越小优先级越高）；出队时优先级越高越早出队，优先级越低越晚出队，优先级相同者按先进先出处理。这种队列称优先队列。
存储方式：顺序存储、链式存储。

顺序优先队列（用数组存放）

两种存放策略：

策略一（进队按时间顺序存放，出队找优先级最高者）：
- 进队：按下标由小到大直接放队尾， $O(1)$ 。
- 出队：从所有元素中找优先级最高者并删除；为避免整队后移浪费空间，出队时把队列最后一个元素移到出队元素所在位置，使队列始终从 0 下标连续到某下标、中间无空隙，故不需要循环技术；查找最高优先级元素 $O(n)$ 。
- 令 rear 指向实际队尾元素的后一单元：队空 rear = 0，队满 rear = maxSize。
- 若严格要求“同优先级先进先出”，末元素填空会破坏同级元素的到达顺序，需要额外记录到达次序或改用稳定删除策略。
策略二（进队按优先级顺序存放，出队取队首）：
- 元素按优先数由小到大排列。
- 进队：先找到合适插入位置、移动后面的元素再插入， $O(n)$ 。
- 出队：删队首（0 下标）即可，为避免后面元素移动可采用顺序循环队列， $O(1)$ 。
- 令 rear 指向实际队尾后一单元：队空 rear == front，队满 (rear + 1) % maxSize == front。

链式优先队列

策略一：进队时直接将元素插入队尾 $O(1)$ ；出队时从所有元素中找优先级最高者删除。
策略二：单链表中结点按元素优先级递减（即优先数增大）排成有序链表，优先级最高的结点是首结点。
- 出队即删首结点， $O(1)$ 。
- 进队需按优先级找到合适插入位置再插入， $O(n)$ ，但不会引起队列中原有元素在内存中移动（相对顺序存储的优势）。

2.5 队列的应用：排队系统模拟

模拟（simulation）：用计算机仿真现实系统的操作并收集统计数据，是计算机的重要应用。
模拟的优点：① 不需要真实顾客就能得到统计信息；② 计算机速度快，模拟比真实实现快很多；③ 模拟结果可以简单地重现。（例：模拟有 K 个出纳员的银行系统，确定满足合理服务时间的最小 K 值。）
事件驱动模拟：将事件按发生时间排队，一个事件处理结束后，直接把时间拨到下一事件的发生时间，处理下一事件。
- 两类核心事件：到达事件（顾客到达时间间隔服从 $[a,b]$ 均匀分布）、离开事件（服务时间服从 $[c,d]$ 均匀分布）。
- 统计指标：平均等待时间、队列长度、员工利用率。

单服务台排队系统的实现

只需使用一个队列；整个模拟由三步组成：
1. 生成所有顾客到达事件，按到达时间排成一个队列；
2. 服务员一旦有空，就为队头元素服务，提供服务前先检查该顾客等待了多少时间并记入累计值；
3. 所有顾客服务完后，返回累计值除以顾客数。

代码

class simulator {
    int arrivalLow;      // 到达间隔时间下限
    int arrivalHigh;     // 到达间隔时间上限
    int serviceTimeLow;  // 服务时间下限
    int serviceTimeHigh; // 服务时间上限
    int customNum;       // 模拟的顾客数
public:
    simulator();             // 接受用户输入参数
    int avgWaitTime() const; // 执行模拟并给出平均等待时间
};

int simulator::avgWaitTime() const {
    int currentTime = 0, totalWaitTime = 0, eventTime;
    linkQueue<int> customerQueue;          // 顾客到达事件队列
    for (int i = 0; i < customNum; ++i) {  // 生成所有到达事件
        currentTime += arrivalLow + (arrivalHigh - arrivalLow) * (double)rand() / RAND_MAX;
        customerQueue.enQueue(currentTime);
    }
    currentTime = 0;
    while (!customerQueue.isEmpty()) {     // 处理所有到达事件
        eventTime = customerQueue.deQueue();
        if (eventTime < currentTime)       // 顾客到达时服务台仍忙 → 需等待
            totalWaitTime += currentTime - eventTime;
        else currentTime = eventTime;      // 服务台空闲 → 时钟拨到到达时刻
        currentTime += serviceTimeLow + (serviceTimeHigh - serviceTimeLow) * (double)rand() / RAND_MAX;
    }
    return totalWaitTime / customNum;
}

构造函数读入到达间隔上下界、服务时间上下界、顾客数，并 srand(time(NULL)) 初始化随机数发生器。
使用伪随机数 rand()（生成 0 到 RAND_MAX 的随机数）配合均匀分布生成间隔/服务时间。
运行示例：到达间隔 0 5、服务时间 1 4、顾客数 1000 → 平均等待时间约 25（每次结果可能不同，因含随机数）。

2.6 单调队列

定义：一个满足单调性质的双向队列，队内元素排列顺序满足单调递增或单调递减。
维护规则：如果新入队的元素破坏了单调性，就弹出队内元素，直到满足单调性，再进行入队操作。
功能：对于一个序列，求出每 k 个连续的数中的最大值和最小值（滑动窗口最值）。

课堂练习解答（滑动窗口最小值）

题目（洛谷 P1886 滑动窗口）：给定长为 n 的序列 a 和一个大小为 k 的窗口；窗口从最左端开始，每次向右滑动一个单位，求每次滑动后窗口内的最大值和最小值。
输入格式：第一行两个正整数 n、k；第二行 n 个整数表示序列 a。输出格式：共两行，第一行依次输出每个窗口的最小值，第二行依次输出每个窗口的最大值。
样例：输入 8 3 / 1 3 -1 -3 5 3 6 7；输出（最小值）-1 -3 -3 -3 3 3、（最大值）3 3 5 5 6 7。逐窗口（含值）：[1,3,-1]→ -1/3；[3,-1,-3]→ -3/3；[-1,-3,5]→ -3/5；[-3,5,3]→ -3/5；[5,3,6]→ 3/6；[3,6,7]→ 3/7。
题源：洛谷 P1886（滑动窗口），链接 https://www.luogu.com.cn/problem/P1886。
用数组模拟单调队列，q 中存储的是下标（索引）；head、tail 为队头/队尾指针。

代码

const int MAXN = 1000005;
int n, k;          // n：数组长度；k：滑动窗口大小
int a[MAXN];       // 输入数组
int ans[MAXN];     // 每个窗口的最小值
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int head = 1, tail = 0, q[MAXN] = {0};         // 单调队列（存下标）
    for (int i = 1; i <= n; ++i) {
        while (head <= tail && a[q[tail]] >= a[i]) --tail; // 维护单调性：弹出 >= 当前值的队尾
        q[++tail] = i;                                     // 入队，存索引
        while (q[head] <= i - k) ++head;                   // 队首"过时"则出队
        if (i >= k) ans[i] = a[q[head]];                   // 窗口最小值 = 队首
    }
    for (int i = k; i <= n; ++i) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

要点：求最小值时，队列对应值单调递增，故队首始终是当前窗口最小值；队尾弹出所有 >= a[i] 的元素以保持单调性；队首下标 <= i - k 表示已滑出窗口，需出队。

2.7 队列小结

队列是限制了插入、删除操作位置的另一种线性表，元素的插入、删除分别在表的两端进行。
除日常生活的实际队列外，计算机操作系统中许多对象的管理都用到队列（如打印队列、进程队列等），是一种重要的数据结构。
队列常见操作：进队、出队、求队首元素、判空、判满等。
队列的顺序循环存储（进队按动态扩容作均摊分析）和链式存储的常见操作时间复杂度都是 $O(1)$ ；考虑到链式存储每个结点额外的空间开销，顺序循环队列是最常用的存储结构。
优先队列不再按先进先出，优先级高者先出队；无论顺序还是链式优先队列，其进队、出队操作的时间复杂度为 $O(1)$ 、 $O(n)$ 或者 $O(n)$ 、 $O(1)$ （两端各有一端 $O(1)$ 、另一端 $O(n)$ ）。
后面章节讨论二叉树后，用二叉树作工具、以堆的方式存储优先队列时，时间复杂度能降到 $O(\log_2 n)$ 。

第三章 栈和队列

一、栈（Stack）

1.1 括号匹配：问题引入与算法思想

括号匹配算法（容器操作抽象）

括号匹配的 C++ 实现（使用标准库栈 std::stack）

1.2 栈的定义、术语与抽象数据类型

栈相关术语

抽象数据类型描述（ADT）

出栈序列辨析（课堂练习）

1.3 顺序栈（seqStack）

类的定义（动态数组实现）

构造、析构

自动扩容 doubleSpace()

入栈、出栈

判空、取栈顶

1.4 链式栈（linkStack）

类的定义（单链表实现）

构造、析构

入栈、出栈、判空、取栈顶

1.5 栈的应用：表达式求值

三种表达式形式

中缀式 → 后缀式（算法）

后缀式计算（算法）

表达式求值的 C++ 实现（calc 类）

1.6 栈小结

二、队列（Queue）

2.1 队列的引入与定义

抽象数据类型描述（ADT）

2.2 顺序队列与顺序循环队列（seqQueue）

顺序队列的三种组织方式

顺序循环队列

类的定义

构造、析构、判空、出队、取队首

进队与 doubleSpace()

2.3 链式队列（linkQueue）

类的定义

构造、析构

判空、取队首、入队、出队

2.4 优先队列（Priority Queue）

顺序优先队列（用数组存放）

链式优先队列

2.5 队列的应用：排队系统模拟

单服务台排队系统的实现

2.6 单调队列

课堂练习解答（滑动窗口最小值）

2.7 队列小结

第三章栈和队列

括号匹配的 C++ 实现（使用标准库栈 `std::stack`）

自动扩容 `doubleSpace()`

表达式求值的 C++ 实现（`calc` 类）

进队与 `doubleSpace()`