💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

💥个人主页：大耳朵土土垚的博客

💥 所属专栏：C++入门至进阶

这里将会不定期更新有关C++的内容，希望大家多多点赞关注收藏💖💖

目录

💞💞 前言1.stack和queue简介2.stack模拟实现✨stack实现代码✨stack测试代码 3.queue模拟实现✨queue实现代码✨queue测试代码 4.结语

1.stack和queue简介

C++中的stack（栈）和queue（队列）是两种常见的数据结构，用于存储和管理数据。

栈是一种先进后出（LIFO）的数据结构，类似于我们平时堆叠的一摞书，只能在顶部进行操作。在C++中，可以使用std::stack模板类来创建栈。栈的主要操作包括压入（push）元素到栈顶、弹出（pop）栈顶元素以及获取栈顶元素等。

队列是一种先进先出（FIFO）的数据结构，类似于排队等候的人群，新元素插入队尾，最早插入的元素在队头。在C++中，可以使用std::queue模板类来创建队列。队列的主要操作包括插入（push）元素到队尾、删除（pop）队头元素以及获取队头元素等。

如下图所示：

stack和queue都有自己的特点和适用场景。栈常用于实现递归算法、表达式求值和括号匹配等问题，而队列常用于实现广度优先搜索（BFS）算法、任务调度和缓冲区管理等问题。

在C++中，stack和queue都是基于deque（双端队列）实现的，默认使用deque容器作为底层数据结构。此外，C++还提供了其他数据结构，如priority_queue（优先队列）和deque（双端队列），可以根据具体需求选择合适的数据结构来解决问题。

2.stack模拟实现

stack函数	作用
push	尾插（栈顶入栈）
pop	尾删（栈顶出栈）
top	获取栈顶元素(也就是尾部元素)
const top	给const对象使用
size	栈中元素个数
empty	判断栈是否为空

stack模拟实现我们就可以使用之前学习过的vector或者list容器来实现，可以创建一个类模板，除了数据的类型可以改变，其使用的容器也可以改变，代码如下：

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

这样我们只需要传入数据类型以及使用的容器类型就可以确定stack是使用什么容器来实现存储和管理数据了🥳🥳，默认传入的是deque容器(给的是缺省值)

deque（双端队列）是C++标准库中的一种容器，它可以在两端进行插入和删除操作。deque的全称是double-ended queue，它融合了向量（vector）和双向链表（doubly linked list）的特性。

使用deque记得包含头文件#include<deque>

✨stack实现代码

#pragma onceusing namespace std;#include<iostream>#include<deque>#include<vector>namespace tutu_stack{ template<class T, class Con = deque<T>> class stack { public: stack() { //使用自定义类型默认的构造函数即可 } //尾插 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: Con _c; };}

stack的构造，因为是使用STL标准库里的容器来实现，所以我们只需要调用标准库里给的构造函数即可，因为类的默认构造会自动调用自定义类型的默认构造，所以这里的默认构造可以不写，栈是使用标准库里的容器来存储数据的，所以不需要手动实现拷贝

✨stack测试代码

//测试代码 void test_stack() { stack<int,vector<int>> s; s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty()) { cout << s.top() << " "; s.pop(); } }

注意测试代码要包含在自己的命名空间中哦，我们这里显示的将容器给了vector来存储数据，记得要包含vector的头文件#include<vector>

3.queue模拟实现

queue的实现与vector非常类似

queue函数	作用
push	队尾入队列
pop	队头出队列
front	获取队头元素
const front	const对象使用
back	获取队尾元素
const back	const对象使用
size	获取队列元素个数
empty	判断队列是否为空
swap	交换两个队列

与stack类似，它也使用了类模板 template<class T, class Container = std::deque<T>>并给了缺省值，使用deque（双端队列），同样其构造函数也不需要写，直接调用自定义类型的默认构造即可，队列是使用标准库里的容器来存储数据的，所以不需要手动实现拷贝

✨queue实现代码

using namespace std;#include<iostream>#include<deque>#include<vector>#include<list>namespace tutu_queue{ 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& front() { return _c.front(); } const T& front() const { return _c.front(); } //获取队尾元素 T& back() { return _c.back(); } const T& back() const { return _c.back(); } //获取队列中有效元素个数 size_t size() const { return _c.size(); } //判断队列是否为空 bool empty() const { return _c.empty(); } //交换两个队列中的数据 void swap(queue<T, Container>& q) { _c.swap(q._c); } private: Container _c; }; }

✨queue测试代码

//测试代码//使用list容器 void test_queue2() { 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(); } }

测试代码要在自己的命名空间里面，使用list容器记得要包头文件#include<list>

结果如下：

这里注意不能使用vector容器，因为vector没有pop_front()这个函数，除非使用erase删除第一个元素，但是这样需要挪动数据，效率很低，所以一般不使用vector作为容器

4.结语

栈和队列是常用的数据结构，可以使用数组或链表来实现，这里我们提了一种类模板，方便我们传入要实现的容器。使用栈和队列非常方便，它们具有高效的性能和覆盖各种操作的方法。可以根据需要调用相关函数来完成相关的操作。以上就是今天所有的内容啦~ 完结撒花~ 🥳🎉🎉