STL栈与队列：配接器模式深度解析

好的，我们来深入剖析STL中的stack和queue，聚焦其作为**配接器（Adapter）**的设计模式、底层容器依赖关系及关键实现细节。

1. 设计模式：配接器（Adapter）

stack和queue并非独立容器，而是基于配接器模式实现的容器适配器。其核心思想是：

• 复用现有容器：通过封装一个底层容器（如deque、list），限制其接口，提供特定语义的访问方式。
• 接口转换：将底层容器的操作转化为栈（后进先出，LIFO）或队列（先进先出，FIFO）的专属操作。

底层容器依赖

默认情况下：

• stack 和 queue 均使用 deque 作为底层容器。
• 可通过模板参数显式指定底层容器类型：

  stack<int, vector<int>> my_stack; // 基于vector实现栈
  queue<char, list<char>> my_queue; // 基于list实现队列

关键约束：底层容器必须支持以下操作：

• stack：push_back, pop_back, back, size, empty。
• queue：push_back, pop_front, front, back, size, empty。

2. 源码探秘：接口与实现

stack 的核心接口

template <typename T, typename Container = deque<T>>
class stack {
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(); }
private:
Container c; // 底层容器
};

关键点：

• push → push_back
• pop → pop_back
• top → back

queue 的核心接口

template <typename T, typename Container = deque<T>>
class queue {
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(); }
size_t size() const { return c.size(); }
private:
Container c; // 底层容器
};

https://tv.sohu.com/v/dXMvNDQyMzEwMjg0LzcwMjIxMDQ5OC5zaHRtbA==.html
https://tv.sohu.com/v/dXMvNDQyMzEwMjg0LzcwMjIxMDcyMC5zaHRtbA==.html
https://tv.sohu.com/v/dXMvNDQyMzEwMjg0LzcwMjIxMDcxOC5zaHRtbA==.html
https://tv.sohu.com/v/dXMvNDQyMzEwMjg0LzcwMjIxMDcxNy5zaHRtbA==.html
https://tv.sohu.com/v/dXMvNDQyMzEwMjg0LzcwMjIxMDcxNi5zaHRtbA==.html

关键点：

• push → push_back
• pop → pop_front
• front → front
• back → back

3. 为什么默认使用 deque？

deque（双端队列）能同时高效支持push_back、pop_back、pop_front操作：

• 栈适配：仅需push_back和pop_back，复杂度为$O(1)$。
• 队列适配：需push_back和pop_front，deque的pop_front同样为$O(1)$。
• 内存效率：相比list的指针开销，deque分块存储更紧凑。

4. 性能特征

注意：若底层容器为vector：

• stack 的 pop 仍为 $O(1)$，但 push 可能触发扩容（均摊 $O(1)$）。
• queue 的 pop 为 $O(n)$（需移动元素），不满足要求！因此不可用vector实现队列。

5. 总结：配接器的精髓

• 复用而非重建：通过限制底层容器接口，快速实现新数据结构。
• 灵活替换：用户可指定底层容器以平衡性能与内存。
• 语义隔离：stack和queue隐藏了底层容器的复杂操作，仅暴露符合其行为模型的接口。

通过这种设计，STL以极低的代码冗余实现了多种数据结构的高效组合，体现了泛型编程的强大威力。