---

前言

模拟实现STL的stack、queue、deque等的介绍

---

一、模拟实现stack

STL的stack是通过增加一个容器的模板参数，不直接实现栈，让容器存储数据，并调用容器的接口实现栈

namespace hhb
{template <class T, class Container>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}bool empty(){return _con.empty();}T& top(){return _con.back();}size_t size(){return _con.size();}private:Container _con;};}

此时使用stack时，需要传两个模板参数一个是数据类型，一个是容器的类型

• 这种方式可以很方便的切换 vector 栈和 list 栈

void test1()
{hhb::stack<int, vector<int>> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);st1.push(5);while (!st1.empty()){cout << st1.top() << " ";st1.pop();}cout << endl;cout << st1.size() << endl;hhb::stack<int, list<int>> st2;st2.push(1);st2.push(2);st2.push(3);st2.push(4);st2.push(5);while (!st2.empty()){cout << st2.top() << " ";st2.pop();}cout << endl;cout << st2.size() << endl;
}

二、模拟实现queue

STL的queue是通过增加一个容器的模板参数，不直接实现队列，让容器存储数据，并调用容器的接口实现队列

namespace hhb
{template <class T, class Container>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){//_con.erase(_con.begin());_con.pop_front();}T& front(){return _con.front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

使用queue需要传入两个模板参数，一个是数据类型，一个是容器类型

• 可以使用 list 队列 也可以使用 vector 队列， 但是不建议使用vector队列，因为队列是先进先出（FIFO），需要头删，vector 的头删效率不高，只能使用erase函数来实现头删。

void test2()
{//hhb::queue<int, vector<int>> q1;//q1.push(1);//q1.push(2);//q1.push(3);//q1.push(4);//q1.push(5);//while (!q1.empty())//{//	cout << q1.front() << " ";//	q1.pop();//}//cout << endl;//cout << q1.size() << endl;hhb::queue<int, list<int>> q2;q2.push(1);q2.push(2);q2.push(3);q2.push(4);q2.push(5);while (!q2.empty()){cout << q2.front() << " ";q2.pop();}cout << endl;cout << q2.size() << endl;
}

三、 deque

这是一个非常全面的容器，它的接口如下：

既可以下标访问，又可以头插头删，尾插尾删。
但是它的下标访问效率不高，而且中间插入数据效率很低。
因为deque的结构是一个中控（指针数据）存每个数组的指针，每个数组一样的大小如下：

基于以上的性质它只适合头插头删除，尾插尾删，所以它可以很好地适配栈和队列的容器， 所以可以用deque来作为stack 和 queue 的容器模板的缺省参数。

namespace hhb
{template <class T, class Container = deque<T>> // 缺省参数class stack{public:void push(const T& x){_con.push_back(x);}// ....private:Container _con;};}

---

namespace hhb
{template <class T, class Container = deque<T>> // 给定缺省参数class queue{public:void push(const T& x){_con.push_back(x);}// .....private:Container _con;};
}

此时，使用stack 和 queue 只需要一个模板参数即可，即数据的类型。

void test3()
{hhb::stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;cout << st.size() << endl;hhb::queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;cout << q.size() << endl;
}

---

总结

模拟实现STL的stack、queue、deque等的介绍