stack和queue模拟实现

一.介绍

1.stack的类模板

LIFO：后进先出

2.queue的类模板

FIFO：先进先出

3.容器适配器

在stack与queue的介绍中，都有介绍其是容器适配器(container adaptor)的一种，对于适配的模式，反向迭代器也使用了同样的思想

template <class T, class Container = deque<T> > 

其模板参数中Container就是其所适配的类的类型，缺省参数为deque类

二. deque类

使用STL中的deque时需要包含头文件#include <deque>，并用std::命名空间

1. 简介

deque：是双端队列(double-ended queues)，可以在头尾两端进行插入和删除。

示例：下图中，先尾插 1 2 3 4 5，再头插 0 -1。后的结构图示

详细可见另一篇博主的优质好文：deque(双端队列)容器

是由于容器vector与liste其各有优点

vector：随机访问([])，效率高

list：插入删除，效率高

因此，有大佬期望能够结合这两个容器的优点来设计一个新的容器，于是deque就诞生了。

deque：头尾插入效率高，不需要移动元素；支持随机访问(但比vecotr的效率低)。

但是其也有自身的缺陷：在中间插入元素时，也需要挪动数据，效率低；不适合遍历（需要检查并转跳到其他的小空间buffer）。

因此，在实际中，可能经常需要遍历，大多数情况下，还是回优先考虑vector或list。deque的使用并不多，目前的一个就是：在STL中，被用来作为stack和queue的底层数据结构。

2.常用成员函数

三. stack模拟实现

1.成员函数

2.代码

#include <deque>
namespace yyjs
{template<class T, class Container = std::deque<T>>class stack{public: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:Container _c;};   
}

可以发现，对于stack类的模拟实现，都是对其Container类型的成员变量进行的适配

四.queue的模拟实现

1.成员函数

2.代码

#include <deque>namespace yyjs
{template<class T, class Container = std::deque<T>>class queue{public: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:Container _c;};
}

对于queue类的模拟实现，也是对其Container类型的成员变量进行的适配

五.小结

1.容器适配器

对于stack或queue的使用时，对于第二个模板参数可以不传参，也可以指定其底层数据结构

//<int ,deque<int>>
stack<int> sti;
//<int, vector<int>>
stack<int, std::vector<int>> stiv;

需要Container类中实现的有stack成员函数里所调用的empty()、size()、push_back()、pop_front()等函数，才能做为第二个模板参数传入。但是一般不传参，使用deque。

queue同上

---

🦀🦀观看~~