C++——StackQueue

一Stack

1介绍

2接口

3模拟实现

4栈的oj题

二Queue

1介绍

2接口

3模拟实现

三容器适配器

1再谈栈和队列

四优先级队列

1接口

编辑

2仿函数

五dequeue的简单介绍

一Stack

1介绍

先来看看库中对栈的介绍：

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2接口

bool empty() const;   判断栈中是否为空

size_type size() const;   返回栈中元素的个数

value_type& top();        返回栈顶的元素

void push (const value_type& val);   往栈中压入val

void pop();    删除栈顶元素

3模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

#include<vector>
namespace bite
{template<class T>class stack{public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top()const { return _c.back(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:std::vector<T> _c;}
}

4栈的oj题

1 最小栈
2 栈的压入、弹出序列

3 逆波兰表达式求值

1 最小栈

二Queue

1介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素：元素从队尾入队列，从队头出队列
3. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2接口

bool empty() const;         判断队列中是否为空

size_type size() const;     返回队列中的个数

value_type& front();        返回队头元素

value_type& back();         返回队尾元素

void push (const value_type& val);     在队尾中插入元素

void pop();                 删除队头元素

3模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现

#include <list>
namespace bite
{template<class T>class queue{public:queue() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_front(); }T& back() { return _c.back(); }const T& back()const { return _c.back(); }T& front() { return _c.front(); }const T& front()const { return _c.front(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:std::list<T> _c;}
}

三容器适配器

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

1再谈栈和队列

虽然栈和队列也可以存储元素，但在stl中没有把它们划分在容器行列里，而是将它们叫做容器适配器，它们的实现是通过别的容器来实现的：实现的模板中传入了容器参数：

以栈为例：

按照上面来完善stack的模拟实现：

template<class T,class Container = deque<T>>//库中给出的缺省值是deque<T>
class Stack
{
public:bool empty(){return _v.empty();}size_t size(){return _v.size();}const T& top(){return _v.back();}void push(const T& x){_v.push_back(x);}void pop(){_v.pop_back();}
private:Container _v;
};

知道了这一点，我们在使用stack时想用那个容器来实现都可以~

四优先级队列

1使用优先级队列与队列一样，需要在前面包含#incldue<queue>才能使用

2优先级队列里面的排序是(默认)以大堆的排序来实现的vector类型的队列

3需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

1接口

bool empty() const;                   判断是否为空

size_type size() const;               返回个数

const value_type& top() const;        返回队头元素

void push (const value_type& val);    队尾插入元素

void pop();                            删除队头元素

使用这些接口：

我们发现：打印出来的顺序是降序的：我们在堆排序中说了：建大堆是排升序的。这里这么是反过来的？？

这里是在学习中最容易遇到坑的地方；在底层实现的思路：

将数据建大堆，第一个一定是数组中最大的，先把它打印出来；在删除pop时，先把第一个与最后一个交换位置，再进行pop删除最后一个元素——也就是最大的那一个；最后调整数组为大堆...与我们实现堆排序的思想不同！！

如果我们想让它打印出来是升序呢？

在模板中传类型：

和sort传入的greator<int>进行比较：

2仿函数

在类中重载()的方式就叫做仿函数；

上面sort参数中传入greater<int>() 对象与这里是类似的：

3模拟实现

模拟实现优先级队列时可以写仿函数来控制升序降序：

//适配器进行容器调用
namespace bit
{template<class T,class Container = deque<T>>class Stack{public:bool empty(){return _v.empty();}size_t size(){return _v.size();}const T& top(){return _v.back();}void push(const T& x){_v.push_back(x);}void pop(){_v.pop_back();}private:Container _v;};template<class T, class Container = deque<T>>class Queue{public:bool empty(){return _l.empty();}size_t size(){return _l.size();}const T& front(){return _l.front();}const T& back(){return _l.back();}void push(const T& x){_l.push_back(x);}void pop(){_l.pop_front();}private:Container _l;};template<class T>class greater{public:bool operator()(const T& x,const T& y){return x > y;}};template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T,class Container=vector<T>,class Compare = less<T>>class priority_queue{public:bool empty() const{return _pro.empty();}size_t size() const{return _pro.size();}const T& top() const{return _pro[0];}//less -> 降序 -> 建大堆（与HeapSort的逻辑不同）void AjustUp(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child >0){//_pro[parent] < _pro[child]if (com(_pro[parent] , _pro[child])){swap(_pro[child], _pro[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& val){_pro.push_back(val);AjustUp(_pro.size()-1);}void AjustDown(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _pro.size()){//选最大(降序)的child与parent交换 _pro[child] <  _pro[child + 1]          if (child + 1<_pro.size() && com(_pro[child] , _pro[child+1])){child++;}//      _pro[parent] < _pro[child]if (com(_pro[parent] , _pro[child])){swap(_pro[child], _pro[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_pro[0], _pro[_pro.size() - 1]);_pro.pop_back();AjustDown(0);}	private:Container _pro;};