数据结构：队列详解与实现

一、队列是什么？

1. 队列的定义

队列： 特殊的线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作的一种数据结构。队列具有先进先出（FIFO, First In First Out）的原则。

2. 队尾&&队头

进行插入操作的一端称为队尾 进行删除操作的一端称为队头

队列示意图

3. 类比

就像我们在餐厅吃饭时，若饭店满人了，也许就会开始排队摇号，有 1 号、2 号、3 号…等等。当有座位空出来时，就让序号前的人先去；当又有人来时，就在队尾加一个序列。 而队列也是如此，只允许在一端进行插入数据操作，在另一端进行删除数据操作的一种数据结构。 当要删除数据时，就让队头的数据（先来的数据）先删除；当要插入数据时，就在队尾插入数据。

二、队列的实现

那么，我们该如何来实现队列呢？

1. 用什么来实现？

想要实现队列，首先要想清楚要用什么实现队列。之前，我们依次实现了顺序表、链表以及栈，他们都是用数组或链表来实现的。

队列也可以数组和链表的结构实现。但是之前我们讲到了在数组上头删（出队列）很麻烦，后续的每一个元素都要往前挪一位。 如果使用数组的结构来实现队列，出队列就会在数组头上出数据，效率会很低。 综上所诉，使用链表的结构来实现队列更优一些。

2. 实现思路

由于队列与单链表类似，这里可以拿单链表的实现来做参考

第 1 步
与单链表同理，队列中的每一个节点有以下两成员：
1. 指向下一个节点的指针
2. 节点中存储的数据
第 2 步 但是，我们需要记录下队列的总元素个数、头节点、尾节点这三个重要信息。 于是乎，我们可以单独创建一个结构体来包含这些信息，将队列的总元素个数、头节点、尾节点包含在内。
第 3 步 最后，就是一一实现我们队列的增、删、查、改等操作了。

3. 代码实现

本文以创建一个 int 类型的队列为例

（1）创建头文件&源文件

详见扫雷游戏等复杂程序的开发规范

如图: 创建了一个 Queue.h 头文件，用于存放用来放函数的声明和一些库函数的头文件。创建了一个 Queue.c 源文件，用于用来放函数的定义 (队列的主体)。还有一个 Test.c 源文件，用于测试实现的队列的运行效果。

（2）定义队列（定义）

首先我们要定义一个队列。 这里之前讲过，要先创建一个结构体来表示每个节点，再单独创建一个结构体来包含这些信息，将队列的总元素个数、头节点、尾节点包含在内。这样方便我们对队列的实现。

代码演示：（内有注释） （在头文件 Queue.h 中写）

//重定义，方便修改类型
typedef int QDataType; //表示每个节点的类型

typedef struct QListNode {
    QDataType data;      //节点中存储的数据
    struct QListNode* next; //指向下一个节点的指针
} QNode;

// 队列的结构
typedef struct Queue {
    QNode* front; //头指针
    QNode* tail;  //尾指针
    int size;     //总元素个数
} Queue;

在定义队列的代码中，有两个需要注意的点： 本文是以 int 类型为例，但如果以后要将队列中的元素类型修改成 char 类型或是其他类型一个一个修改就很麻烦。 所以我们重定义 int 类型为 QDataType,并将接下来代码中的 int 类型全部写成 QDataType。 这是为了方便我们以后对类型进行修改，仅需将 int 改为其他类型即可。 在定义队列的同时重定义队列的变量名为 QNode 方便以后使用。

（3）队列的初始化（初始化）

定义完队列后，肯定要对队列进行初始化，内容全部置 0 / NULL。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 初始化队列
void QueueInit(Queue* q);

在 Queue.c 源文件中写到：

// 初始化队列
void QueueInit(Queue* q) {
    assert(q); //断言空指针
    q->front = NULL;
    q->tail = NULL;
    q->size = 0; //全部初始化置 0 / NULL
}

在写实现代码中，有一个很重要的点： 当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的。 故为了我们的代码更加健壮，可以加入 assert 断言 来判断是否符合条件，在之后的代码中也都有。

（4）队列的销毁（销毁）

在我们的程序运行完毕后，当然要对队列进行销毁，以免占用内存。 这里我们直接遍历链表，一一释放空间销毁就行啦。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 销毁队列
void QueueDestroy(Queue* q);

在 Queue.c 源文件中写到：

// 销毁队列
void QueueDestroy(Queue* q) {
    assert(q); //断言空指针
    QNode* cur = q->front; //遍历链表，一一释放空间销毁
    while(cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->front = q->tail = NULL;
    q->size = 0; //全部初始化置 0 / NULL
}

（5）队尾入队列（尾插）

怎么插入？

在入队列时，由于队列只允许在一端进行插入数据操作，在另一端进行删除数据。 所以我们在插入时进行尾插数据，而在删除时进行头删数据。
怎么开辟空间？

由于这里是链表的结构，故每一次插入时开辟一个节点的空间就行了。
注意！！！

注意：当队列中没有节点时，此时插入的节点既是头节点，又是尾节点，所以头尾节点都要赋值。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 队尾入队列
void QueuePush(Queue* q, QDataType data);

在 Queue.c 源文件中写到：

// 队尾入队列
void QueuePush(Queue* q, QDataType data) {
    assert(q); //断言空指针
    QNode* tmp = (QNode*)malloc(sizeof(QNode)); //直接开辟一个节点的空间
    if(tmp == NULL) { //加一个 if语句 防止增容失败
        perror("malloc");
        return;
    }
    //没有问题后就赋值
    tmp->data = data;
    tmp->next = NULL;
    //注意：当队列中没有节点时
    //此时插入的节点既是头节点，又是尾节点
    if(q->size == 0) {
        q->front = tmp;
        q->tail = tmp;
    } else {
        q->tail->next = tmp;
        q->tail = tmp;
    }
    q->size++;
}

（6）队头出队列（头删）

怎么删除？

在出队列时，由于队列只允许在一端进行插入数据操作，在另一端进行删除数据。 刚刚我们在队尾进行插入数据，而现在删除数据时就是用头删数据。
注意！！！

注意：当队列中只有一个节点时，此时头尾节点相等，都要进行删除，所以将头节点和尾节点都释放。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 队头出队列
void QueuePop(Queue* q);

在 Queue.c 源文件中写到：

// 队头出队列
void QueuePop(Queue* q) {
    assert(q);
    assert(q->size > 0); //断言空指针
                         //断言顺序表不能为空
    //注意：当队列中只有一个节点时，头尾节点相等
    //此时将头节点和为尾节点都释放
    if(q->size == 1) {
        free(q->front);
        q->front = NULL;
        q->tail = NULL;
    } else {
        QNode* del = q->front;
        q->front = q->front->next;
        free(del);
    }
    q->size--;
}

（7）获取队列头部元素

这个很简单，直接用下标进行访问数据，再返回所对应的值。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 获取队列头部元素
QDataType QueueFront(Queue* q);

在 Queue.c 源文件中写到：

// 获取队列头部元素
QDataType QueueFront(Queue* q) {
    assert(q);
    assert(q->size > 0); //断言空指针
                         //断言顺序表不能为空
    return q->front->data;
}

（8）获取队列尾部元素

这个很简单，直接用下标进行访问数据，再返回所对应的值。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 获取队列队尾元素
QDataType QueueBack(Queue* q);

在 Queue.c 源文件中写到：

// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
    assert(q);
    assert(q->size > 0); //断言空指针
                         //断言顺序表不能为空
    return q->tail->data;
}

（9）获取队列中有效元素个数

这个很简单，直接返回所对应的值。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 获取队列中有效元素个数
int QueueSize(Queue* q);

在 Queue.c 源文件中写到：

// 获取队列中有效元素个数
int QueueSize(Queue* q) {
    assert(q); //断言空指针
    return q->size;
}

（10）检测队列是否为空

这个很简单，如果队列为空返回非零结果，如果不为空返回 0。

代码演示：（内有注释） （其中 q 是一个指向队列的指针，下同）

在 Queue.h 头文件中写到：

// 检测队列是否为空，如果为空返回非零结果，如果不为空返回 0
int QueueEmpty(Queue* q);

在 Queue.c 源文件中写到：

// 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueEmpty(Queue* q) {
    assert(q); //断言空指针
    return q->size == 0;
}

三、完整代码实现

1. Queue.h

用于存放用来放函数的声明和一些库函数的头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

//重定义，方便修改类型
typedef int QDataType; //表示每个节点的类型

typedef struct QListNode {
    QDataType data;      //节点中存储的数据
    struct QListNode* next; //指向下一个节点的指针
} QNode;

// 队列的结构
typedef struct Queue {
    QNode* front; //头指针
    QNode* tail;  //尾指针
    int size;     //总元素个数
} Queue;

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

2. Queue.c

用于用来放函数的定义 (队列的主体)

#include "Queue.h"

// 初始化队列
void QueueInit(Queue* q) {
    assert(q); //断言空指针
    q->front = NULL;
    q->tail = NULL;
    q->size = 0; //全部初始化置 0 / NULL
}

// 队尾入队列
void QueuePush(Queue* q, QDataType data) {
    assert(q); //断言空指针
    QNode* tmp = (QNode*)malloc(sizeof(QNode)); //直接开辟一个节点的空间
    if(tmp == NULL) { //加一个 if语句 防止增容失败
        perror("malloc");
        return;
    }
    //没有问题后就赋值
    tmp->data = data;
    tmp->next = NULL;
    //注意：当队列中没有节点时
    //此时插入的节点既是头节点，又是尾节点
    if(q->size == 0) {
        q->front = tmp;
        q->tail = tmp;
    } else {
        q->tail->next = tmp;
        q->tail = tmp;
    }
    q->size++;
}

// 队头出队列
void QueuePop(Queue* q) {
    assert(q);
    assert(q->size > 0); //断言空指针
                         //断言顺序表不能为空
    //注意：当队列中只有一个节点时，头尾节点相等
    //此时将头节点和为尾节点都释放
    if(q->size == 1) {
        free(q->front);
        q->front = NULL;
        q->tail = NULL;
    } else {
        QNode* del = q->front;
        q->front = q->front->next;
        free(del);
    }
    q->size--;
}

// 获取队列头部元素
QDataType QueueFront(Queue* q) {
    assert(q);
    assert(q->size > 0); //断言空指针
                         //断言顺序表不能为空
    return q->front->data;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
    assert(q);
    assert(q->size > 0); //断言空指针
                         //断言顺序表不能为空
    return q->tail->data;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q) {
    assert(q); //断言空指针
    return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueEmpty(Queue* q) {
    assert(q); //断言空指针
    return q->size == 0;
}

// 销毁队列
void QueueDestroy(Queue* q) {
    assert(q); //断言空指针
    QNode* cur = q->front; //遍历链表，一一释放空间销毁
    while(cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->front = q->tail = NULL;
    q->size = 0; //全部初始化置 0 / NULL
}

3. Test.c

用于测试实现的队列的运行效果

#include "Queue.h"

int main() {
    Queue Q;
    QueueInit(&Q);
    QueuePush(&Q, 1);
    QueuePush(&Q, 2);
    QueuePush(&Q, 3);
    QueuePush(&Q, 4);
    QueuePush(&Q, 5);
    QueuePush(&Q, 6);
    /*QueuePop(&Q); 
     int ret1 = QueueFront(&Q); 
     QueuePop(&Q); 
     int ret2 = QueueFront(&Q); 
     QueuePop(&Q); 
     int ret3 = QueueFront(&Q); 
     printf("%d %d %d\n\n", ret1, ret2, ret3);*/
    while(QueueEmpty(&Q)) {
        printf("%d ", QueueFront(&Q));
        QueuePop(&Q);
    }
    printf("\n\n");
    QueueDestroy(&Q);
    return 0;
}

参考资料

C++ Reference