容器适配器进阶：从栈到队列的C++模拟实现技巧

一、容器适配器核心概念

容器适配器通过封装底层容器（如deque或list），提供特定接口实现受限访问：

1. 栈：后进先出（LIFO）结构，支持操作：

   • push(): 元素入栈
   • pop(): 栈顶出栈
   • top(): 访问栈顶元素 $$ \text{栈操作复杂度} = O(1) $$

2. 队列：先进先出（FIFO）结构，支持操作：

   • push(): 元素入队尾
   • pop(): 队首出队
   • front()/back(): 访问首尾元素 $$ \text{队列操作复杂度} = O(1) $$

二、栈的模拟实现

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

关键技巧：

1. 选择deque作为默认容器：支持$O(1)$复杂度的两端操作
2. 禁用不相关接口：隐藏底层容器的insert()等非栈操作
3. 异常安全：pop()前检查空栈状态

三、队列的模拟实现

template <typename T, typename Container = std::deque<T>>
class MyQueue {
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(); 
    }
    // size()和empty()实现同栈
};

进阶技巧：

1. 容器选择策略：
   • deque：默认选择，内存非连续但高效
   • list：需频繁中间插入时使用

   MyQueue<int, std::list<int>> customQueue;
   

2. 迭代器控制：禁用底层容器的随机访问迭代器，防止破坏FIFO特性
3. 移动语义优化：

   void push(T&& value) { 
       c.push_back(std::move(value)); 
   }
   

四、性能对比与选型

操作	栈（deque）	队列（deque）	队列（list）
push()	$O(1)$	$O(1)$	$O(1)$
pop()	$O(1)$	$O(1)$	$O(1)$
内存局部性	高	高	低

选型建议：

1. 栈：优先选择deque（缓存友好）
2. 队列：
   • 99%场景使用deque
   • 需频繁中间插入时用list
   • 避免vector（队首删除$O(n)$）

五、特殊场景实现

循环队列（固定容量）：

template <typename T, size_t N>
class CircularQueue {
private:
    std::array<T, N> data;
    size_t head = 0, tail = 0, count = 0;
public:
    void push(const T& value) {
        if (count == N) throw std::overflow_error("Queue full");
        data[tail] = value;
        tail = (tail + 1) % N;
        ++count;
    }
    void pop() {
        if (count == 0) throw std::underflow_error("Queue empty");
        head = (head + 1) % N;
        --count;
    }
    // ...其他接口
};

优势：内存预分配，无动态内存开销，适合嵌入式系统

通过封装底层容器并限制接口，容器适配器在保持高性能的同时提供了简洁的抽象层。实际开发中应优先使用标准库的stack/queue，理解其实现原理有助于处理特殊需求场景。