队列是一种线性表，它有两个开放的端点。只允许在表的一端进行插入操作，在另一端进行删除操作。队列的特点是先进先出（First In First Out）。
允许插入的一端称为队尾（rear），允许删除的一端称为队头 (front)。向队列中插入新的数据元素称为入队（enqueue）。从队列中删除队头元素称为出队（dequeue）。

FIFO 队列原理

在队列中，新元素总是被添加到队列的尾部，而删除操作总是在队列的头部。这意味着，最早进入队列的元素将首先被删除。这就像一条排队等候购票的队伍，第一个到达的人将是第一个被服务的人。这就是所谓的“先来先服务”（First Come First Serve）原则。
队列的应用场景很多，比如生活中排队买东西，先排队的先购买，平时我们用微信聊天，用键盘进行各种数字的输入，到聊天框中输出，也是队列的应用。
我们看下图，可以看到队列的 front 和 rear 元素。这个图也很好地展示了FIFO原则：一旦front元素被删除，下一个元素（在rear之后）就会移动到front的位置。

队列的操作

队列的操作主要包括以下几种：

• 入队（enqueue）：在队尾添加一个新的数据元素。这个操作通常需要分配给新元素的内存空间，并将队列的尾指针向后移动一位。
• 出队（dequeue）：删除队头的数据元素。这个操作通常需要释放被删除元素所占用的内存空间，并将队列的头部指针向后移动一位。
• 取队头元素（front）：获取队头的数据元素。这个操作通常只需要返回队头的元素，不需要修改队列的状态。
• 求队列长度（size）：获取队列中数据元素的个数。这个操作通常只需要返回队列中元素的数量，不需要修改队列的状态。
• 判断队列是否为空（isEmpty）：判断队列中是否有数据元素。这个操作通常只需要检查队列的头部指针是否等于尾指针，如果相等则队列为空。
• 判断队列是否为满（isFull）：判断队列中数据元素是否超过了队列可容纳的最大的数据元素个数。这个操作通常需要检查队列的尾指针是否已经到达了队列的最大容量，如果已经到达则队列为满。

#include <cassert>
#include <iostream>
#include <queue>
 
int main(){
    std::queue<int> q;
 
    q.push(0); // back pushes 0
    q.push(1); // q = 0 1
    q.push(2); // q = 0 1 2
    q.push(3); // q = 0 1 2 3
 
    assert(q.front() == 0);
    assert(q.back() == 3);
    assert(q.size() == 4);
 
    q.pop(); // removes the front element, 0
    assert(q.size() == 3);
 
    // Print and remove all elements. Note that std::queue does not
    // support begin()/end(), so a range-for-loop cannot be used.
    std::cout << "q: ";
    for (; !q.empty(); q.pop())
        std::cout << q.front() << ' ';
    std::cout << '\n';
    assert(q.size() == 0);
}

输出：

q: 1 2 3

队列的分类

• 普通队列：普通队列是指只能在队列的一端进行插入操作，在另一端进行删除操作的队列。
• 双端队列：双端队列是指两端都可以进行插入和删除操作的队列。
• 优先队列：优先队列是指每个元素都有一个优先级，插入时按照优先级的高低插入，删除时则按照优先级的高低删除的队列。
• 阻塞队列：阻塞队列是指在队列为空的情况下，从队列中获取元素的操作将会被阻塞，直到队列中有了新的元素才会被唤醒的队列。
• 循环队列：循环队列是指在队列的头尾之间形成一个环，可以充分利用数组空间的队列。

队列的实现方式

队列的两种实现方式：顺序分配和链表分配。
顺序分配使用一个数组来实现队列。这种实现方式可以组织有限数量的元素。在顺序分配中，队列的元素在内存中是连续存储的。入队操作可以通过在数组的末尾添加元素来完成，而出队操作可以从数组的开头删除元素。然而，顺序分配队列的一个限制是它需要预先分配固定数量的空间，因此如果队列空间不足，可能需要重新分配更多的内存空间。

链表分配使用一个链表来实现队列。这种实现方式可以组织无限数量的元素。在链表分配中，每个节点都存储一个元素和一个指向下一个节点的指针。入队操作可以通过在链表的末尾添加一个新节点来完成，而出队操作可以从链表的开头删除一个节点。链表分配的一个优点是它不需要预先分配固定数量的空间，因此可以动态地添加和删除元素。然而，链表分配的缺点是它需要更多的指针操作，因此可能比顺序分配队列在时间上更慢。

栈和队列的区别

数据结构中的队列和栈是两种不同的数据结构，它们的主要区别体现在以下三个方面：

• 操作方式：队列的插入操作称为入队，删除操作称为出队，都是在队尾进行的。而栈的插入操作称为进栈，删除操作称为出栈，都是在栈顶进行的。
• 可操作方向：队列是在队尾入队，队头出队，即两边都可操作。而栈的进栈和出栈都是从栈顶进行的，无法对栈底直接进行操作。
• 操作原则：队列是先进先出（FIFO），即队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（不能中间插入），每次离开的成员总是队列头上的（不允许中途离队）。而栈则不同，它先进后出（FILO），只允许在表的一端进行插入和删除操作。
  总结来说，队列和栈在操作方式、可操作方向和操作原则上存在明显的差异。

队列的优点和缺点

队列的优点

• 先进先出：队列中的元素遵循先进先出的原则，即最先加入队列的元素最先被删除。这种顺序使得队列在处理任务时具有顺序性和公平性。
• 操作高效：队列中的插入和删除操作通常具有很高的效率，特别是对于链表实现的队列。在单链表中，插入和删除操作的时间复杂度为O(1)，而在双链表中，操作的时间复杂度也是O(1)。
• 适用于多线程环境：队列可以很好地支持多线程环境下的并发操作。多个线程可以同时向队列中插入或删除元素，而不会产生冲突或死锁。

队列的缺点

• 容量限制：队列的容量是有限的，一旦队列已满，就不能再添加新的元素。这可能导致一些问题，例如在预先不知道队列最大容量的情况下，可能导致内存溢出或者数组越界等问题。
• 不适用于循环使用场景：队列中的元素只能从队头删除，不能从中间或任意位置删除。因此，对于需要循环使用元素的场景，队列可能不适用。
• 无法直接访问元素：由于队列中的元素只能从队头删除，无法直接访问或修改队列中的任意元素。这可能导致一些不便或错误的出现。

总之，队列作为一种常用的数据结构，具有其独特的优点和缺点。在实际应用中，需要根据具体的需求和场景选择合适的队列实现方式，并注意避免其可能存在的缺点。