广扬建设集团网站,h5小游戏制作教程,手表网站欧米茄价格,核酸结果查询#x1f388;个人主页:#x1f388; :✨✨✨初阶牛✨✨✨ #x1f43b;强烈推荐优质专栏: #x1f354;#x1f35f;#x1f32f;C的世界(持续更新中) #x1f43b;推荐专栏1: #x1f354;#x1f35f;#x1f32f;C语言初阶 #x1f43b;推荐专栏2: #x1f354;… 个人主页: :✨✨✨初阶牛✨✨✨ 强烈推荐优质专栏: 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()
{queueint 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.front1 q1.back4 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() {queueint* empty_q ;queueint* 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:queueint q1;queueint q2;
};三、队列的模拟实现:
(1) 浅提一下双端队列deque
在介绍队列的,模拟实现前,先介绍一下deque. 双端队列Double-Ended Queue是一种具有队列和栈的特点的数据结构。它允许从两端插入和删除元素具有以下特点
可以从队列两端进行插入和删除操作。支持常数级别的访问和修改元素即在队列头和尾进行操作的时间复杂度都为O(1)。在中间进行操作时性能较差时间复杂度为O(n)。
是的,这个双端队列不仅支持头插头删,尾插尾删的同时,还支持随机访问. 那这不就意味着链表list和vector都被淘汰了吗? 这里就不过多介绍deque的底层了,我们可以暂时理解为,类似于链表,但是链接起来的是一个个数组,这样就实现了这些功能. 但是,他并不能代替链表list和vector.原因如下:
与vector比较 deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不 需要搬移大量的元素 劣势:但是它的访问需要计算,在大量访问元素的场景时,与vector比就落后了.
与list比较 优势:其底层是连续空间空间利用率比较高不需要存储额外字段。 缺点:deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多.
巧合的是,stack和queue都不需要访问中间的元素,访问头部数据效率还是很高的. 所以STL用deque作为stack和queue的底层数据结构再合适不过了.
(2) 模拟实现
队列也是一种容器适配器,我们底层采用deque实现还是很轻松的. #pragma once
#include iostream
#include deque
using namespace std;namespace cjn
{templateclass T, class Con dequeT//默认采用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;};
}
