队列(queue)是线性表的一种特殊形式‌，其遵循先进先出(FirstInFirstOut，FIFO)的原则。
与顺序表不同，队列的插入和删除操作是固定在队尾与队头进行的，顺序队列实际上是运算受限的顺序表。
队列有两个关键位置:队尾和队头。队尾是允许执行插入操作的位置，而队头是允许执行删除操作的位置。刚开始时，队列是空的，没有任何元素。
例如，在超市购物时，需要结账的顾客加入队列的队尾，也就是新插入的元素成为队尾元素。一个顾客结完账就离开了，排在最前面的顾客就可以开始结账，该顾客就是当前队头元素。这种方式保证了先来的顾客先离开队列，体现了先进先出的原则。队列不允许“插队”因此不允许在队尾以外的其他地方插入元素，也不允许删除其他位置的元素。队列中排队的人数称为队列的长度，当队列中没有顾客时，称为空队列。

这种先进先出的特性使得队列非常适合用来管理需要按照顺序处理的任务，例如打印机的打印任务、消息传递系统中的消息处理任务等。

这里只讨论队列的链式实现，即链式队列(Linked Queue)

基本概念

链式队列是一种基于链表实现的队列数据结构，它使用链表节点来存储数据元素，并通过指针连接这些节点来形成队列结构。与顺序队列（数组实现）相比，链式队列的主要特点是不需要预先分配固定大小的存储空间，可以动态地增长和缩减。

结构组成

链式队列通常由以下两个部分组成：

队首指针(front)：指向队列的第一个元素（即将被移除的元素）
队尾指针(rear)：指向队列的最后一个元素（最新添加的元素）

每个节点包含：

数据域：存储实际的数据
指针域：指向下一个节点的指针

优缺点分析

优点：

动态大小：不需要预先指定队列大小，可以动态增长
无空间浪费：不会出现顺序队列中的"假溢出"问题
内存利用率高：只在使用时分配内存

缺点：

每个节点需要额外的指针空间
操作稍慢：需要动态内存分配和释放
内存不连续：可能导致缓存不友好

应用场景

链式队列适合以下情况：

无法预估队列最大长度的场景
内存碎片化严重的环境
需要频繁插入删除且队列大小变化大的场合

例如：

操作系统中的进程调度队列
网络数据包缓冲队列
打印机任务队列

时间复杂度分析
操作 时间复杂度
入队 O(1)
出队 O(1)
检查空 O(1)
变体与扩展

双向链式队列：可以在两端进行插入和删除操作
优先队列：结合优先级的链式队列实现
循环链式队列：最后一个节点指向第一个节点，形成循环

实现注意事项

内存管理：确保正确释放出队节点的内存
边界条件：特别注意空队列和只有一个元素的情况
线程安全：在多线程环境中使用时需要添加同步机制

LinkedQueue.cpp实现

#include <iostream>
#include <stdexcept> // For std::underflow_error

template <typename T>
class Node {
public:
    T value;
    Node* next;
    Node(T val) : value(val), next(nullptr) {}
};

template <typename T>
class Queue {
private:
    Node<T>* front; // 指向队列首部的指针
    Node<T>* rear;  // 指向队列尾部的指针
    int count;      // 队列中的元素数量
public:
    Queue() : front(nullptr), rear(nullptr), count(0) {}
    ~Queue() { clear(); } // 析构函数，释放所有节点内存
    
    void push(const T& value) { // 在队尾添加元素
        Node<T>* newNode = new Node<T>(value);
        if (rear == nullptr) { // 如果队列为空，则新节点既是头部也是尾部
            front = rear = newNode;
        } else { // 如果队列不为空，将新节点添加到尾部，并更新尾部指针
            rear->next = newNode;
            rear = newNode;
        }
        count++; // 增加计数器
    }
    void pop() { // 从队首移除元素，如果队列为空则抛出异常
        if (empty()) throw std::underflow_error("Queue is empty"); // 检查队列是否为空并抛出异常（可选）
        Node<T>* temp = front; // 保存当前队首节点的指针以便释放内存
        front = front->next; // 更新队首指针到下一个节点
        if (front == nullptr) rear = nullptr; // 如果队列变为空，更新尾部指针为nullptr
        delete temp; // 释放原队首节点的内存
        count--; // 减少计数器
    }
    T& front() { // 获取队首元素但不移除（引用返回）
        if (empty()) throw std::underflow_error("Queue is empty"); // 检查队列是否为空并抛出异常（可选）
        return front->value; // 返回队首节点的值引用（注意：不检查是否为nullptr，因为已经在pop中做了检查）
    }
    bool empty() const { return count == 0; } // 检查队列是否为空
    int size() const { return count; } // 获取队列的大小（元素数量）
    void clear() { // 清空队列，释放所有节点内存（可选）
        while (!empty()) { pop(); } // 清空队列直到为空，释放所有节点内存（可选）
    }
};

main.cpp测试

C++标准库中的队列
std::queue是C++标准库中单端队列的实现。仅允许在队尾插入元素（push）和在队头删除元素（pop）‌，不支持随机访问或直接操作中间元素。

//
// C++标准库中的单端队列
//

#include <iostream>
using namespace std;

int main() {

    std::queue<int> queue;

    queue.push(1);//元素入队
    queue.push(2);
    queue.push(3);
    queue.push(4);
    
    queue.pop();//元素出队
    int front = queue.front();//访问队首元素

    int size = queue.size();//获取队列的长度
    bool empty = queue.empty();//判断队列是否为空

    cout << front << " " << size << " " << empty << endl;
    return 0;
}

std::deque是C++标准库中双端队列的实现，允许在队列的两端进行插入和删除操作，支持随机访问（通过[]或at()方法），性能接近数组。

//
// C++标准库中的双端队列
//

#include <iostream>
using namespace std;

int main() {

    std::deque<string> deque;

    deque.push_back("a");//元素入队
    deque.push_back("b");
    deque.push_back("c");
    deque.push_back("d");
    deque.push_back("e");

    for (int i = 0;i < deque.size();i++) {
        cout << "deque[" << i << "]:" << deque[i] << endl;
    }

    deque.pop_front();//队首元素出队
    deque.pop_back();//队尾元素出队

    cout << endl;
    
    for (int i = 0;i < deque.size();i++) {
        cout << "deque[" << i << "]:" << deque[i] << endl;
    }

    auto front = deque.front();//访问队首元素
    auto back = deque.back();//访问队尾元素

    auto size = deque.size();//获取队列的长度
    bool empty = deque.empty();//判断队列是否为空

    cout << front << " " << size << " " << empty << endl;
    return 0;
}

适用场景：‌std::queue适用于需要严格FIFO语义的场景，如广度优先搜索（BFS）或任务调度系统；而std::deque更适合需要灵活两端操作和随机访问的场景，例如滑动窗口算法或需要避免vector头部操作低效的场合。‌