引言

模擬實現queue和stack，理解適配器，實現起來非常簡單。

一、適配器?

????????適配器是一種能讓原本不兼容的接口協同工作的設計模式或者組件。它的主要作用是對一個類的接口進行轉換，使其符合另一個類的期望接口，進而實現適配和復用。（看下面代碼來理解）

可以理解為是一個更高層次的封裝。（解耦性更高）

比如：stack可以封裝list來實現，queue也可以封裝一個list來實現，但是list對內存的空間利用率不高。用vector封裝實現的話，頭插和頭刪的效率很低。

所以底層實現了一個雙端隊列deque用來解決上面的問題。

deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端 進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與 list比較，空間利用率比較高。

deque的底層這里就不多描述了。

二、模擬實現queue

queue是先進后出的數據結構，即只能在尾部插入，頭部刪除。

#include <deque>namespace stl
{template<class T, class Container = deque<T>> //用deque做適配器class queue{public:void push(const T& x) //尾插{_con.push_back(x);}void pop() //頭刪{_con.pop_front();}size_t size() const  //元素個數{return _con.size();}bool empty() const  //判空{return _con.empty();}const T& front() const //返回隊頭{return _con.front();}T& front() //返回隊頭{return _con.front();}const T& back() const  //返回隊尾{return _con.back();}T& back()  //返回隊尾{return _con.back();}private:Container _con; //適配器適配數據結構};
}

三、模擬實現stack

stack是先進先出的數據結構。

#pragma once
#include <deque>
using namespace std;namespace stl
{template<class T, class Container = deque<T>>class stack{public:void push(const T& x) //入棧{_con.push_back(x);}void pop()  //出棧{_con.pop_back();}void size() const  //元素個數{return _con.size();}bool empty() const  //判空{return _con.empty();}const T& top() const  //返回棧頂{return _con.back();}T& top() //返回棧頂{return _con.back();}private:Container _con;};
}