C++ STL栈与队列的适配器模式实现

一、适配器模式的核心思想

在C++ STL中，栈（std::stack）和队列（std::queue）通过适配器模式实现，其本质是：

1. 复用底层容器：基于现有容器（如 deque, list, vector）实现
2. 接口转换：通过封装限制操作，仅暴露栈/队列的特有接口
3. 默认底层容器：栈和队列默认使用 std::deque 实现

二、栈（stack）的适配器实现

核心操作：

• push()：入栈 → 调用底层容器的 push_back()
• pop()：出栈 → 调用底层容器的 pop_back()
• top()：获取栈顶 → 调用底层容器的 back()

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(); 
    }
};

底层容器要求：

• 必须支持 back(), push_back(), pop_back()
• 可用容器：deque（默认）、vector、list

---

三、队列（queue）的适配器实现

核心操作：

• push()：入队 → 调用底层容器的 push_back()
• pop()：出队 → 调用底层容器的 pop_front()
• front()：获取队首 → 调用底层容器的 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() { 
        c.pop_front(); 
    }
    T& front() { 
        return c.front(); 
    }
    bool empty() const { 
        return c.empty(); 
    }
};

底层容器要求：

• 必须支持 front(), push_back(), pop_front()
• 可用容器：deque（默认）、list
• 不可用：vector（缺少 $O(1)$ 的 pop_front()）

---

四、适配器模式的优势

1. 代码复用：无需重新实现底层存储
2. 灵活性：可自由更换底层容器

   std::stack<int, std::vector<int>> vec_stack;  // 基于vector的栈
   std::queue<int, std::list<int>> list_queue;    // 基于list的队列
   

3. 接口统一：不同底层容器提供一致的操作接口

---

五、经典算法应用

案例：用栈实现队列（LeetCode 232）

class MyQueue {
private:
    std::stack<int> in, out;
    
    void transfer() {
        while (!in.empty()) {
            out.push(in.top());
            in.pop();
        }
    }
public:
    void push(int x) { 
        in.push(x); 
    }
    int pop() {
        if (out.empty()) transfer();
        int val = out.top();
        out.pop();
        return val;
    }
    int peek() {
        if (out.empty()) transfer();
        return out.top();
    }
};

算法分析：

• 时间复杂度：均摊 $O(1)$
• 空间复杂度：$O(n)$
• 核心思想：用两个栈模拟队列的 FIFO 特性

---

六、性能对比

操作	栈（deque底层）	队列（deque底层）
push()	$O(1)$ 均摊	$O(1)$ 均摊
pop()	$O(1)$	$O(1)$
随机访问	不支持	不支持

注：使用 vector 作为栈底层时，push() 可能触发扩容（$O(n)$），但均摊后仍为 $O(1)$。

---

总结

1. 设计本质：栈和队列是接口受限的容器适配器
2. 底层依赖：栈依赖 push_back/pop_back，队列依赖 push_back/pop_front
3. 应用场景：
   • 栈：函数调用栈、括号匹配、DFS
   • 队列：BFS、缓冲区、任务调度
4. 扩展思考：优先队列（std::priority_queue）本质是堆适配器，默认使用 vector 实现