队列的使用以及模拟实现(C++版本)

初阶牛

发布于 2023-10-14 18:08:23

3650

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中) 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:讲解队列的使用以及模拟实现金句分享: ✨来日方长,未来是星辰大海般璀璨,✨ ✨不必踌躇于过去的半亩方塘.✨

一、队列的介绍

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;
    };
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-09-29，如有侵权请联系 cloudcommunity@tencent.com 删除

c++