【C++】编程必备：深入解析stack和queue的使用和实现(附源码)
如果还没有了解过stack和queue是什么的小伙伴推荐看这个博客扫一下盲，然后再来看这篇文章就好理解多了，文章：栈的定义与实现、队列的定义与实现
文章目录
一、stack的使用
栈和队列的使用非常简单，只有几个接口，并且还和我们之前学习的容器类似，我们首先来看看stack的接口 有哪些：
其中的emplace可以先不管，其它接口的含义都很明确，分别是empty(判空)、size(有效数据个数)、top(取栈顶元素)、push(入栈)、pop(出栈)
这里我们简单演示一下就好，今天的重点在它们的实现，如下：
#include <iostream>
#include <stack>
int main()
{
std::stack<int> st;
//给栈插入一些元素
st.push(1);
st.push(2);
st.push(3);
st.push(4);
std::cout << "size:" << st.size() << std::endl;
//栈不为空就一直取栈顶元素打印，直到栈为空
while (!st.empty())
{
std::cout << st.top() << " ";
st.pop();
}
std::cout << std::endl;
std::cout << "size:" << st.size() << std::endl;
return 0;
}
运行结果为：
二、queue的使用
接下来我们来看看queue有哪些接口，如下：
queue和stack接口上的区别就是多了一个front，既可以取出队列的尾元素，也可以取出队列的头元素，简单举个例就好，如下：
#include <iostream>
#include <queue>
int main()
{
std::queue<int> q;
//给栈插入一些元素
q.push(1);
q.push(2);
q.push(3);
q.push(4);
std::cout << "size:" << q.size() << std::endl;
//栈不为空就一直取栈顶元素打印，直到栈为空
while (!q.empty())
{
std::cout << q.front() << " ";
q.pop();
}
std::cout << std::endl;
std::cout << "size:" << q.size() << std::endl;
return 0;
}
运行结果如下：
三、容器适配器的概念
什么是容器适配器
容器适配器是一种特殊的容器，它并不像普通容器那样独立实现数据结构，而是基于其他已有的容器（如 vector、deque 或 list）来提供特定的接口和功能，简单来说，它就像是一个 “包装器”，通过调整已有容器的接口，使其满足特定的使用场景
比如stack，它的底层其实就是一个数组，只是它只能对最后面的数据进行操作，那么我们就可以使用vector去巧妙的实现stack，stack需要的接口vector都有，我们只需要封装需要的接口，不需要的接口不管就好了
又比如queue，因为队列是头删，所以底层使用链表(顺序表头删比较慢)，那么我们就可以使用list去实现queue，同样只实现我们需要的接口
这就是容器适配器大致的解释，也就是属于容器适配器的容器都可以巧妙的借助其它容器进行实现，大大提高了效率
STL中的stack和queue
我们来看看cpp网站中stack和queue的定义：
可以看到它们的前一个模板参数都是数据类型T，而后面这个模板参数则是放的一个容器，这个容器默认是deque（双端队列），它的设计比较复杂
它的核心优势在于兼顾了数组的随机访问效率和链表的动态扩容能力，尤其适合需要频繁在两端操作的场景，在需要一个 “既能快速排队，又能快速插队” 的数据结构时，deque就很好用
有了这个数据结构，我们就实现stack和queue就可以统一使用deque做它们的底层容器了，但是由于它的底层比较复杂，我们就不过多介绍，我们实现stack和queue就使用vector和queue作为底层就够了，我们只需要了解一下deque
四、stack的实现
stack的结构
上面说了那么多，我们终于可以开始着手stack和queue的实现了，过程比想象中更加简单，首先我们需要两个模板参数，一个是底层存放数据的类型，一个是底层的容器，stack的底层容器我们选择vector，如下：
#include <vector>
namespace TL
{
template<class T, class Container = std::vector<T>>
class stack
{
public:
private:
Container _con;
};
}
这里我们默认使用了vector作为stack的底层容器，当然，用户自己传容器过来也行，但是要保证他传的容器能够支持后续的操作，当然，这个是用户考虑的事情，我们不用管
这里我们使用这个容器定义了一个对象，接下来外面用户对栈的操作，我们就可以转化为对这个底层对象的操作，接下来我们开始实现栈，非常爽
默认成员函数
由于stack内部只有一个成员变量，是一个容器的对象，没有堆上的资源需要我们手动释放和拷贝，至于这个容器对象内部的资源管理，是这个容器自己内部的事情，我们不用管
我们需要做的就是直接调用这个容器自己的各种默认成员函数，并且我们不需要手动去做，因为如果我们不写默认成员函数，那么编译器默认生成的默认成员函数，就会自动调用自定义类型对象的默认成员函数，所以最后的结论就是，stack不需要写默认成员函数，编译器帮我们自动生成的就够用了
empty和size
stack的判空和有效数据个数就是底层vector的判空和有效数据个数，如下：
//不需要写那几个默认成员函数，因为编译器自动生成的就够用了
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
是不是非常简单呢？我们直接复用内部容器的成员函数即可
push和pop
栈的push相当于就是vector的尾插，pop也相当于尾删，如下：
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
//直接删除就可以了，如果出错，_con内部会处理
_con.pop_back();
}
top和swap
取栈顶元素其实就是取vector的尾部元素，swap就是调用底层容器的swap如下：
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}
//类内
void swap(stack& st)
{
_con.swap(st._con);
}
//类外
template<class T, class Container = std::vector<T>>
void swap(stack<T>& st1, stack<T>& st2)
{
st1.swap(st2);
}
测试
#include <iostream>
#include "stack.h"
int main()
{
TL::stack<int> st;
//给栈插入一些元素
st.push(1);
st.push(2);
st.push(3);
st.push(4);
std::cout << "size:" << st.size() << std::endl;
//栈不为空就一直取栈顶元素打印，直到栈为空
while (!st.empty())
{
std::cout << st.top() << " ";
st.pop();
}
std::cout << std::endl;
std::cout << "size:" << st.size() << std::endl;
return 0;
}
运行结果：
可以看到我们实现的栈运行这段代码和std的栈运行这段代码的栈没有区别，这就是栈的实现，是不是非常简单呢？
源码
#pragma once
#include <vector>
namespace TL
{
template<class T, class Container = std::vector<T>>
class stack
{
public:
//不需要写那几个默认成员函数，因为编译器自动生成的就够用了
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
//直接删除就可以了，如果出错，_con内部会处理
_con.pop_back();
}
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}
void swap(stack& st)
{
_con.swap(st._con);
}
private:
Container _con;
};
template<class T, class Container = std::vector<T>>
void swap(stack<T>& st1, stack<T>& st2)
{
st1.swap(st2);
}
}
五、queue的实现
接下来我们开始queue的实现，它的原理和stack差不多，只不过它的底层我们默认使用链表，它的结构如下：
#pragma once
#include <list>
namespace TL
{
template<class T, class Container = std::list<T>>
class queue
{
public:
//不需要写那几个默认成员函数，因为编译器自动生成的就够用了
private:
Container _con;
};
}
empty和size
和stack一样，如下：
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
push和pop
这里稍微和stack有些不同，因为stack的push和pop相当于对vector的尾插和尾删，而queue的push和pop则相当于对list的尾插和头删，因为栈是先进后出，而队列是先进先出，如下：
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
front和back
一个是取队头元素，一个是取队尾元素，如下：
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
swap
和stack的swap实现差不多，如下：
//类内
void swap(queue& q)
{
_con.swap(q._con);
}
//类外
template<class T, class Container = std::list<T>>
void swap(queue<T>& q1, queue<T>& q2)
{
q1.swap(q2);
}
测试
#include <iostream>
#include "queue.h"
int main()
{
TL::queue<int> q;
//给栈插入一些元素
q.push(1);
q.push(2);
q.push(3);
q.push(4);
std::cout << "size:" << q.size() << std::endl;
//栈不为空就一直取栈顶元素打印，直到栈为空
while (!q.empty())
{
std::cout << q.front() << " ";
q.pop();
}
std::cout << std::endl;
std::cout << "size:" << q.size() << std::endl;
return 0;
}
源码
#pragma once
#include <list>
namespace TL
{
template<class T, class Container = std::list<T>>
class queue
{
public:
//不需要写那几个默认成员函数，因为编译器自动生成的就够用了
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
void swap(queue& q)
{
_con.swap(q._con);
}
private:
Container _con;
};
template<class T, class Container = std::list<T>>
void swap(queue<T>& q1, queue<T>& q2)
{
q1.swap(q2);
}
}
那么今天关于list的实现就讲到这里，有什么不懂欢迎私信问我，我会及时做出解答，下一篇文章开始我们学习仿函数了，敬请期待吧！
bye~
更多推荐
12
0- 0
已为社区贡献9条内容
所有评论(0)