STL容器适配器 -- stack和queue（使用+实现）（C++）

栈和队列数据结构+画图分析如果对栈和队列的结构不了解的，可以先看该链接的内容

stack

使用stack时需要头文件#include<stack>

stack的介绍

stack是一种容器适配器，用于具有后进先出(LIFO)的环境中。只能从容器的一端（栈顶），执行删除、插入和提取操作。

stack是作为容器适配器实现的，容器适配器是对特定容器类封装，作为其底层的容器。vector、deque、list均符合特定的底层容器需求，如果没有指定特定的底层容器，默认使用deque

stack的使用

函数	接口说明
stack()	构造空的栈
empty()	判断栈是否为空
size()	返回栈中的元素个数
top()	返回栈顶元素的引用
push()	将val压栈
pop()	出栈顶元素

test:

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << st.size() << endl;while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;
}

注意：从栈的接口可以看出，栈实际是一种特殊的vector，使用vector完全可以模拟实现stack

stack的实现

stack接口的实现是对deque容器接口的封装。

#include <deque>namespace kpl
{//容器可以使用vector,deque容器在本博客最后一个知识点介绍//template<class T, class Container = vector<T>>//template<class T, class Container = list<T>>template<class T, class Container = deque<T>>class stack{public:stack(){}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

queue

使用queue时需要头文件#include<queue>

queue的介绍

queue是一种容器适配器，用于具有先进先出(FIFO)的环境中。从容器的一端插入元素，另一端提取元素。

queue作为容器适配器实现，容器适配器是对特定容器类封装，作为其底层的容器。deque、list符合特定的底层容器需求，如果没有为queue实列化指定特定的底层容器，默认使用deque

queue的使用

函数	接口说明
queue()	构造空的队列
empty()	判断队列是否为空
size()	返回队列中的元素个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将val入列
pop()	在队头元素出队列

test:

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << "size:" << q.size() << endl;cout << "front:" << q.front() << endl;q.pop();cout << "back:" << q.back() << endl;while (!q.empty()){cout << "front:" << q.front() << " ";q.pop();}cout << endl;
}

queue的实现

因为queue的接口有头插和尾插，使用vector封装效率底，所以可以借助list模拟实现。这里我们依旧使用的默认容器deque

queue接口的实现是对deque容器接口的封装。

#include <deque>namespace kpl
{//template<class T, class Container = list<T>>template<class T, class Container = deque<T>>class queue{public:queue(){}bool empty(){return _con.empty();}size_t size(){return _con.size();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}private:Container _con;};
}

deque

简单介绍deque（双端队列）

概念：是一种双开口“连续”空间的数据结构。

双开口

连续打引号的原因

原因：deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成，分段连续。

deque底层结构

deque的迭代器封装结构（复杂）

deque的优缺点

deque的优缺点决定了它适合当stack和queue的底层数据结构

1. stack和queue不需要遍历（deque不适合遍历），只需要在固定的一端或者两端操作即可。
2. stack元素在增长时，deque比vector的效率高（不需要搬移数据），queue元素在增长是，内存使用率高，效率也高。