C++容器适配器进阶：栈与队列的模拟实现与性能分析

一、栈（Stack）的模拟实现

栈是后进先出（LIFO）的容器适配器，核心操作包括：

• push(): 压入元素
• pop(): 弹出元素
• top(): 访问栈顶元素
• empty(): 判空

底层容器选择：默认使用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() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

二、队列（Queue）的模拟实现

队列是先进先出（FIFO）的容器适配器，核心操作包括：

• push(): 入队
• pop(): 出队
• front(): 访问队首
• back(): 访问队尾

底层容器选择：必须支持push_back()和pop_front()，通常用deque或list

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(); }
    size_t size() const { return c.size(); }
};

三、性能分析

时间复杂度对比（$n$为元素数量）：

关键性能因素：

1. 内存分配策略：

   • deque：分块连续存储，扩容成本低
   • vector：连续存储，扩容时需整体复制（$O(n)$）
   • list：非连续存储，无扩容开销但缓存不友好

2. 操作边界影响：

   • 栈：仅需操作单端（尾部）
   • 队列：需操作双端（头部和尾部）

3. 实际场景建议：

   • 栈首选vector：尾部操作高效，内存连续提升缓存命中率
   • 队列必选deque：避免vector的头部删除开销（$O(n)$）和list的指针开销
   • 元素量极大时：栈可用vector预留容量（reserve()），队列用deque

四、应用场景对比

通过自定义底层容器，可平衡内存与性能需求。例如高吞吐场景用vector栈，强实时系统用deque队列。