C++STL之stack和queue容器(详细+通俗易懂)
前言:老铁们好，笔者好久没更新STL的容器了，今天，笔者接着之前的STL容器的内容继续更新，所以今天给老铁们分享的是STL里面的栈和队列的容器的知识。
1.栈的定义
老规矩，我们先来看看C++的官网对stack的介绍文档。
然后我再为老铁们用大白话解释一下文档里面的内容。
1.在数据结构那一门课程中我们就学过，栈具有后进先出的特点，数据只能从栈顶出入，文档中第一点讲的就是这个。
2.栈是作为容器适配器被实现的，什么是容器适配器呢？容器适配器就像一个"转化器"(比如我们的充电线的接口)，它能将现有的容器转化为新的，具有特定功能的东西，例如可以将vector,list…转化为stack
3.底层容器可以是任何容器，只需要满足empty，size，back，push_back，pop_back这些操作即可，如果没有我们自己写的容器，那么会使用标准的容器，例如vector,list…
.
2.stack的使用
我会为老铁们逐一演示stack的常用接口是如何使用的。
首先stack使用，需要包头文件
#include <stack>
栈的定义
stack<int> st;//栈里面数据类型是int型
栈的插入数据
stack<int> st;
//插入1 2 3 4
st.push(1);
st.push(2);
st.push(3);
st.push(4);
栈数据的遍历
这里需要注意一下，栈是没有迭代器的，那么我们该如何遍历栈里面的数据呢？
stack<int> st;
//插入1 2 3 4
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())//判断栈里面的数据不为空
{
int top = st.top();//取栈顶的数据
st.pop();//删除该数据，让栈顶的数据进行迭代
cout << top << endl;
}
代码的预期结果应该是4 3 2 1，那么我们来看看结果吧
结果正确!以上这些结果就是stack里面常用的接口了。
3.队列的定义
还是老规矩，我们先来看看c++官网文档对queue的介绍文档。
1.队列也是一种容器适配器，队列满足先进先出的性质，队列从队头出数据，从队尾入数据。
2.如果底层容器是我们自己设计的话，需要满足以下功能接口，empty，size，front，back，push_back，pop_front。
4.队列的使用
queue的使用和stack的使用一样，都是要包头文件
#include <queue>
队列的定义
queue<int> q;
队列的插入数据
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
队列中数据的遍历
queue也是没有迭代器的，所以queue的遍历操作和stack的遍历操作差不多
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
int top = q.front();//取队头的数据
cout << top << " ";
q.pop();//让队头进行迭代
}
代码的预期结果应该是1 2 3 4,那么我们来看看是不是这样
取队尾的元素
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
cout << q.back() << endl;
求队列元素的个数
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
cout << q.size() << endl;
5.stack的模拟实现
通过以上的知识，我们已经懂得了栈和队列的使用了，那么接下来，我们需要模拟栈和队列的实现了。
首先，我们需要定义一个命名空间，防止和库里面的冲突
namespace ljy
{
}
再声明模板(不懂得可以看模板那一篇博客)
//T表示stack里面数据的类型，Container表示底层的容器
template<class T,class Container>
再定义类模板和声明底层容器的对象
template<class T,class Container>//T表示stack里面数据的类型，Container表示底层的容器
class stack
{
private:
Container _con;//声明底层容器的对象
};
实现插入接口
public:
void push(const T& x)
{
_con.push_back(x);//调用底层容器的插入数据的接口
}
实现删除栈顶数据的接口
void pop()
{
_con.pop_back();//调用底层容器的删掉数据的接口
}
实现求栈的大小
size_t size()
{
return _con.size();//调用底层容器的求数据个数的接口
}
实现栈判空
bool empty()
{
return _con.empty();//调用底层容器的判断是否为空的接口
}
实现取栈顶的数据
T& top()
{
return _con.back();//栈是后进先出
}
测试代码1
void test_stack1()
{
//定义一个栈，底层容器是数组
stack<int, vector<int>> st1;
st1.push(1);
st1.push(2);
st1.push(3);
while (!st1.empty())
{
int top = st1.top();
cout << top << " ";
st1.pop();
}
cout << endl;
}
执行代码看看有没有问题
#include "stack.h"
int main()
{
ljy::test_stack1();
return 0;
}
测试代码2
void test_stack2()
{
//定义一个栈，底层容器是数组
//stack<int, vector<int>> st1;
//定义一个栈，底层容器是链表
stack<int, list<int>> st1;
st1.push(1);
st1.push(2);
st1.push(3);
while (!st1.empty())
{
int top = st1.top();
cout << top << " ";
st1.pop();
}
cout << endl;
}
#include "stack.h"
int main()
{
ljy::test_stack2();
return 0;
}
结论:无论是数组还是链表都可以作为底层容器来模拟实现栈，所以可以推导出栈就是一个容器适配器!!!
6.queue模拟实现
queue的模拟实现和stack的模拟实现非常相似，只是队尾入，队头出而已。
#pragma once
#include <iostream>
#include <list>
#include <vector>
using namespace std;
namespace ljy
{
template<class T, class Container>//T表示queue里面数据的类型，Container表示底层的容器
class queue
{
public:
void push(const T& x)//队尾入
{
_con.push_back(x);//调用底层容器的插入数据的接口
}
void pop()//队头出
{
_con.pop_front();//调用底层容器的删掉数据的接口
}
size_t size()
{
return _con.size();//调用底层容器的求数据个数的接口
}
bool empty()
{
return _con.empty();//调用底层容器的判断是否为空的接口
}
T& front()//取队头数据
{
return _con.front();//队列是先进先出
}
T& back()//取队尾数据
{
return _con.back();//队列是先进先出
}
private:
Container _con;
};
}
测试代码
void test_queue()
{
queue<int, vector<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
看一下运行结果有没有问题
直接报错了，我们看看报错内容，是头删出问题了，我们知道vector是不支持头删了，因为vector头删需要挪动数据，效率太低了，由于我们实现queue底层是使用vector容器，所有就直接报错了，我们把vector换成list看还有没有问题。
#pragma once
#include <iostream>
#include <list>
#include <vector>
using namespace std;
namespace ljy
{
template<class T, class Container>//T表示queue里面数据的类型，Container表示底层的容器
class queue
{
public:
void push(const T& x)//队尾入
{
_con.push_back(x);//调用底层容器的插入数据的接口
}
void pop()//队头出
{
_con.pop_front();//调用底层容器的删掉数据的接口
}
size_t size()
{
return _con.size();//调用底层容器的求数据个数的接口
}
bool empty()
{
return _con.empty();//调用底层容器的判断是否为空的接口
}
T& front()//取队头数据
{
return _con.front();//队列是先进先出
}
T& back()//取队尾数据
{
return _con.back();//队列是先进先出
}
private:
Container _con;
};
void test_queue()
{
queue<int, list<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
}
换成list就没问题了
7.deque容器
老规矩，我们先来看看有关deque容器的文档。
deque叫双端队列，但它不是队列，而是一种双开口，连续的空间的数据结构，那什么是双开口呢？双开口就是可以在头和在尾插入和删除数据，那么deque相比于vector效率就高很多了，deque相比于list空间的利用率较高。
deque的缺点
我们知道C++是一门极度注重效率的语言，deque虽然结合了list和vector的优点，但是deque并没有完全继承二者的优点，相比于二者各自的优点还是差点意思，所以deque代替不了vector和list
我们可以看看deque的随机访问和vector随机访问相差的时间
总结
以上就是关于STL中的stack和queue的全部内容，希望各位老铁看了这篇文章能有所收获。