队列的使用以及模拟实现(C++版本)
🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解队列的使用以及模拟实现
金句分享:
✨来日方长,未来是星辰大海般璀璨,✨
✨不必踌躇于过去的半亩方塘.✨
目录
- 一、队列的介绍
- 二、队列的使用
- 🍭练练手(用队列模拟栈)
- 三、队列的模拟实现:
- (1) 浅提一下双端队列`deque`
- (2) 模拟实现
一、队列的介绍
C++中的队列是一种容器，使用队列可以实现先进先出（FIFO）的数据结构。队列可以添加元素到队列的末尾，也可以从队列的开头删除元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的
成员函数来访问其元素。元素从队尾入队列，从队头出队列。
C++中的队列通常使用STL库中的queue类实现。
队列的基本操作包括：
- push(element)：将元素插入队列的末尾。
- pop()：将队列的第一个元素删除。
- front()：返回队列的第一个元素。
- back()：返回队列的最后一个元素。
- empty()：判断队列是否为空。
队列具有先进先出FIFO(First In First Out)
入队列：进行"插入"操作的一端称为队尾
出队列：进行"删除"操作的一端称为队头
二、队列的使用
文档链接
| 接口名 | 解释 |
|---|---|
| empty() | 判断是否为空队列 |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队首元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 将新元素入队列 |
| emplace() | 将新元素入队列 |
| pop() | 将队首元素出队 |
相信大家对队列的基本操作十分简单,下面演示一下具体使用,使用十分简单,就不过分介绍了.
测试代码:
#include <iostream>
#include <queue>
using namespace std;void test1()
{queue<int> q1;//创建一个存储整形数据的队列q1.push(1); //入队列q1.push(2);q1.push(3);q1.emplace(4); //在stack使用时有详细介绍cout << "q1.front=" << q1.front() << endl; //取队头元素cout << "q1.back=" << q1.back() << endl; //取队尾元素//利用front的返回值,修改队首元素int& top = q1.front();top = 22;//利用back的返回值,修改队尾元素int& back = q1.back();top = -22;cout << endl;while (!q1.empty()) //只要队列不为空,就打印队头元素和出队列{cout << q1.front() << endl;q1.pop();//出队列}
}int main()
{test1();return 0;
}
运行结果:
q1.front=1
q1.back=4
22
2
3
4
🍭练练手(用队列模拟栈)
题目链接:
同样,在C语言阶段,我们已经"十分痛苦"的写过这道题,现在C++阶段,再来写要轻松很多了.
用队列实现栈(C语言版本)
C++实现版本:
class MyStack {
public:MyStack() {}void push(int x) {if (!(q1.empty() && q2.empty())) {//往空栈里面插入数据q1.push(x);}else q2.push(x);}int pop() {queue<int>* empty_q ;queue<int>* un_empty_q;if (q1.empty()) {//找到两个队列中的空队列empty_q = &q1;un_empty_q = &q2;}else {empty_q = &q2;un_empty_q = &q1;}while (un_empty_q->size() > 1) {//将非空队列除了最后一个元素以外,其他全部插入到另一个队列empty_q->push(un_empty_q->front());un_empty_q->pop();}int front = un_empty_q->front();un_empty_q->pop();//删除剩下的最后一个元素->return front;}int top() {int top;if (q1.empty()) {top = q2.back();}else top = q1.back();return top;}bool empty() {return q1.empty() && q2.empty();}
private:queue<int> q1;queue<int> q2;
};
三、队列的模拟实现:
(1) 浅提一下双端队列deque
在介绍队列的,模拟实现前,先介绍一下deque.
双端队列（Double-Ended Queue），是一种具有队列和栈的特点的数据结构。它允许从两端插入和删除元素，具有以下特点：
- 可以从队列两端进行插入和删除操作。
- 支持常数级别的访问和修改元素，即在队列头和尾进行操作的时间复杂度都为O(1)。
- 在中间进行操作时，性能较差，时间复杂度为O(n)。
是的,这个双端队列不仅支持头插头删,尾插尾删的同时,还支持随机访问.
那这不就意味着链表list和vector都被淘汰了吗?
这里就不过多介绍deque的底层了,我们可以暂时理解为,类似于链表,但是链接起来的是一个个数组,这样就实现了这些功能.
但是,他并不能代替链表list和vector.原因如下:
与vector比较
deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不
需要搬移大量的元素
劣势:但是它的访问需要计算,在大量访问元素的场景时,与vector比就落后了.
与list比较
优势:其底层是连续空间，空间利用率比较高，不需要存储额外字段。
缺点:deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多.
巧合的是,stack和queue都不需要访问中间的元素,访问头部数据效率还是很高的.
所以STL用deque作为stack和queue的底层数据结构再合适不过了.
(2) 模拟实现
队列也是一种容器适配器,我们底层采用deque实现还是很轻松的.
#pragma once
#include <iostream>
#include <deque>
using namespace std;namespace cjn
{template<class T, class Con = deque<T>>//默认采用deque进行复用class queue{public:queue(){}void push(const T& x){ //入队列元素相当于尾插_c.push_back(x);}void pop(){_c.pop_front(); //出队列是从队首元素出队,所以相当于头删}T& back(){ //返回队尾元素return _c.back();}const T& back()const{return _c.back();}T& front(){ //返回队首元素return _c.front();}const T& front()const{return _c.front();}size_t size()const{ //返回队列中有效元素的个数return _c.size();}bool empty()const{ //判断队列是否为空return _c.empty();}private:Con _c;};
}