C++之栈和队列使用及模拟实现
目录
栈的使用
队列的使用
栈的模拟实现
队列的模拟实现
deuqe容器介绍
在C语言中我们已经学习了栈和队列的相关性质，今天我们主要来学习C++语法中栈和队列的相关概念。
栈的使用
在C++中栈是一种容器适配器，在其内部适配了其它的容器，其相关接口使用适配的容器的相关接口进行实现。什么是适配器呢？下面我们模拟实现的时候会讲述。
栈的主要接口有:push(),pop(),top(),size(),empty().
#include<iostream>
#include<stack>
using namespace std;int main()
{stack<int> s;
//1.往栈中入数据s.push(1);s.push(2);s.push(3);s.push(4);
//2.求栈顶的元素cout<<s.top()<<endl;
//3.删除栈顶的元素s.pop();
//4.判断栈顶是否为空while (!s.empty()){cout << s.top() << " ";s.pop();}cout << endl;
//5.求栈中元素的个数cout << s.size() << endl;return 0;
}
队列的使用
队列和栈一样，也是一个容器适配器。
队列的主要接口有：push(),pop(),front(),back(),size(),empty().
int main()
{queue<int> q;
//向队列中入元素q.push(1);q.push(2);q.push(3);q.push(4);
//获取队列头的数据cout << q.front() << endl;
//获取队列尾的数据cout << q.back() << endl;
//判断队列是否为空，删除队列头部的数据while (!q.empty()){cout << q.front() << " ";q.pop();} cout << endl;
//获取队列的元素的个数cout << q.size() << endl;return 0;
}
栈的模拟实现
上面我们提到了栈是一种容器适配器，下来我们详细讲解一下什么是容器适配器。 我们之前学习过，栈可以是数组栈，也可以是链式栈。所以按照这个思路而言，栈的数据结构中我们完全可以采用vector数组或者list链表作为底层的容器去进行数据的存储以及接口的封装。但是有没有一种方法可以使底层容器既可以是链表也可以是数组呢。这个问题其实就回到了我们之前学习的模板的概念，因为一个模板在实例化时可以被转化为多种类型。所以这个容器适配器本质上其实也是一种模板，不过这个模板一般在实例化时都会被实例化成stl中的容器类型，比如vector，list，string，deque,forward_list等等。stl库中一般采用deque这个双端队列容器，至于为什么，下面我们讲deque时会为大家讲解。
代码如下。
#pragma once
#pragma once
#include<deque>
using namespace std;
namespace yjd
{template<class T, class Container = deque<T>>class stack{public://pushvoid push(const T& x){_con.push_back(x);}//popvoid pop(){_con.pop_back();}//sizesize_t size()const{return _con.size();}//emptybool empty() const{return _con.empty();}//topconst T& top() const{return _con.back();}private:Container _con;};}
队列的模拟实现
#pragma once
#include<deque>
using namespace std;
namespace yjd
{template<class T, class Container = deque<T>>class queue{public://pushvoid push(const T& x){_con.push_back(x);}//popvoid pop(){_con.pop_front();}//sizesize_t size()const{return _con.size();}//emptybool empty() const{return _con.empty();}//frontconst T& front() const{return _con.front();}//backconst T& back() const{return _con.back();}private:Container _con;};}
总的来说，栈和队列的实现都是采用deque容器存储数据，并封装deque的接口成了stack和queue对应的的接口，为什么使用deque容器，下来为大家解释。
deuqe容器介绍
上文说道，stack和queue的容器适配器中我们选择了deque这个容器进行适配，为什么要选择这个容器适配呢？list和vector一样也支持对应的接口，为什么不去使用list和vector这两个容器呢？先来回忆一下vector和list的优缺点。
vector优点：底层物理空间是连续的，所以支持下标随机访问，cpu高速缓存命中率高。高速缓存命中率就是，cpu在访问数据时所需的数据已经加载到高速缓存中的比率。cpu在访问数据时，会先将数据加载到高速缓存中然后再进行访问。因为vector底层是连续的，所以加载第一个元素数据时，会顺便将后面的元素数据全部加载到高速缓存中，所以它的高速缓存命中率高。
vector缺点：头插头删效率低下，往往需要挪动整个数组的数据，复杂度为O(N)。不能按需申请释放空间，扩容时往往会二倍扩容，往往会开出很大的一块空间，造成空间的浪费，释放时会释放整个数组的空所以bu。
list优点：支持任意位置的插入删除，复杂度为O(1)，因为只需要更改指针的指向。按需申请释放空间，比如new一个结点，delete这个结点。
list缺点：物理空间不连续，所以不支持下标随机访问。
再来讲讲deque的结构。图示如下。
deque在底层申请空间时，先申请buffer1这块空间， 假设每个buffer空间可以存储8个元素，当buffer1满了时，在进行尾插时，我们申请了buffer3这块空间，进行元素的插入，要进行头插时，我们申请了buffer2这块空间，进行头插。并且为了保证deque的连续，必须在buffer2的尾部插入，在buffer3的头部进行插入。
中控指针数组中存储的就是每个buffer的地址，且buffer1的地址要放在中间的位置，其它buffer的地址要根据对应buffer的位置进行填入，保证数据的顺序存储。指针数组一般采用vector进行存储。
那么deque作为适配器容器相比vector和list的优点是什么呢？
先抛开deque作为适配容器不谈，我们先来对比deque和vector和list这两个容器。通过deque的底层结构我们可以看出，deque在进行头插时并不像vector那样要移动整个数组的元素，从这一方面来看，deque优于vector容器。且deque也支持重载[]进行随机访问，具体的访问方式为，先判断当前下标是否在第一个buffer里，没有在就先减去第一个buffer中的元素个数，然后进行除和模操作确定这些元素具体的位置，因为每个buffer的空间其实并不是连续的，所以这个随机访问也并不像vector那样随机，随机访问这一点又优于list容器。
所以其实deque是融合了vector和list优点的一个容器，至于为什么没有替代vector和list，是因为deque虽然融合了vector和list的优点，但是并没有将vector和list的优点发挥到极致，比如头插时，又要开辟一大块的空间，而list只需要创建一个节点，更改指针指向。比如[]随机访问，又不像vector那样随机。所以纵使deque融合了vector和list的优点，vector和list在stl容器中的地位仍然是无法撼动的。
deque作为stack和queue的适配器容器较vector和list的优点又是什么呢？
较vector的优势：push_back元素时，空间不够进行扩容，并不会像vector那样扩容二倍，扩完容之后也不会拷贝数据，不会造成空间资源的浪费。
较list的优势：在底层deque的物理结构也是部分连续的，只要是连续的物理空间，那么cpu在访问数据时，cpu的命中效率一定是很高的，而list底层的物理结构不连续，所以cpu命中率不高。其次，不需要像list那样频繁地申请和释放空间，一次开一个buffer的空间，所以申请和释放空间的代价低。
以上便是本期的所有内容。本期的重点为stack和queue的相关接口以及容器适配器的概念，deque这个容器相关内容作为了解即可。
本期内容到此结束^_^