栈和队列有哪些特殊的操作？栈和队列能解决什么样的问题？用栈和队列这种数据结构，来解决与“先进先出”、“先进后出”有关的实际问题了，如宽度优先搜索、表达式求值等。

类比 - 日常生活普遍规律

如果桌上有一叠盘子，大家都只会拿最上面的那一个。食堂排队的时候，你总是先找到队尾加入，而排在队首的同学打完饭之后就会离开。

类比计算机，也许只需要在线性序列的一端或两端进行操作，对应的就是栈和队列这两种受限的线性表，他们是最简单的基础数据结构，应用也最广泛。

重点：栈的 LIFO（后进先出）特性，深度优先搜索，理解递归中栈的作用；队列的 FIFO（先进先出）特性，宽度优先搜索。
难点：机械的递归转非递归，简单理解就可以了，不需要掌握；顺序队列的实现假溢出处理。

栈

在C++程序中，栈（Stack） 是一种非常重要的线性数据结构，它遵循 LIFO（Last In, First Out） 原则，即 后进先出。

一、栈的核心特点

后进先出（LIFO）：最后被添加到栈中的元素，会最先被移除。
只能在一端操作：所有的插入（入栈/Push）和删除（出栈/Pop）操作都发生在栈的同一端，这一端被称为 栈顶（Top）。
另一端是固定的：栈的另一端称为 栈底（Bottom）。

📌 类比：

想象一个放羽毛球的筒：

你只能从筒的开口（栈顶）放入或取出羽毛球。
最后放进去的球，会最先被拿出来。

二、栈的基本操作

操作	描述
`push(x)`	将元素 `x` 压入栈顶
`pop()`	移除并返回栈顶元素
`top()` / `peek()`	返回栈顶元素，但不移除
`empty()`	判断栈是否为空
`size()`	返回栈中元素的个数

三、C++ 中如何实现栈？

C++ 提供了两种主要方式来使用栈：

1. 使用 STL 容器适配器 `std::stack`

这是最常用、最推荐的方式。std::stack 是一个容器适配器，默认基于 std::deque 实现。

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s; // 创建一个存储 int 类型的栈

    s.push(10); // 入栈
    s.push(20);
    s.push(30);

    std::cout << "栈顶元素: " << s.top() << std::endl; // 输出: 30

    s.pop(); // 出栈

    std::cout << "新的栈顶元素: " << s.top() << std::endl; // 输出: 20

    std::cout << "栈的大小: " << s.size() << std::endl; // 输出: 2

    if (!s.empty()) {
        std::cout << "栈非空" << std::endl;
    }

    return 0;
}

`std::stack` 的特点：

使用简单，接口清晰。

默认底层容器是 std::deque，也可以指定为 std::vector 或 std::list：

std::stack<int, std::vector<int>> s_vec; // 基于 vector
std::stack<int, std::list<int>> s_list;  // 基于 list

2. 自己用数组或链表实现

虽然不常用，但理解其原理很重要。

示例：基于数组的简单栈实现

#include <iostream>
#include <stdexcept> // for std::underflow_error

class ArrayStack {
private:
    int* arr;
    int capacity;
    int topIndex;

public:
    ArrayStack(int size) : capacity(size), topIndex(-1) {
        arr = new int[capacity];
    }

    ~ArrayStack() {
        delete[] arr;
    }

    void push(int x) {
        if (topIndex >= capacity - 1) {
            throw std::overflow_error("Stack overflow");
        }
        arr[++topIndex] = x;
    }

    void pop() {
        if (topIndex < 0) {
            throw std::underflow_error("Stack underflow");
        }
        --topIndex;
    }

    int top() const {
        if (topIndex < 0) {
            throw std::underflow_error("Stack is empty");
        }
        return arr[topIndex];
    }

    bool empty() const {
        return topIndex == -1;
    }

    int size() const {
        return topIndex + 1;
    }
};

int main() {
    ArrayStack s(5); // 创建容量为5的栈

    s.push(10);
    s.push(20);
    std::cout << "栈顶: " << s.top() << std::endl; // 输出: 20
    s.pop();
    std::cout << "栈顶: " << s.top() << std::endl; // 输出: 10
    std::cout << "大小: " << s.size() << std::endl; // 输出: 1

    return 0;
}

四、栈的应用场景

栈在程序设计和算法中应用非常广泛：

函数调用管理：程序运行时，函数调用的返回地址、局部变量等都存储在调用栈（Call Stack）中。
表达式求值与转换：如中缀表达式转后缀表达式（逆波兰表示法）。
括号匹配检查：检查代码中的括号是否匹配。
深度优先搜索（DFS）：在图或树的遍历中，DFS通常用栈来实现。
浏览器历史记录：后退功能可以看作是栈的应用。
撤销操作（Undo）：很多软件的撤销功能是基于栈实现的。

五、总结

特性	描述
数据结构类型	线性结构
访问原则	LIFO（后进先出）
主要操作	`push`, `pop`, `top`, `empty`, `size`
C++实现	推荐使用 `std::stack`
常见用途	函数调用、表达式计算、DFS、括号匹配等

队列

一、队列的核心概念

队列（Queue） 是一种线性数据结构，它遵循 FIFO（First In, First Out） 原则，即 先进先出。

📌 直观理解：

想象你在银行或餐厅排队：

先排队的人（先“入队”）会先被服务（先“出队”）。
新来的人总是排在队尾。
服务人员总是从队头叫人。

二、队列的基本操作

操作	描述
`enqueue(x)` / `push(x)`	将元素 `x` 添加到队列的尾部（入队）
`dequeue()` / `pop()`	移除并返回队列头部的元素（出队）
`front()`	返回队列头部的元素，但不移除
`back()`	返回队列尾部的元素（非标准，但常见）
`empty()`	判断队列是否为空
`size()`	返回队列中元素的个数

三、C++ 中如何使用队列？

C++ 标准模板库（STL）提供了 std::queue 容器适配器，这是使用队列最方便的方式。

1. 使用 STL `std::queue`

std::queue 默认是基于 std::deque 实现的。

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q; // 创建一个存储 int 类型的队列

    // 入队
    q.push(10);
    q.push(20);
    q.push(30);

    // 查看队头和队尾元素
    std::cout << "队头元素: " << q.front() << std::endl; // 输出: 10
    std::cout << "队尾元素: " << q.back() << std::endl;  // 输出: 30

    // 出队
    q.pop(); // 移除 10

    std::cout << "新的队头元素: " << q.front() << std::endl; // 输出: 20

    // 其他信息
    std::cout << "队列大小: " << q.size() << std::endl; // 输出: 2

    if (!q.empty()) {
        std::cout << "队列非空" << std::endl;
    }

    // 继续出队直到为空
    while (!q.empty()) {
        std::cout << "出队: " << q.front() << std::endl;
        q.pop();
    }

    return 0;
}

`std::queue` 的特点：

使用简单，接口清晰。
默认底层容器是 std::deque，也可以指定为 std::list（不能是 std::vector，因为 vector 不支持高效的头部删除）：
```
#include <list>
std::queue<int, std::list<int>> q_list; // 基于 list
```

四、队列的其他变种

STL 还提供了一些队列的变种：

1. `std::priority_queue`（优先队列）

元素具有优先级，最高优先级的元素总是在队头。
通常基于堆（Heap）实现。
默认是最大堆（最大元素优先）。

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq; // 最大堆

    pq.push(10);
    pq.push(30);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 输出: 30 20 10
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

2. 双端队列 `std::deque`

允许在两端进行插入和删除操作。
std::queue 和 std::stack 都可以基于 std::deque 实现。

五、队列的应用场景

队列在计算机科学和日常生活中应用广泛：

广度优先搜索（BFS）：在图或树的遍历中，BFS 通常使用队列来实现。
任务调度：操作系统或打印任务队列，先提交的任务先执行。
缓冲区：处理数据流时，如键盘输入缓冲、网络数据包缓冲。
模拟排队系统：如银行、超市结账队列。
多线程编程：生产者-消费者模型中，生产者将任务放入队列，消费者从队列中取出任务。

六、栈 vs 队列对比

特性	栈 (Stack)	队列 (Queue)
原则	LIFO (后进先出)	FIFO (先进先出)
插入操作	`push()` 到顶部	`push()` / `enqueue()` 到尾部
删除操作	`pop()` 从顶部	`pop()` / `dequeue()` 从头部
访问元素	`top()` 访问顶部	`front()` 访问头部, `back()` 访问尾部
比喻	一摞盘子	排队

七、总结

特性	描述
数据结构类型	线性结构
访问原则	FIFO（先进先出）
主要操作	`push`, `pop`, `front`, `back`, `empty`, `size`
C++实现	推荐使用 `std::queue`
常见用途	BFS、任务调度、缓冲区、模拟排队等

类比 - 日常生活普遍规律#

栈#

一、栈的核心特点#

📌 类比：#

二、栈的基本操作#

三、C++ 中如何实现栈？#

1. 使用 STL 容器适配器 std::stack#

std::stack 的特点：#

2. 自己用数组或链表实现#

示例：基于数组的简单栈实现#

四、栈的应用场景#

五、总结#

队列#

一、队列的核心概念#

📌 直观理解：#

二、队列的基本操作#

三、C++ 中如何使用队列？#

1. 使用 STL std::queue#

std::queue 的特点：#

四、队列的其他变种#

1. std::priority_queue（优先队列）#

2. 双端队列 std::deque#

五、队列的应用场景#

六、栈 vs 队列 对比#

七、总结#