C++容器适配器：栈与队列底层实现解析

一、容器适配器核心概念

容器适配器不直接管理内存，而是基于现有容器封装特定接口：

1. 栈 (Stack)：后进先出 (LIFO) 结构
   • 核心操作：push(), pop(), top()
2. 队列 (Queue)：先进先出 (FIFO) 结构
   • 核心操作：push(), pop(), front(), back()

二、栈 (Stack) 底层实现

默认基于 deque 实现，也可指定 vector 或 list：

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() {
        if (!empty()) c.pop_back();  // 尾部删除
    }

    T& top() {
        return c.back();  // 访问尾部元素
    }

    bool empty() const {
        return c.empty();
    }

    size_t size() const {
        return c.size();
    }
};

关键点：

• 时间复杂度：$O(1)$
• 底层依赖容器的 push_back(), pop_back(), back()

三、队列 (Queue) 底层实现

默认基于 deque，不可用 vector（缺少 pop_front）：

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() {
        if (!empty()) c.pop_front();  // 头部出队
    }

    T& front() {
        return c.front();  // 访问头部
    }

    T& back() {
        return c.back();   // 访问尾部
    }

    bool empty() const {
        return c.empty();
    }

    size_t size() const {
        return c.size();
    }
};

关键点：

• 时间复杂度：$O(1)$
• 必须支持 pop_front()（故 vector 不适用）

四、底层容器选择对比

操作	deque	vector	list
push_back	$O(1)$	均摊 $O(1)$	$O(1)$
pop_back	$O(1)$	$O(1)$	$O(1)$
pop_front	$O(1)$	$O(n)$	$O(1)$
内存布局	分段连续	连续	非连续

五、应用场景分析

1. 栈适用场景：

   • 函数调用栈
   • 表达式求值（如：$3 * (4 + 2)$）
   • 撤销操作 (Ctrl+Z)

2. 队列适用场景：

   • 消息缓冲区
   • 广度优先搜索 (BFS)
   • 打印机任务调度

实现要点：容器适配器通过限制底层容器的接口实现特定数据行为，体现了组合优于继承的设计原则。实际开发中应优先使用 std::stack 和 std::queue，避免重复造轮子。