C++ 队列详解

队列的数据结构 #

队列是一种先进先出（FIFO）的数据结构，常用于任务调度、缓冲区管理等场景。以下是队列的链式实现示例：

#include <iostream>
#include <cstdlib>
using namespace std;

// 定义队列结点的数据结构
struct QNode {
    QNode *next;  // 指针域，指向下一个结点
    double data;  // 数据域，存储队列信息
};

// 定义队列的数据结构
struct LinkQueue {
    QNode *front;  // 队首指针，指向队列的第一个结点
    QNode *rear;   // 队尾指针，指向队列的最后一个结点
};

// 初始化队列
void InitQueue(LinkQueue &Q) {
    QNode *q = new QNode;  // 申请一个结点的空间
    q->next = NULL;        // 作为头结点
    Q.front = q;           // 队首和队尾指针都指向头结点
    Q.rear = q;
}

// 判断队列是否为空
int IsEmpty(LinkQueue &Q) {
    return (Q.rear == Q.front) ? 0 : 1;  // 队列为空返回 0，否则返回 1
}

// 入队操作
void EnQueue(LinkQueue &Q, double e) {
    QNode *p = new QNode;  // 创建新结点
    p->next = NULL;
    p->data = e;           // 设置新结点的数据
    Q.rear->next = p;      // 将新结点插入队尾
    Q.rear = p;            // 更新队尾指针
}

// 出队操作
void DeQueue(LinkQueue &Q, double &e) {
    QNode *p = Q.front->next;  // 获取队首结点
    e = p->data;               // 保存队首结点的数据
    Q.front->next = p->next;   // 更新队首指针
    if (Q.rear == p)           // 如果队列只有一个结点，更新队尾指针
        Q.rear = Q.front;
    delete p;                  // 释放队首结点的内存
}

// 销毁队列
void DestoryQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;  // 逐个删除队列结点
        delete Q.front;
        Q.front = Q.rear;
    }
}

int main() {
    LinkQueue *Q = new LinkQueue;  // 定义队列
    InitQueue(*Q);                 // 初始化队列

    cout << "开始往队列里输入数据，以 -1 作为结束符" << endl;
    double a, x;
    cin >> a;
    while (a != -1) {
        EnQueue(*Q, a);            // 入队操作
        cout << "请输入一个数：" << endl;
        cin >> a;
    }

    // 输出队列元素
    QNode *p = Q->front->next;
    if (p == NULL) {
        cout << "队列为空！" << endl;
        return 0;
    }
    cout << "队列数据依次为：" << endl;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    // 出队操作
    while (IsEmpty(*Q)) {
        DeQueue(*Q, x);
        cout << x << " ";
    }

    // 释放内存
    delete Q->front;
    delete Q;
    system("pause");
    return 0;
}

---

C++ STL 中的队列 #

C++ 标准模板库（STL）提供了 queue 容器，用于实现队列功能。

定义队列 #

queue<typename> 队列名字;

例如：

queue<int> q1;          // 定义一个空的整型队列
queue<int> q2(q1);      // 通过复制 q1 定义 q2

常用方法 #

#include <queue>          // 引入队列头文件

q.front();        // 获取队首元素
q.back();         // 获取队尾元素
q.push(x);        // 将元素 x 插入队尾
q.pop();          // 弹出队首元素
q.size();         // 返回队列中元素的个数
q.empty();        // 判断队列是否为空
q.swap(q2);       // 交换两个队列的元素

---

双向队列（Deque） #

双向队列（deque）是一种可以在队头和队尾进行插入和删除操作的数据结构。

定义双向队列 #

deque<typename> 双向队列名字;

例如：

deque<int> dq;  // 定义一个整型双向队列

常用方法 #

#include <deque>          // 引入双向队列头文件

dq.push_front(x);   // 在队头插入元素 x
dq.push_back(x);    // 在队尾插入元素 x
dq.pop_front();     // 弹出队头元素
dq.pop_back();      // 弹出队尾元素
dq.front();         // 获取队头元素
dq.back();          // 获取队尾元素
dq.size();          // 返回队列中元素的个数
dq.empty();         // 判断队列是否为空
dq[i];              // 访问第 i 个元素
dq.at(i);           // 访问第 i 个元素（带边界检查）
dq.clear();         // 清空双向队列

---

优先队列（Priority Queue） #

优先队列是一种特殊的队列，元素的出队顺序由优先级决定，而不是插入顺序。

定义优先队列 #

priority_queue<Type, Container, Functional>

• Type：数据类型。
• Container：容器类型，默认为 vector。
• Functional：比较方式，默认为 less（大顶堆）。

例如：

priority_queue<int> pq;  // 默认大顶堆
priority_queue<int, vector<int>, greater<int>> pq2;  // 小顶堆

常用方法 #

pq.push(x);       // 插入元素
pq.pop();         // 弹出队头元素
pq.top();         // 获取队头元素
pq.size();        // 返回队列中元素的个数
pq.empty();       // 判断队列是否为空

优先队列的顺序控制 #

默认情况下，优先队列是大顶堆（队头为最大元素）。可以通过指定比较方式实现小顶堆：

// 大顶堆
priority_queue<int> q1;

// 小顶堆
priority_queue<int, vector<int>, greater<int>> q2;

// 大顶堆
priority_queue<int, vector<int>, less<int>> q3;