数据结构 - 队列（C++ 实现） - 什么是队列

队列是一种基础且广泛应用的数据结构，它具有以下核心特征：

定义：

• 线性表：队列是一种特殊的线性表，其中的元素呈线性排列，每个元素都有一个直接前驱和一个直接后继（除了第一个元素无前驱，最后一个元素无后继）。

操作特性：

• 先进先出 (FIFO)：队列遵循“先进先出”原则，即最早进入队列的元素将最先离开队列。这意味着新元素总是被添加到队列的末端（称为队尾），而删除或访问元素则发生在队列的另一端（称为队头）。

基本操作：

1. 入队（Enqueue）：在队尾添加一个新元素。新元素成为队列中的最新成员，并且在任何已存在的元素之后等待被处理。
2. 出队（Dequeue）：从队头移除并返回最先进入队列的元素。这个操作确保了队列中最早加入的元素优先被处理。
3. 查看队头（Peek 或 Front）：返回队头元素但不移除它，允许查看即将被出队的元素而不改变队列状态。
4. 判空（IsEmpty）：检查队列是否为空，即没有任何元素。

实现方式：

• 顺序队列：使用固定大小的数组来存储元素。队头和队尾的索引需要进行适当的调整以确保正确的插入和删除。当队列满时，可能需要循环利用数组空间（环形缓冲区）或动态扩容。
• 链式队列：使用链表结构来存储元素，队头和队尾分别对应链表的首节点和尾节点。链式队列通常更易于处理队列满和队列空的情况，因为节点的增删不受固定数组大小的限制。

应用：
队列在计算机科学和许多实际应用场景中广泛使用，例如：

• 任务调度：安排任务按照提交顺序依次执行。
• 资源管理：如打印机任务队列，请求按照到达顺序打印文档。
• 消息传递：在分布式系统中，消息队列用于异步通信，发送者将消息放入队列，接收者按照消息进入队列的顺序进行消费。
• 缓存失效策略：如最近最少使用 (LRU) 缓存算法可以用双端队列来实现。
• 广度优先搜索 (BFS)：在图算法中，队列用于存储待探索的节点，确保按层级顺序遍历。

总结来说，队列是一个线性数据结构，它按照先进先出的原则组织和管理元素，支持在队尾进行插入（入队）和在队头进行删除（出队）的操作，常用于实现排队、任务调度、消息传递等场景，并可通过数组或链表等方式实现。