链表：单链表、双向链表、循环链表

一、核心概念

核心概念

1. 单链表

• 定义：由多个节点组成，每个节点包含「数据域」（存储数据）和「指针域」（存储下一个节点的地址），最后一个节点的指针域为 nullptr（空指针）。
• 特点：只能从表头向表尾单向遍历，插入/删除时只需修改指针指向，无需移动大量元素。
• 结构示意：
  头节点 → 节点1 → 节点2 → ... → 尾节点 → nullptr

2. 双向链表

• 定义：每个节点除数据域外，包含两个指针域：「前驱指针」（指向前一个节点）和「后继指针」（指向后一个节点）。
• 特点：可双向遍历（从头到尾或从尾到头），插入/删除时需同时维护两个指针，但操作更灵活。
• 结构示意：
  nullptr ← 节点1 ↔ 节点2 ↔ ... ↔ 尾节点 → nullptr

3. 循环链表

• 定义：链表首尾相连，尾节点的指针域指向头节点（单循环链表），或头节点的前驱指针指向尾节点（双循环链表）。
• 特点：可循环遍历，适合模拟「环形」场景（如约瑟夫问题）。
• 结构示意：
  头节点 → 节点1 → ... → 尾节点 → 头节点（形成环）

二、实战案例（C++ 实现）

实战案例

1. 单链表基础操作（创建、插入、删除、遍历）

c++

#include <iostream>
using namespace std;

// 定义节点结构
struct Node {
    int data;       // 数据域
    Node* next;     // 指针域（指向下一节点）
    Node(int x) : data(x), next(nullptr) {} // 构造函数
};

// 单链表类
class LinkedList {
private:
    Node* head; // 头指针
public:
    LinkedList() : head(nullptr) {}

    // 尾插法创建节点
    void push_back(int x) {
        Node* newNode = new Node(x);
        if (head == nullptr) { // 空链表时，新节点为头节点
            head = newNode;
            return;
        }
        // 遍历到尾节点
        Node* cur = head;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = newNode; // 尾节点指向新节点
    }

    // 在第pos个位置插入（pos从1开始）
    void insert(int pos, int x) {
        if (pos < 1) {
            cout << "位置无效" << endl;
            return;
        }
        Node* newNode = new Node(x);
        if (pos == 1) { // 插入到头节点前
            newNode->next = head;
            head = newNode;
            return;
        }
        // 找到第pos-1个节点
        Node* cur = head;
        for (int i = 1; i < pos - 1; i++) {
            if (cur == nullptr) { // 位置超出链表长度
                cout << "位置无效" << endl;
                return;
            }
            cur = cur->next;
        }
        newNode->next = cur->next; // 新节点指向原pos节点
        cur->next = newNode;       // pos-1节点指向新节点
    }

    // 删除第pos个节点
    void remove(int pos) {
        if (head == nullptr || pos < 1) {
            cout << "删除失败" << endl;
            return;
        }
        Node* temp;
        if (pos == 1) { // 删除头节点
            temp = head;
            head = head->next;
            delete temp;
            return;
        }
        // 找到第pos-1个节点
        Node* cur = head;
        for (int i = 1; i < pos - 1; i++) {
            if (cur == nullptr || cur->next == nullptr) {
                cout << "删除失败" << endl;
                return;
            }
            cur = cur->next;
        }
        temp = cur->next;          // 待删除节点
        cur->next = temp->next;    // 跳过待删除节点
        delete temp;               // 释放内存
    }

    // 遍历链表
    void print() {
        Node* cur = head;
        while (cur != nullptr) {
            cout << cur->data << " ";
            cur = cur->next;
        }
        cout << endl;
    }

    // 析构函数：释放所有节点
    ~LinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

// 测试
int main() {
    LinkedList list;
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.print(); // 输出：1 2 3

    list.insert(2, 4);
    list.print(); // 输出：1 4 2 3

    list.remove(3);
    list.print(); // 输出：1 4 3
    return 0;
}

2. 循环链表应用：约瑟夫问题

问题：n个人围成一圈，从第1个人开始报数，报到k的人出列，剩下的人继续从1报数，直到最后一人。输出出列顺序。

c++

#include <iostream>
using namespace std;

struct Node {
    int num; // 编号
    Node* next;
    Node(int x) : num(x), next(nullptr) {}
};

// 创建循环链表（n个节点）
Node* createCircle(int n) {
    Node* head = new Node(1);
    Node* cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new Node(i);
        cur = cur->next;
    }
    cur->next = head; // 尾节点指向头节点，形成环
    return head;
}

// 解决约瑟夫问题
void josephus(int n, int k) {
    Node* head = createCircle(n);
    Node* cur = head;

    // 只剩一个节点时停止
    while (cur->next != cur) {
        // 找到第k-1个节点（因为要删除第k个）
        for (int i = 1; i < k - 1; i++) {
            cur = cur->next;
        }
        // 输出出列节点编号
        Node* out = cur->next;
        cout << out->num << " ";
        // 删除出列节点
        cur->next = out->next;
        delete out;
        // 从下一个节点继续报数
        cur = cur->next;
    }
    // 输出最后剩下的节点
    cout << cur->num << endl;
    delete cur;
}

int main() {
    int n = 5, k = 2;
    josephus(n, k); // 输出：2 4 1 5 3
    return 0;
}

3. 双向链表（简化实现）

c++

#include <iostream>
using namespace std;

struct DNode {
    int data;
    DNode* prev; // 前驱指针
    DNode* next; // 后继指针
    DNode(int x) : data(x), prev(nullptr), next(nullptr) {}
};

// 在节点p后插入新节点
void insertAfter(DNode* p, int x) {
    if (p == nullptr) return;
    DNode* newNode = new DNode(x);
    newNode->prev = p;          // 新节点前驱指向p
    newNode->next = p->next;    // 新节点后继指向p的原后继
    if (p->next != nullptr) {   // 若p不是尾节点，更新原后继的前驱
        p->next->prev = newNode;
    }
    p->next = newNode;          // p的后继指向新节点
}

// 遍历（从 head 到 tail）
void printForward(DNode* head) {
    DNode* cur = head;
    while (cur != nullptr) {
        cout << cur->data << " ";
        cur = cur->next;
    }
    cout << endl;
}

int main() {
    DNode* head = new DNode(1);
    insertAfter(head, 2);
    insertAfter(head->next, 3);
    printForward(head); // 输出：1 2 3
    return 0;
}

三、信奥赛应用场景

信奥赛应用场景

1. 模拟类问题：如约瑟夫问题（循环链表）、多项式相加（单链表，每个节点存系数和指数）。
2. 动态数据处理：需要频繁插入/删除（如链表实现队列、栈，比数组更灵活）。
3. 内存敏感场景：链表无需预先分配连续内存，适合数据量不确定的情况。
4. 链表变形题：如判断链表是否有环、求环的入口（循环链表相关）、链表反转等。

四、避坑指南

避坑指南

1. 指针初始化：未初始化的指针可能指向随机内存（野指针），操作前务必赋值（如 nullptr）。

c++

Node* p; // 危险！应改为 Node* p = nullptr;

2. 边界条件处理：

   • 单链表插入/删除头节点时，需单独处理（头指针会变）。
   • 循环链表遍历终止条件是「回到头节点」，而非 nullptr，避免死循环。

3. 内存泄漏：删除节点后必须用 delete 释放内存（竞赛中虽不严格扣分，但养成好习惯）。

4. 双向链表指针同步：插入/删除时，必须同时更新「前驱指针」和「后继指针」，否则链表断裂。

5. 静态链表替代：普及用组常用「数组模拟链表」（静态链表）避免指针操作风险，用数组下标模拟指针：

c++

struct Node { int data; int next; };
Node nodes[1000]; // 预分配节点数组
int head = -1;    // -1 表示空指针

重要

• 单链表：结构简单，适合单向遍历，插入删除效率高（O(1)，已知前驱时）。
• 双向链表：支持双向遍历，操作灵活但指针维护复杂。
• 循环链表：适合环形场景，需注意遍历终止条件。

栈

一、核心概念

栈

栈（Stack）是一种后进先出（LIFO, Last In First Out） 的线性数据结构，只能在一端（称为栈顶，Top）进行插入和删除操作，另一端称为栈底（Bottom）。

核心概念

2. 基本操作

• 压栈（Push）：向栈顶添加元素
• 出栈（Pop）：从栈顶移除元素
• 取栈顶元素（Top）：获取栈顶元素但不删除
• 判空（Empty）：判断栈是否为空
• 求大小（Size）：获取栈中元素个数

3. 存储结构

• 顺序栈：用数组实现，需预先分配内存
• 链式栈：用链表实现，动态分配内存，无固定大小限制

4. 结构示意图

栈底 ← 元素1 ← 元素2 ← 元素3（栈顶）
                ↑
              操作端

二、实战案例（C++ 实现）

实战案例

1. 顺序栈实现

c++

#include <iostream>
using namespace std;

const int MAX_SIZE = 1000; // 栈的最大容量

class Stack {
private:
    int data[MAX_SIZE]; // 存储元素的数组
    int top;            // 栈顶指针（指向栈顶元素的位置）
public:
    // 构造函数：初始化空栈
    Stack() : top(-1) {}
    
    // 压栈操作
    void push(int x) {
        if (top == MAX_SIZE - 1) {
            cout << "栈溢出！" << endl;
            return;
        }
        data[++top] = x; // 先移动栈顶指针，再存入元素
    }
    
    // 出栈操作
    void pop() {
        if (isEmpty()) {
            cout << "栈为空，无法出栈！" << endl;
            return;
        }
        top--; // 只需移动栈顶指针即可
    }
    
    // 获取栈顶元素
    int getTop() {
        if (isEmpty()) {
            cout << "栈为空！" << endl;
            return -1; // 实际应用中可抛出异常
        }
        return data[top];
    }
    
    // 判断栈是否为空
    bool isEmpty() {
        return top == -1;
    }
    
    // 获取栈的大小
    int size() {
        return top + 1;
    }
};

// 测试
int main() {
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    cout << "栈顶元素：" << s.getTop() << endl; // 输出：3
    cout << "栈大小：" << s.size() << endl;      // 输出：3
    
    s.pop();
    cout << "出栈后栈顶元素：" << s.getTop() << endl; // 输出：2
    
    while (!s.isEmpty()) {
        s.pop();
    }
    cout << "清空栈后是否为空：" << (s.isEmpty() ? "是" : "否") << endl; // 输出：是
    
    return 0;
}

2. 链式栈实现

c++

#include <iostream>
using namespace std;

// 节点结构
struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

class LinkStack {
private:
    Node* top; // 栈顶指针（指向栈顶节点）
    int len;   // 栈的长度
public:
    // 构造函数：初始化空栈
    LinkStack() : top(nullptr), len(0) {}
    
    // 压栈操作
    void push(int x) {
        Node* newNode = new Node(x);
        newNode->next = top; // 新节点指向原栈顶
        top = newNode;       // 更新栈顶指针
        len++;
    }
    
    // 出栈操作
    void pop() {
        if (isEmpty()) {
            cout << "栈为空，无法出栈！" << endl;
            return;
        }
        Node* temp = top;
        top = top->next; // 栈顶指针下移
        delete temp;     // 释放原栈顶节点内存
        len--;
    }
    
    // 获取栈顶元素
    int getTop() {
        if (isEmpty()) {
            cout << "栈为空！" << endl;
            return -1;
        }
        return top->data;
    }
    
    // 判断栈是否为空
    bool isEmpty() {
        return top == nullptr;
    }
    
    // 获取栈的大小
    int size() {
        return len;
    }
    
    // 析构函数：释放所有节点
    ~LinkStack() {
        while (top != nullptr) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }
};

// 测试
int main() {
    LinkStack s;
    s.push(10);
    s.push(20);
    s.push(30);
    
    cout << "栈顶元素：" << s.getTop() << endl; // 输出：30
    cout << "栈大小：" << s.size() << endl;      // 输出：3
    
    s.pop();
    cout << "出栈后栈顶元素：" << s.getTop() << endl; // 输出：20
    
    return 0;
}

3. 栈的典型应用：括号匹配

c++

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

// 判断括号是否匹配
bool isMatch(string s) {
    Stack st; // 使用前面实现的顺序栈
    
    for (char c : s) {
        // 左括号入栈
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        }
        // 右括号判断匹配
        else {
            if (st.isEmpty()) return false; // 右括号多了
            
            char top = st.getTop();
            st.pop();
            
            // 判断是否匹配
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    // 栈为空说明所有括号都匹配
    return st.isEmpty();
}

int main() {
    string s1 = "()[]{}";
    string s2 = "([)]";
    string s3 = "({[]})";
    
    cout << s1 << " 是否匹配：" << (isMatch(s1) ? "是" : "否") << endl; // 是
    cout << s2 << " 是否匹配：" << (isMatch(s2) ? "是" : "否") << endl; // 否
    cout << s3 << " 是否匹配：" << (isMatch(s3) ? "是" : "否") << endl; // 是
    
    return 0;
}

4. 栈的典型应用：表达式求值（后缀表达式）

c++

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

// 计算后缀表达式的值
int calculatePostfix(string expr) {
    Stack st; // 使用前面实现的顺序栈
    
    for (char c : expr) {
        if (isdigit(c)) {
            // 数字入栈
            st.push(c - '0'); // 字符转数字
        } else {
            // 运算符：弹出两个数计算后入栈
            int b = st.getTop(); st.pop(); // 注意顺序：后出栈的是第一个操作数
            int a = st.getTop(); st.pop();
            int res;
            
            switch (c) {
                case '+': res = a + b; break;
                case '-': res = a - b; break;
                case '*': res = a * b; break;
                case '/': res = a / b; break;
                default: cout << "无效运算符！" << endl; return -1;
            }
            st.push(res);
        }
    }
    
    return st.getTop();
}

int main() {
    string expr = "34+5*"; // 等价于 (3+4)*5
    cout << "后缀表达式 " << expr << " 的结果是：" << calculatePostfix(expr) << endl; // 35
    
    return 0;
}

三、信奥赛应用场景

信奥赛应用场景

1. 括号匹配问题：判断表达式中的括号是否合法配对
2. 表达式求值：中缀表达式转后缀表达式并计算结果
3. 深度优先搜索（DFS）：用栈模拟递归过程（避免递归栈溢出）
4. 单调栈问题：解决"下一个更大元素"、"直方图最大矩形面积"等问题
5. 迷宫问题：记录路径并实现回溯
6. 进制转换：将十进制数转换为其他进制（除基取余法）

四、避坑指南

避坑指南

1. 栈溢出处理：使用顺序栈时，必须先判断栈是否已满再进行压栈操作

c++

// 错误示例
void push(int x) {
    data[++top] = x; // 未判断是否溢出
}

// 正确示例
void push(int x) {
    if (top == MAX_SIZE - 1) {
        // 处理溢出（提示错误或动态扩容）
        return;
    }
    data[++top] = x;
}

2. 空栈操作防护：出栈和取栈顶元素前必须判断栈是否为空

c++

// 错误示例
int getTop() {
    return data[top]; // 栈为空时会访问非法内存
}

// 正确示例
int getTop() {
    if (isEmpty()) {
        // 处理空栈情况
        return -1;
    }
    return data[top];
}

3. 链式栈内存管理：出栈时必须释放节点内存，避免内存泄漏

c++

void pop() {
    if (isEmpty()) return;
    Node* temp = top;
    top = top->next;
    delete temp; // 关键：释放内存
}

4. 操作顺序注意：后缀表达式求值时，注意弹出元素的顺序（先出栈的是第二个操作数）

c++

// 错误：顺序颠倒
int a = st.getTop(); st.pop();
int b = st.getTop(); st.pop();
int res = a - b; // 实际应该是 b - a

5. 选择合适的实现方式：
   • 数据量固定且已知：优先用顺序栈（效率高）
   • 数据量不确定或可能很大：用链式栈（避免溢出）

重要

• 核心特性：栈是LIFO结构，仅允许在栈顶操作，插入和删除效率为O(1)
• 实现方式：顺序栈（数组）适合固定大小场景，链式栈（链表）适合动态大小场景
• 关键操作：压栈、出栈、取栈顶元素，均需注意边界条件（空栈、满栈）
• 应用核心：利用"后进先出"特性解决具有回溯性的问题（如括号匹配、DFS、表达式求值等）

队列

一、核心概念

队列的定义

队列（Queue）是一种先进先出（FIFO, First In First Out） 的线性数据结构，元素只能从一端（队尾，Rear）插入，从另一端（队头，Front）删除，类似现实中排队的场景。

核心概念

2. 基本操作

• 入队（Enqueue）：向队尾添加元素
• 出队（Dequeue）：从队头移除元素
• 取队头元素（Front）：获取队头元素但不删除
• 判空（Empty）：判断队列是否为空
• 求大小（Size）：获取队列中元素个数

3. 存储结构

• 顺序队列：用数组实现，需处理"假溢出"问题
• 循环队列：顺序队列的优化，将数组首尾相连形成环形
• 链式队列：用链表实现，动态分配内存，无固定大小限制

4. 结构示意图

队头 → 元素1 → 元素2 → 元素3 → 队尾
  ↑                           ↑
出队端                       入队端

二、实战案例（C++ 实现）

实战案例

1. 循环队列实现（解决顺序队列假溢出问题）

c++

#include <iostream>
using namespace std;

const int MAX_SIZE = 1000; // 队列最大容量

class CircularQueue {
private:
    int data[MAX_SIZE];
    int front; // 队头指针（指向队头元素）
    int rear;  // 队尾指针（指向队尾元素的下一个位置）
    int size;  // 当前元素个数
public:
    // 构造函数：初始化空队列
    CircularQueue() : front(0), rear(0), size(0) {}
    
    // 入队操作
    void enqueue(int x) {
        if (isFull()) {
            cout << "队列已满，无法入队！" << endl;
            return;
        }
        data[rear] = x;
        rear = (rear + 1) % MAX_SIZE; // 循环移动队尾指针
        size++;
    }
    
    // 出队操作
    void dequeue() {
        if (isEmpty()) {
            cout << "队列为空，无法出队！" << endl;
            return;
        }
        front = (front + 1) % MAX_SIZE; // 循环移动队头指针
        size--;
    }
    
    // 获取队头元素
    int getFront() {
        if (isEmpty()) {
            cout << "队列为空！" << endl;
            return -1;
        }
        return data[front];
    }
    
    // 判断队列是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 判断队列是否已满
    bool isFull() {
        return size == MAX_SIZE;
    }
    
    // 获取队列大小
    int getSize() {
        return size;
    }
};

// 测试
int main() {
    CircularQueue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    
    cout << "队头元素：" << q.getFront() << endl; // 输出：1
    cout << "队列大小：" << q.getSize() << endl;   // 输出：3
    
    q.dequeue();
    cout << "出队后队头元素：" << q.getFront() << endl; // 输出：2
    
    while (!q.isEmpty()) {
        q.dequeue();
    }
    cout << "清空队列后是否为空：" << (q.isEmpty() ? "是" : "否") << endl; // 输出：是
    
    return 0;
}

2. 链式队列实现

c++

#include <iostream>
using namespace std;

// 节点结构
struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

class LinkQueue {
private:
    Node* front; // 队头指针（指向队头节点）
    Node* rear;  // 队尾指针（指向队尾节点）
    int size;    // 队列大小
public:
    // 构造函数：初始化空队列
    LinkQueue() : front(nullptr), rear(nullptr), size(0) {}
    
    // 入队操作
    void enqueue(int x) {
        Node* newNode = new Node(x);
        if (isEmpty()) {
            // 空队列时，队头和队尾都指向新节点
            front = rear = newNode;
        } else {
            // 非空队列时，队尾节点指向新节点，更新队尾指针
            rear->next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    // 出队操作
    void dequeue() {
        if (isEmpty()) {
            cout << "队列为空，无法出队！" << endl;
            return;
        }
        Node* temp = front;
        front = front->next;
        // 如果队列变为空，队尾也置为空
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp; // 释放节点内存
        size--;
    }
    
    // 获取队头元素
    int getFront() {
        if (isEmpty()) {
            cout << "队列为空！" << endl;
            return -1;
        }
        return front->data;
    }
    
    // 判断队列是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 获取队列大小
    int getSize() {
        return size;
    }
    
    // 析构函数：释放所有节点
    ~LinkQueue() {
        while (front != nullptr) {
            Node* temp = front;
            front = front->next;
            delete temp;
        }
        rear = nullptr;
    }
};

// 测试
int main() {
    LinkQueue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    
    cout << "队头元素：" << q.getFront() << endl; // 输出：10
    cout << "队列大小：" << q.getSize() << endl;   // 输出：3
    
    q.dequeue();
    cout << "出队后队头元素：" << q.getFront() << endl; // 输出：20
    
    return 0;
}

3. 队列的典型应用：广度优先搜索（BFS）

c++

#include <iostream>
#include <vector>
using namespace std;

// 邻接表表示图
vector<vector<int>> graph;
// 记录节点是否被访问
vector<bool> visited;

// BFS函数
void bfs(int start) {
    LinkQueue q; // 使用前面实现的链式队列
    
    // 起始节点入队并标记为访问
    q.enqueue(start);
    visited[start] = true;
    
    while (!q.isEmpty()) {
        // 队头节点出队
        int current = q.getFront();
        q.dequeue();
        cout << current << " "; // 访问节点
        
        // 遍历所有邻接节点
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.enqueue(neighbor);
            }
        }
    }
}

int main() {
    // 构建图（5个节点）
    int n = 5;
    graph.resize(n);
    visited.resize(n, false);
    
    // 添加边
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(4);
    
    cout << "BFS遍历结果：";
    bfs(0); // 输出：0 1 2 3 4
    
    return 0;
}

4. 队列的典型应用：滑动窗口最大值

c++

#include <iostream>
#include <vector>
#include <deque> // C++标准库双端队列
using namespace std;

// 求滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> q; // 存储下标，队头为当前窗口最大值的下标
    
    for (int i = 0; i < nums.size(); i++) {
        // 移除窗口外的元素
        while (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        }
        
        // 移除队列中比当前元素小的元素
        while (!q.empty() && nums[q.back()] < nums[i]) {
            q.pop_back();
        }
        
        // 当前元素下标入队
        q.push_back(i);
        
        // 当窗口大小达到k时，开始记录结果
        if (i >= k - 1) {
            result.push_back(nums[q.front()]);
        }
    }
    
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    
    cout << "滑动窗口最大值：";
    for (int num : res) {
        cout << num << " "; // 输出：3 3 5 5 6 7
    }
    cout << endl;
    
    return 0;
}

三、信奥赛应用场景

信奥赛应用场景

1. 广度优先搜索（BFS）：层次遍历图或树，如最短路径问题、迷宫求解
2. 滑动窗口问题：处理固定大小的窗口内的极值或统计
3. 队列模拟：如银行排队、打印机任务调度等模拟类问题
4. 缓冲区设计：如字符流处理、数据缓冲等
5. 单调队列：解决滑动窗口最大值、最小值等问题
6. 树的层次遍历：按层次输出树的节点
7. 图的拓扑排序：有向无环图（DAG）的拓扑排序实现

四、避坑指南

避坑指南

1. 循环队列的边界处理：
   • 区分空队列和满队列：通过size变量或预留一个空位置
   • 队头队尾指针移动时必须使用取模运算实现循环
   c++

   // 错误示例：未使用取模运算
   rear++; // 可能超出数组范围
   
   // 正确示例
   rear = (rear + 1) % MAX_SIZE;

2. 链式队列的空队列处理：出队后若队列变空，需同时将rear置为nullptr

c++

void dequeue() {
    if (isEmpty()) return;
    Node* temp = front;
    front = front->next;
    if (front == nullptr) {
        rear = nullptr; // 关键：队列为空时队尾也为空
    }
    delete temp;
}

3. 入队出队的顺序性：严格遵守FIFO原则，不能在中间插入或删除元素

c++

// 错误：直接修改队头元素
front->data = x; // 破坏了队列的顺序性

4. 选择合适的实现方式：

   • 数据量固定且已知：用循环队列（效率高）
   • 数据量不确定或可能很大：用链式队列（避免溢出）
   • 需要两端操作：用双端队列（deque）

5. 标准库队列的使用：信奥赛中可直接使用queue或deque，但需注意：

c++

#include <queue>
queue<int> q; // 普通队列
deque<int> dq; // 双端队列，支持front()、back()、push_back()、push_front()等

重要

• 核心特性：队列是FIFO结构，元素从队尾入队、队头出队，插入和删除效率为O(1)
• 实现方式：循环队列适合固定大小场景，链式队列适合动态大小场景，双端队列支持两端操作
• 关键操作：入队、出队、取队头元素，需注意边界条件（空队列、满队列）
• 应用核心：利用"先进先出"特性解决具有顺序性的问题（如BFS、滑动窗口、模拟排队等）