从理论到实践：C++容器适配器中的栈与队列实现

一、理论基础

1. 容器适配器本质
   栈（stack）和队列（queue）是基于其他容器实现的接口封装，遵循特定操作规则：

   • 栈：后进先出（LIFO），核心操作：
     $push$（入栈），$pop$（出栈），$top$（访问栈顶）
   • 队列：先进先出（FIFO），核心操作：
     $push$（入队），$pop$（出队），$front$（访问队首），$back$（访问队尾）

2. 底层容器依赖
   默认使用 deque 实现，但可指定其他序列容器： $$ \begin{cases} \text{栈} & \rightarrow \text{需支持 } back(),\ push_back(),\ pop_back() \ \text{队列} & \rightarrow \text{需支持 } back(),\ front(),\ push_back(),\ pop_front() \end{cases} $$ 例如 vector 或 list 均可作为底层容器。

二、C++实现解析

1. 栈（stack）实现示例

#include <deque>
template <typename T, typename Container = std::deque<T>>
class Stack {
private:
    Container c;  // 底层容器
public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

关键点：

• 所有操作在 $O(1)$ 时间复杂度完成
• 指定 vector 为底层容器时需注意扩容开销

2. 队列（queue）实现示例

#include <deque>
template <typename T, typename Container = std::deque<T>>
class Queue {
private:
    Container c;  
public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_front(); }
    T& front() { return c.front(); }
    T& back() { return c.back(); }
    bool empty() const { return c.empty(); }
};

关键点：

• 若使用 vector 作为底层容器，$pop_front()$ 将导致 $O(n)$ 元素移动
• deque 的块状存储结构保证两端操作均为 $O(1)$

三、实践应用场景

1. 栈的典型应用

   • 函数调用栈（递归实现）
   • 括号匹配检测（({[]})）
   • 深度优先搜索（DFS）

2. 队列的典型应用

   • 消息缓冲队列（生产者-消费者模型）
   • 广度优先搜索（BFS）
   • 打印机任务调度

四、性能优化建议

1. 容器选择策略

   场景	推荐容器	原因
   高频随机访问	vector	连续内存缓存友好
   频繁两端插入/删除	deque	避免内存重分配
   中间插入操作多	list	$O(1)$ 插入删除

2. 临界操作注意事项

   • 调用 $pop()$ 前必须检查 $empty()$，否则引发未定义行为
   • 多线程场景需配合互斥锁（如 std::mutex）

五、扩展实现：最小栈

#include <stack>
class MinStack {
    std::stack<int> data_stack;
    std::stack<int> min_stack;  // 辅助栈存储历史最小值
public:
    void push(int x) {
        data_stack.push(x);
        if (min_stack.empty() || x <= min_stack.top()) {
            min_stack.push(x);
        }
    }
    void pop() {
        if (data_stack.top() == min_stack.top()) {
            min_stack.pop();
        }
        data_stack.pop();
    }
    int getMin() { return min_stack.top(); }
};

数学原理：
通过辅助栈维护最小值序列，空间换时间，保证 $getMin()$ 操作时间复杂度为 $O(1)$。

通过容器适配器模式，C++实现了数据结构与操作的解耦，开发者可灵活选择底层容器以满足不同场景的性能需求。