C++基础：模拟实现queue和stack。底层：适配器

引言

模拟实现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;};
}