当前位置：首页 > news >正文

Lesson12---queue

news 2024/10/28 9:37:38

Lesson12—queue

本篇博客介绍了c++queue的介绍使用以及模拟实现

文章目录

Lesson12---queue
前言
一、queue的成员函数
- 1 queue
- 2.empty
- 3.size
- 4.front
- 5.back
- 6.push
- 7.pop
二、相关题目
三、模拟实现
- 完整代码
四、deque（双端队列）
总结

前言

queue的文档:https://cplusplus.com/reference/queue/queue/
翻译：

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端
提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：
标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

提示：以下是本篇文章正文内容，下面案例可供参考

一、queue的成员函数

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
常用的就这些，和我上一篇的stack一模一样只不过一个是先进后出一个是先进先出

1 queue

在这里插入图片描述
就构造一个空队列

2.empty

检查这个队列是不是空的，返回值是一个布尔类型

在这里插入图片描述

3.size

返回队列有多少个值
在这里插入图片描述

4.front

取队头的数据，这里就和栈不一样，栈是top，这里要特殊记一下
在这里插入图片描述

5.back

取队尾的数据
在这里插入图片描述

6.push

在这里插入图片描述

7.pop

出数据，这里是先进先出
在这里插入图片描述

插入一个数据

二、相关题目

二叉树的层序遍历：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
在这里插入图片描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution
{
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q;if(root == nullptr){return vv;}q.push(root);int leveSzie = 1;while(!q.empty()){vector<int> v;while(leveSzie--){TreeNode* front = q.front();v.push_back(q.front()->val);q.pop();if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}vv.push_back(v);leveSzie = q.size(); }return vv;}
};

三、模拟实现

queue是先进先出，需要头删和尾插，但是呢vector并没有头删函数，主要原因是因为vector头删效率太低了，这里用deque来实现

基本框架

#pragma once
#include<bits/stdc++.h>
template<class T,class Container=deque<T>>
class my_queue
{
private:Container _con;
};

完整代码

#pragma once
#include<bits/stdc++.h>
template<class T,class Container=deque<T>> 
class my_queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& back(){return _con.back();}const T& front(){return _con.front();}bool empty(){return _con.empty();}size_t size(){return _con.size();}
private:Container _con;
};