🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯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;};
}