数据结构——队列
- 什么是队列
- 顺序队列
- 链式队列实现
今天我们接着来看队列：
什么是队列
队列是一种基础且广泛应用的数据结构，它具有以下核心特征：
定义：
- 线性表：队列是一种特殊的线性表，其中的元素呈线性排列，每个元素都有一个直接前驱和一个直接后继（除了第一个元素无前驱，最后一个元素无后继）。
操作特性：
- 先进先出 (FIFO)：队列遵循“先进先出”原则，即最早进入队列的元素将最先离开队列。这意味着新元素总是被添加到队列的末端（称为队尾），而删除或访问元素则发生在队列的另一端（称为队头）。
基本操作：
- 入队（Enqueue）：在队尾添加一个新元素。新元素成为队列中的最新成员，并且在任何已存在的元素之后等待被处理。
- 出队（Dequeue）：从队头移除并返回最先进入队列的元素。这个操作确保了队列中最早加入的元素优先被处理。
- 查看队头（Peek 或 Front）：返回队头元素但不移除它，允许查看即将被出队的元素而不改变队列状态。
- 判空（IsEmpty）：检查队列是否为空，即没有任何元素。
实现方式：
- 顺序队列：使用固定大小的数组来存储元素。队头和队尾的索引需要进行适当的调整以确保正确的插入和删除。当队列满时，可能需要循环利用数组空间（环形缓冲区）或动态扩容。
- 链式队列：使用链表结构来存储元素，队头和队尾分别对应链表的首节点和尾节点。链式队列通常更易于处理队列满和队列空的情况，因为节点的增删不受固定数组大小的限制。
应用：
队列在计算机科学和许多实际应用场景中广泛使用，例如：
- 任务调度：安排任务按照提交顺序依次执行。
- 资源管理：如打印机任务队列，请求按照到达顺序打印文档。
- 消息传递：在分布式系统中，消息队列用于异步通信，发送者将消息放入队列，接收者按照消息进入队列的顺序进行消费。
- 缓存失效策略：如最近最少使用 (LRU) 缓存算法可以用双端队列来实现。
- 广度优先搜索 (BFS)：在图算法中，队列用于存储待探索的节点，确保按层级顺序遍历。
总结来说，队列是一个线性数据结构，它按照先进先出的原则组织和管理元素，支持在队尾进行插入（入队）和在队头进行删除（出队）的操作，常用于实现排队、任务调度、消息传递等场景，并可通过数组或链表等方式实现。
顺序队列
我们这里可以用一个数组来模拟队列（就是一个插入删除受限的顺序表）：
#pragma once
#include<iostream>
#include<cassert>
#include<algorithm>
template<class T>
class MyQueue
{
public:
// 默认构造函数，初始容量为 10
MyQueue()
: _capacity(10)
, _size(0)
{
_data = new T[_capacity]; // 分配动态数组，大小为初始容量
}
// 自定义容量的构造函数
MyQueue(const size_t capacity)
: _capacity(capacity)
, _size(0)
{
_data = new T[_capacity]; // 分配动态数组，大小为指定容量
}
// 判断是否需要扩容，并在必要时进行扩容
T* resizeIfNecessary()
{
if (_size >= _capacity) // 当元素数量达到或超过当前容量时，需要扩容
{
size_t newcapceity = _capacity * 2; // 新容量为原容量的两倍
T* tmp = new T[newcapceity]; // 分配新内存
if (tmp == nullptr)
{
exit(EXIT_FAILURE); // 如果内存分配失败，程序终止
}
std::copy_n(_data, _size, tmp); // 将原有数据复制到新内存
delete[] _data; // 释放旧内存
_data = tmp; // 更新数据指针
_capacity = newcapceity; // 更新容量
std::cout<< "has resize!!" << std::endl; // 输出扩容提示信息
}
return _data; // 返回当前数据指针
}
// 在队尾添加一个元素
void push(const T& data)
{
// 判断是否需要扩容并执行扩容操作
resizeIfNecessary();
_data[_size] = data; // 将新元素添加到队尾
_size++; // 增加元素数量
}
// 移除并返回队头元素
T pop()
{
assert(_size > 0); // 断言队列非空
T first = _data[0]; // 保存队头元素
for(int i = 0; i < (int)_size - 1; i++) // 通过元素移动而非元素拷贝的方式移除队头元素
{
_data[i] = _data[i+1];
}
_size--; // 减少元素数量
return first; // 返回已移除的队头元素
}
// 返回队头元素（不移除）
const T& front() const
{
assert(_size > 0); // 断言队列非空
return _data[0]; // 返回队头元素
}
// 判断队列是否为空
bool empty() const
{
return _size == 0; // 若元素数量为 0，则队列为空
}
// 打印队列中的所有元素
void PrintQueue()
{
for(int i = 0; i < _size; i++) // 输出队列中的每个元素
{
std::cout << _data[i] << " ";
}
std::cout<<std::endl; // 输出换行
}
// 析构函数，释放动态数组
~MyQueue()
{
delete[] _data; // 释放动态数组内存
}
private:
T* _data; // 动态数组，用于存储队列元素
size_t _capacity; // 队列当前容量
size_t _size; // 队列当前元素数量
};
链式队列实现
我们这里用带头结点和带尾指针的单链表来实现：
#pragma once
#include<iostream>
#include<cassert>
// 结点类模板
// 用于存储链式队列中的数据元素和指向下一个结点的指针
template<class T>
struct Node
{
// 默认构造函数，初始化数据域为默认构造的T对象，并将_next设为nullptr
Node() : _next(nullptr), _data(T()) {}
// 构造函数，接收一个T类型的参数data，用以初始化数据域，并将_next设为nullptr
Node(const T& data) : _next(nullptr), _data(data) {}
// 数据域，存储链式队列中实际的数据
T _data;
// 指向下一个结点的指针
Node<T>* _next;
};
// 链式队列模板类
// 提供入队、出队、查看队首元素、判断队列是否为空等操作
template<class T>
class MyQueue
{
// 内部类型别名，简化代码中的结点类型名称
typedef Node<T> _Node;
public:
// 构造函数，初始化队列为空，头尾指针均指向空结点
MyQueue() : _size(0)
{
_head = new _Node();
_tail = _head;
}
// 创建新结点，接收一个T类型的参数data，返回新建的结点指针
_Node* createNode(const T& data)
{
_Node* newnode = new _Node(data);
if (newnode == nullptr)
{
exit(EXIT_FAILURE); // 如果内存分配失败，程序退出
}
return newnode;
}
// 入队操作，将给定数据插入队尾
void push(const T& data)
{
_Node* newnode = createNode(data);
if (_head->_next == nullptr)
{
_head->_next = newnode;
_tail = newnode;
}
else
{
_tail->_next = newnode;
_tail = newnode;
}
_size++; // 入队成功后，队列大小增一
}
// 出队操作，移除并返回队首元素
T pop()
{
assert(_size > 0); // 若队列为空，程序终止
_Node* first = _head->_next;
T first_data = first->_data; // 保存队首元素的值
_Node* second = first->_next;
_head->_next = second; // 更新头结点的_next，使其指向原队首元素的下一个结点
delete first; // 删除原队首结点
--_size; // 出队成功后，队列大小减一
return first_data; // 返回原队首元素的值
}
// 查看队首元素（不移除）
const T& front() const
{
assert(_size > 0); // 若队列为空，程序终止
return _head->_next->_data; // 直接返回队首元素的值
}
// 判断队列是否为空
bool empty() const
{
return _size == 0; // 如果队列大小为0，说明队列为空
}
// 打印队列中的所有元素
void PrintQueue()
{
_Node* cur = _head->_next;
while (cur)
{
std::cout << cur->_data << " "; // 输出当前结点的值
cur = cur->_next; // 移动到下一个结点
}
std::cout << "END" << std::endl; // 打印结束标记
}
private:
// 头结点，其_next指向队首元素
_Node* _head;
// 尾结点，始终指向队尾元素
_Node* _tail;
// 队列中元素的数量
size_t _size;
};
我们这里简单介绍一下，我们要看的几种队列的变形——双端队列，循环队列。
