【算法通关指南：数据结构和算法篇】算法里的 “排队系统”：队列的数组模拟 + STL queue 实战
🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨ 永远相信美好的事情即将发生
文章目录
前言
本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力
ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长
一、队列的概念
队列也是⼀种访问受限的线性表，它只允许在表的⼀端进行插入操作，在另⼀端进行删除操作。
• 允许插入的⼀端称为队尾，允许删除的⼀端称为队头。
• 先进入队列的元素会先出队，故队列具有先进先出(FirstInFirstOut)的特性。
二、队列的模拟实现
2.1创建
• 一个足够大的数组充当队列；
• 一个变量h 标记队头元素的前⼀个位置；
• 一个变量t标记队尾元素的位置。两个变量(h, t] 是⼀种左开右闭的形式，这样设定纯属个人喜好，因为后续的代码写着比较舒服。，也以h标记队头元素的位置。只要能控制住代码不出现bug ，想怎么实现就怎么实现。
constint N =1e6+10;int h, t;// 队头指针，队尾指针int q[N];// 队列2.2 入队
注意：我们依旧从下标为1的位置开始存储有效元素
// ⼊队voidpush(int x){ q[++t]= x;}时间复杂度：O(1)
2.3出队
// 出队voidpop(){ h++;;}时间复杂度：O(1)
2.4队头
注意：不是h所指的位置，而是h所指的下⼀个位置
// 队头元素intfront(){return q[h +1];}时间复杂度：O(1)
2.5队尾
// 队尾元素intback(){return q[t];}时间复杂度：O(1)
2.6判空
// 队列是否为空 bool empty(){return t == h;}时间复杂度：O(1)
2.7有效元素个数
// 队列的大小intsize(){return t - h;}时间复杂度：O(1)
2.8 所有测试代码
#include<iostream> using namespace std;constint N =1e6+10;int h, t;// 队头指针，队尾指针int q[N];// 队列// ⼊队voidpush(int x){ q[++t]= x;}// 出队voidpop(){ h++;;}// 队头元素intfront(){return q[h +1];}// 队尾元素intback(){return q[t];}// 队列是否为空 bool empty(){return t == h;}// 队列的大小intsize(){return t - h;}intmain(){// 测试for(int i =1; i <=10; i++){push(i);}while(size())// while(!empty()){ cout <<front()<<" "<<back()<< endl;pop();}return0;}运行结果：
三、queue
（1）如何创建？
（2）里面提供了什么函数接口？
（3） 每个函数的功能以及时间复杂度
3.1 如何创建
queue<T> q; T ：可以是任意类型的数据。 3.2容器相关接口
3.2.1 size / empty
(1) size ：返回队列⾥实际元素的个数；
(2) empty ：返回队列是否为空。
时间复杂度：O(1)
3.2.2 push / pop
（1） push ：入队；
（2）pop：出队。
时间复杂度：O(1)
3.2.3 front / back
（1） front ：返回队头元素，但不会删除；
（2） b ack ：返回队尾元素，但不会删除
时间复杂度： O(1)
3.3测试所有接口
#include<iostream>#include<queue> using namespace std;typedef pair<int,int> PII;intmain(){// 测试queue queue<PII> q;for(int i =1; i <=10; i++){ q.push({ i, i *10});}while(q.size())// while(!q.empty()){auto t = q.front(); q.pop(); cout << t.first <<" "<< t.second << endl;}return0;}运行结果：
总结与每日励志时刻
✨ 本文介绍了队列的概念、实现方法和STL中的queue容器。队列是一种先进先出(FIFO)的线性数据结构，文章详细讲解了如何用数组模拟实现队列，包括入队、出队、获取队头/队尾元素、判空和计算元素个数等操作。同时，文章也介绍了C++标准库queue容器的基本用法和接口函数。队列在算法竞赛中应用广泛，主要关注时间效率，通常采用数组实现。文章还提供了完整的测试代码和运行结果，帮助读者理解队列的实现原理和使用方法。
