下面是关于「栈和队列」这两个经典数据结构的完整讲解，包括原理、实现、常用操作、应用场景与典型例题，适用于蓝桥杯、数据结构课程与编程面试。

📚 目录

  1. 栈（Stack）
    • 定义与特性
    • 顺序栈与链式栈实现
    • 常用操作
    • 应用场景与典型题
  2. 队列（Queue）
    • 定义与特性
    • 顺序队列、链式队列、循环队列
    • 常用操作
    • 应用场景与典型题
  3. 栈与队列的区别与联系
  4. 蓝桥杯/LeetCode经典题汇总

1. ✅ 栈（Stack）

🔍 定义与特性

  • 先进后出（LIFO）：Last In First Out
  • 操作只能在栈顶进行
  • 常见操作：
    • push(x)：压栈
    • pop()：弹栈
    • top()：查看栈顶元素
    • isEmpty()：判断是否为空

🔧 顺序栈实现（数组版）

int stk[100], top = -1;

void push(int x) {
    stk[++top] = x;
}

void pop() {
    --top;
}

int getTop() {
    return stk[top];
}

🧱 链式栈实现（链表）

struct Node {
    int val;
    Node* next;
};

Node* top = nullptr;

void push(int x) {
    Node* node = new Node{x, top};
    top = node;
}

void pop() {
    Node* tmp = top;
    top = top->next;
    delete tmp;
}

🎯 应用场景

场景说明
括号匹配左右括号入栈出栈是否匹配
表达式求值后缀表达式、中缀转后缀
深度优先搜索（DFS）用栈代替递归
撤销功能浏览器后退、文本编辑器撤销等

2. ✅ 队列（Queue）

🔍 定义与特性

  • 先进先出（FIFO）：First In First Out
  • 入队在队尾，出队在队头

🔧 顺序队列实现（数组）

int q[100], front = 0, rear = 0;

void enqueue(int x) {
    q[rear++] = x;
}

void dequeue() {
    ++front;
}

int getFront() {
    return q[front];
}

🔁 循环队列（避免假溢出）

const int N = 100;
int q[N], front = 0, rear = 0;

bool isFull() { return (rear + 1) % N == front; }
bool isEmpty() { return front == rear; }

void enqueue(int x) {
    if (!isFull()) {
        q[rear] = x;
        rear = (rear + 1) % N;
    }
}

void dequeue() {
    if (!isEmpty()) {
        front = (front + 1) % N;
    }
}

🎯 应用场景

场景说明
宽度优先搜索（BFS）图与树的层次遍历
消息队列、打印队列任务排队
滑动窗口最值问题单调队列优化
多线程中的生产者消费者模型线程通信

3. 🆚 栈与队列对比总结

属性/操作栈（Stack）队列（Queue）
操作方向只在栈顶头出尾进
数据特性先进后出 LIFO先进先出 FIFO
常见用途DFS、括号匹配等BFS、滑动窗口等
实现方式顺序、链式栈顺序、链式、循环队列

4. 📌 蓝桥杯/LeetCode经典题推荐

✅ 栈相关

  • LeetCode 20. 有效的括号
  • LeetCode 155. 最小栈
  • LeetCode 739. 每日温度（单调栈）
  • 蓝桥杯：栈操作模拟题（括号、表达式）

✅ 队列相关

  • LeetCode 933. 最近请求次数（队列）
  • LeetCode 239. 滑动窗口最大值（单调队列）
  • 蓝桥杯：BFS 图遍历、最短路径问题
  • 蓝桥杯：循环队列模拟问题（工位排队等）

📘 拓展学习建议

  • 掌握 STL：C++ 中 stack<T> 与 queue<T>、deque<T> 使用；
  • 熟练写出手动实现模板（用于面试/竞赛）；
  • 深入应用：单调栈/队列、双端队列 deque、优先队列 priority_queue；
  • 多刷题巩固，如力扣标签「栈」「队列」。