C++栈与队列的容器适配器实现

容器适配器设计模式通过封装现有容器（如deque、list或vector），提供特定接口实现栈（LIFO）和队列（FIFO）数据结构。以下是源码解析和实现：

一、栈（Stack）适配器

template <typename T, typename Container = std::deque<T>>
class Stack {
public:
    // 元素访问
    T& top() { 
        return c.back(); 
    }
    
    // 容量操作
    bool empty() const { 
        return c.empty(); 
    }
    size_t size() const { 
        return c.size(); 
    }
    
    // 修改操作
    void push(const T& value) { 
        c.push_back(value); 
    }
    void pop() { 
        c.pop_back(); 
    }

private:
    Container c;  // 底层容器
};

设计要点：

1. 底层容器要求：必须支持back()、push_back()、pop_back()
2. 默认容器：std::deque（两端操作$O(1)$时间复杂度）
3. 接口限制：仅暴露栈操作（隐藏底层容器的其他方法）

二、队列（Queue）适配器

template <typename T, typename Container = std::deque<T>>
class Queue {
public:
    // 元素访问
    T& front() { 
        return c.front(); 
    }
    T& back() { 
        return c.back(); 
    }
    
    // 容量操作
    bool empty() const { 
        return c.empty(); 
    }
    size_t size() const { 
        return c.size(); 
    }
    
    // 修改操作
    void push(const T& value) { 
        c.push_back(value); 
    }
    void pop() { 
        c.pop_front(); 
    }

private:
    Container c;  // 底层容器
};

设计要点：

1. 底层容器要求：必须支持front()、back()、push_back()、pop_front()
2. 容器限制：std::vector不可用（缺少高效$O(1)$的pop_front()）
3. 时间复杂度：所有操作保证$O(1)$

三、设计模式解析

1. 适配器模式核心：

   • 组合关系：包含底层容器对象
   • 接口转换：通过封装暴露受限接口 $$ \text{适配器} = \text{目标接口} + \text{被适配者} $$

2. 底层容器选择：

   操作	栈所需支持	队列所需支持
   前端删除	×	✓ (pop_front)
   后端插入	✓ (push_back)	✓ (push_back)
   后端删除	✓ (pop_back)	×

3. 模板参数设计：

   template <typename T, typename Container = std::deque<T>>
   

   • T：元素类型
   • Container：满足接口要求的任意容器（默认deque）

四、使用示例

// 栈使用
Stack<int, std::vector<int>> s;  // 使用vector作为底层容器
s.push(10);
s.push(20);
s.pop();  // 移除20

// 队列使用
Queue<std::string> q;           // 默认deque容器
q.push("first");
q.push("second");
q.pop();  // 移除"first"

五、设计优势

1. 代码复用：重用现有容器实现
2. 接口一致性：提供标准数据结构接口
3. 灵活性：可自由切换底层容器（如Stack<int, list<int>>）
4. 复杂度保证：所有操作保持$O(1)$时间复杂度

关键限制：队列适配器不能使用vector，因其pop_front()操作时间复杂度为$O(n)$，违反队列的基本操作要求。