数据结构：手把手带你实现链式队列

1. 引言

在数据结构中，队列（Queue）是一个非常重要的线性表。它的规则很简单就四个字：先进先出（FIFO，First In First Out)。就像在食堂打饭，先排队的人先打到饭，从队尾进，从队头出。

在数据结构中，实现队列通常有两种方式，顺序表（顺序队列）和链表（链式队列）

• 顺序队列：以数组首元素为队头，出队时，需要把后面的所有元素往前移动，时间复杂度为O（N），效率较低。而以数组尾元素为队头，入队时，时间复杂度也为O（N）。
• 链式队列：出队时只需删除头节点，入队时直接在尾节点后插入，时间复杂度都是 O(1)，效率极高。

因此，我们就基于单链表来实现一个高效的链式队列。

2. 队列的结构

2.1 队列结点的结构

先给出队列结点的结构，和单链表类似。

typedef int QDataType;

typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;

接着，我们尝试理一理入队和出队的思路。

• 两个指针：假设像实现单链表一样，我们只有一个头指针，那么我们就需要遍历链表找尾指针，那不对呀，在引言中不是说链式队列效率高吗？因此，我们就需要两个指针，一个头指针，一个尾指针。
• 二级指针：我们入队（插入新节点），要对尾指针修改；出队（删除节点）要对头指针修改。而C语言中函数传参传递的是变量的副本，传一级指针，在函数内部只能修改副本，外部原变量不会发生改变。因此，我们需要二级指针。

  // 队尾入队
  //void QueuePush(QNode** phead, QNode** ptail, QDataType x);
  // 对头出队
  //void QueuePop(QNode** phead, QNode** ptail);

• 结构体封装头指针和尾指针：传递二级指针：比如 void QueuePush(QNode** pphead, QNode** pptail, QDataType x);。每次调用都要传两个二级指针，代码显得非常臃肿。而把 phead 和 ptail 包装进一个结构体，直接传递结构体指针，就显得更简洁。

这样也引出了队列的结构。

2.2 队列的结构

由上文，我们得出队列的结构把 phead 和 ptail 包装进一个结构体。

typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size; // 记录队列元素个数
}Queue;

size的作用：只是一次计算队列的长度，假如结构体 Queue 里没有 size ,每次插入删除都会改变size ,这和单独遍历一次用时没区别。但是多次计算队列长度，结构体 Queue 里没有 size 则要多次遍历，那么 size 的优势就体现了。

还有一个问题，不是说要修改函数里的一级指针，需要二级指针吗，为什么结构体 Queue 里的phead 和 ptail 是一级指针？

3. 头文件

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int QDataType;

typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;

//// 入队（队尾插入）
//void QueuePush(QNode** phead, QNode** ptail, QDataType x);
//// 出队（队头删除）
//void QueuePop(QNode** phead, QNode** ptail);
// 参数太多，较为麻烦

typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;

// 初始化
void QueueInit(Queue* pq);
// 入队（队尾插入）
void QueuePush(Queue* pq, QDataType);
// 出队（队头删除）
void QueuePop(Queue* pq);

//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);

//获取队列大小
int QueueSize(Queue* pq);

//判空
bool QueueEmpty(Queue* pq);

//销毁
void QueueDestroy(Queue* pq);

4. 具体实现

4.1 初始化

// 初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

4.2 入队（队尾插入）

分成两种情况，和单链表类似，不再赘述。

// 入队（队尾插入）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (!newnode)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;

if (!pq->ptail) // 特殊情况
{
pq->phead = pq->ptail =newnode;
}
else // 一般情况
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}

pq->size++;
}

4.3 出队（队头删除）

分情况讨论，和单链表类似。

注意：

• 删除时，队列不能为空
• 并且为空时，del->next 会报错

// 出队（队头删除）
void QueuePop(Queue* pq)
{
assert(pq);
//删除时，队列不能为空
//并且为空时，del->next 会报错
assert(pq->phead);

QNode* del = pq->phead;
pq->phead = del->next;
free(del);
del = NULL;

if (pq->phead == NULL)
pq->ptail = NULL;

pq->size–;
}

4.4 获取队头元素

//获取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}

4.5 获取队尾元素

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}

4.6 获取队列大小

//获取队列大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

4.7 判空

//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);

return pq->size == 0;
}

4.8 销毁

//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);

while (pq->phead)
{
QNode* del = pq->phead;
pq->phead = del->next;
free(del);
del = NULL;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

4.9 完整实现文件

#include"Queue.h"

// 初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

// 入队（队尾插入）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (!newnode)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;

if (!pq->ptail) // 特殊情况
{
pq->phead = pq->ptail =newnode;
}
else // 一般情况
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}

pq->size++;
}

// 出队（队头删除）
void QueuePop(Queue* pq)
{
assert(pq);
//删除时，队列不能为空
//并且为空时，del->next 会报错
assert(pq->phead);

QNode* del = pq->phead;
pq->phead = del->next;
free(del);
del = NULL;

if (pq->phead == NULL)
pq->ptail = NULL;

pq->size–;
}

//获取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}

//获取队列大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);

return pq->size == 0;
}

//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);

while (pq->phead)
{
QNode* del = pq->phead;
pq->phead = del->next;
free(del);
del = NULL;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

5. 测试文件

#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);

// 测试入队
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("%d\\n", QueueSize(&q));

// 测试出队与遍历
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\\n");

QueueDestroy(&q);

return 0;
}