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

（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