【算法通关指南：数据结构和算法篇（四）】算法里的 “排队系统”：队列的数组模拟 + STL queue 实战

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力 ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

一、队列的概念

队列也是⼀种访问受限的线性表，它只允许在表的⼀端进行插入操作，在另⼀端进行删除操作。 • 允许插入的⼀端称为队尾，允许删除的⼀端称为队头。 • 先进入队列的元素会先出队，故队列具有先进先出(FirstInFirstOut)的特性。

二、队列的模拟实现

2.1创建

• 一个足够大的数组充当队列； • 一个变量h 标记队头元素的前⼀个位置； • 一个变量t标记队尾元素的位置。两个变量(h, t] 是⼀种左开右闭的形式，这样设定纯属个人喜好，因为后续的代码写着比较舒服。，也以h标记队头元素的位置。只要能控制住代码不出现bug ，想怎么实现就怎么实现。

在这里插入图片描述

const int N = 1e6 + 10;
int h, t; //  队头指针，队尾指针
int q[N]; // 队列

2.2 入队

注意：我们依旧从下标为1的位置开始存储有效元素

在这里插入图片描述

// ⼊队
void push(int x)
{
	q[++t] = x;
}

时间复杂度：O(1)

2.3出队

在这里插入图片描述

// 出队
void pop()
{
	h++;;
}

时间复杂度：O(1)

2.4队头

注意：不是h所指的位置，而是h所指的下⼀个位置

在这里插入图片描述

// 队头元素
int front()
{
	return q[h + 1];
}

时间复杂度：O(1)

2.5队尾

在这里插入图片描述

// 队尾元素
int back()
{
	return q[t];
}

时间复杂度：O(1)

2.6判空

在这里插入图片描述

// 队列是否为空
bool empty()
{
	return t == h;
}

时间复杂度：O(1)

2.7有效元素个数

在这里插入图片描述

// 队列的大小
int size()
{
	return t - h;
}

时间复杂度：O(1)

2.8 所有测试代码

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int h, t; //  队头指针，队尾指针
int q[N]; // 队列

// ⼊队
void push(int x)
{
	q[++t] = x;
}

// 出队
void pop()
{
	h++;;
}

// 队头元素
int front()
{
	return q[h + 1];
}

// 队尾元素
int back()
{
	return q[t];
}

// 队列是否为空
bool empty()
{
	return t == h;
}

// 队列的大小
int size()
{
	return t - h;
}
int main()
{
	// 测试
	for (int i = 1; i <= 10; i++)
	{
		push(i);
	}
	while (size()) // while(!empty())
	{
		cout << front() << " " << back() << endl;
		pop();
	}
	return 0;
}

运行结果：

在这里插入图片描述

三、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;
int main()
{
	// 测试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;
	}

	return 0;
}

运行结果：

在这里插入图片描述

总结与每日励志时刻

✨ 本文介绍了队列的概念、实现方法和STL中的queue容器。队列是一种先进先出(FIFO)的线性数据结构，文章详细讲解了如何用数组模拟实现队列，包括入队、出队、获取队头/队尾元素、判空和计算元素个数等操作。同时，文章也介绍了C++标准库queue容器的基本用法和接口函数。队列在算法竞赛中应用广泛，主要关注时间效率，通常采用数组实现。文章还提供了完整的测试代码和运行结果，帮助读者理解队列的实现原理和使用方法。