C++STL详解（六）——stack和queue

空间适配器

适配器是一种设计模式（设计模式是一套被反复使用的，多数人知晓的，经过分类编目的，代码设计经验的总结），该种模式是将一个类的接口转换客户希望的另外一个接口。

虽然stack和queue中也可以存放元素，但在STL中却并没有划分到容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，当我们没有显示传时，STL中stack和queue默认使用deque。
例如：
如果我们定义一个stack，并指定使用vector容器，则定义出来的实际出来的stack就可以
复用vector的接口来实现栈的各个函数接口。

stack

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其只能从容器的一段继续元素的增删操作。

stack的定义方式

方式一：使用STL中默认的适配器定义栈。(默认为deque）

	stack<int> s1;

方式二：使用特定的适配器定义栈

    stack<int, vector<int>> st2;stack<char, vector<char>> st3;

stack的使用

int main()
{stack<int, vector<int>> st1;st1.push(1);st1.push(2);st1.push(3);while (!st1.empty()){cout << st1.top() << endl;st1.pop();}//3 2 1cout << st1.size() << endl;   //0return 0;
}

stack的模拟实现

1：为了体现vector适配器特性，在初始栈的基础上增加一个模板参数Container，并用deque默认容器作缺省值。
2: 根据我们所传的容器类型，就变成指定容器类型的适配器，进而复用指定容器的接口实现stack成员函数，进而实现stack的各种功能。

namespace yzh
{template <class T,class Container = deque<T>>class stack{public://构造，拷贝构造，赋值都不需要。//编译器会调用自定义类型参数。void push(const T& x)    //尾插{_con.push_back(x);            //复用vector的push_back();}void pop()              //尾删{_con.pop_back();             //复用vector的pop_back();}const  T& top() const            //栈顶不可以被修改。return _con.back();         //复用vector的back();}size_t size() const {return _con.size();        //复用vector的size();}bool empty() const{ return _con.empty();        //复用vector的empty；}private:Container _con;};
}

queue

queque是一种容器适配器，专门用具有先进先出的操作的上下文环境中，其只能从容器的一端插入元素，另一端提取元素。

queue的定义方式

定义方式一：使用STL中默认的适配器定义队列。(默认为deque）

queue<int> q1;

定义方式二：使用特定的适配器定义队列。

	queue<int, vector<int>> q2;queue<char, list<char>> q3;

queue的使用

因为queue的接口存在头删和尾插，如果使用vector封装效率太低，所以一般借助lsit来封装。

int main()
{queue<int, list<int>> q1;q1.push(1);q1.push(2);q1.push(3);cout<<q1.back()<<endl;while (!q1.empty()){cout << q1.front() << endl;q1.pop();}//3 2 1cout << q1.size() << endl;   //0return 0;
}

queue的模拟实现

1: queue不能使用vector容器封装，头插尾删效率太低。
2：写两种front和back成员函数是为支持const队列调用const front和const back ，它们的返回值是可读但不可以写的，普通队列调用普通front和普通back，返回值可读可写。

namespace yzh
{template<class T, class Container = deque<T>>class queue{void push(const T& x)                //队尾入队列。{_con.push_back(x);}void pop()                          //对头出队列。{_con.pop_front();}T& front(){return _con.front();}//返回值可以被修改T& back(){return _con.back();}//返回值不可以被修改。T& front(){return _con.top();}const T& back()const{return _con.front();}//不可以被修改。const T& front() const{return _con.front();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}
}