数据结构-队列【小白指南，超详细】
一、队列的概述
队列（Queue)是一种只允许在一端插入操作，一端删除操作的线性表。其特点是先进先出（First in First out),出队列的一端我们称为对头，入队列的一端我们称为队尾。
对头：只允许数据出队列（删除），我们一般用phead指针指向对头。
队尾：只允许数据入队列（插入），我们一般用ptail指针指向队尾。
由队列存储数据的方式不同，我们将队列分为顺序队列、链队列；顺序队列采用数组存储数据，链队列采用链表存储数据。本文主要讲述的是链队列。实现的功能主要有出队列、入队列、获取对头元素、获取队尾元素、获取队列中有效元素个数等等。其代码如下：
//入队列，队尾
void QueuePush(Queue* pq, QDataType x);
//出队列，对头
void QueuePop(Queue* pq);
//队列为空判断
bool QueueEmpty(Queue* pq);
//取对头元素
QDataType QueueFront(Queue* pq);
//取队尾元素
QDataType QueueBack(Queue* pq);
//求队列有效数据个数
int QueueSize(Queue* pq);二、队列结构的定义
由于我们采用链表存储数据，其节点结构与单链表结构类似，但是考虑到有对头、队尾，我们需要再创建一个结构体，将指向对头、队尾的指针包含进来。其代码如下：
//定义队列结构
//定义节点
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
QueueNode* phead;
QueueNode* ptail;
int size;//保留队列里有效数据个数
}Queue;这里的int size如果不求队列中的有效元素个数，可以删去。
三、队列的初始化
注意传过来的指针不能为空，需要用assert函数来断言报错，以及别忘记有头、尾指针，都需要赋NULL。其代码如下：
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}四、入栈操作
队列的入栈操作是在队尾进行，入队列操作需要先向内存申请新的节点空间，运用malloc函数即可。由于入栈操作只在队尾，就不用新的函数封装申请新的存储空间操作了。
//入队列，队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);//为什么，队列不可以为空吗？ 这不是队列不可以为空的判断
//判断队列是否满了（先申请新的节点）
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//入队列
//考虑队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
//队列不为空
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;//尾指针后移
}
pq->size++;
}入队列操纵我们首先需要考虑队列是否为空，如果没有考虑这点，那么pq->ptail是空指针，pq->ptail->next就是不合法的，程序会出错。所以，当队列为空时，我们直接将头指针和尾指针指向新节点即可；当队列不为空时，先将尾指针的下一个节点指向新节点（pq->ptail->next = newnode;），然后尾指针后移（pq->ptail = pq->ptail->next;）即可完成入队列操作。如果统计队列有效元素个数，别忘记pq->size++。
五、出栈操作
外甥打灯笼——照“舅”，一旦涉及删除操作，首先就要判断其是否为空，我们将判断读队列是否为空的操作封装在QueueEmpty函数里。其代码如下：
//队列为空判断
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL &&pq->ptail==NULL;
}QueueEmpty函数是bool类型的，当函数为空时即：pq->phead == NULL &&pq->ptail==NULL;为真返回ture,我们下面在考虑的时候让其不为空加个！就OK了。先看代码：
//队列为空判断
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL &&pq->ptail==NULL;
}
//出队列，对头
void QueuePop(Queue* pq)
{
assert(pq);
//首先考虑队列是否为空
assert(!QueueEmpty(pq));
//当队列只有一个节点时，单独考虑，避免ptail变为野指针
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* p = pq->phead->next;
free(pq->phead);
pq->phead = p;
}
pq->size--;
}无论入队列、出队列、获取对头元素、队尾元素、有效数据、销毁操作都需要assert函数断言，后面不再论述。
出队列操作需要额外考虑队列是否为空，需要对判断队列是否为空的函数断言：assert(!QueueEmpty(pq));为空时会断言报错，程序不再执行。
考虑完队列为空的情况，只有一个节点的情况也要额外考虑（if (pq->phead == pq->ptail)），如果没有考虑，我们free掉这唯一的一个节点后，尾指针缺乏指向，会变为野指针。
考虑完上述两种情况后，先将原队列头指针指向的节点的下一个节点的地址用新的指针存储起来（QueueNode* p = pq->phead->next;），然后释放掉头节点（free(pq->phead);），将存储的指针赋为头指针（pq->phead = p;）即可完成出栈操作。别忘记pq->size--。
六、取对头、队尾元素
取对头、队尾元素注意判断队列不为空。
1、取对头元素
//取对头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}2、取队尾元素
//取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}七、获取有效数据个数
有两种方法：
（1）在定义结构体时，如果记录了有效数据个数size,直接返回即可。代码如下：
//求队列有效数据个数
int QueueSize(Queue* pq)
{
assert(pq);
/*int size = 0;
QueueNode* pcur = pq->phead;
while (pcur)
{
size++ ;
pcur = pcur->next;
}
return size;*/
return pq->size;
}（2）遍历整个链表
没有记录有效数据size时，就遍历整个队列：
先记录头节点地址：QueueNode* pcur = pq->phead;然后while(pcur),使pucr指针不断向后移动（pcur = pcur->next;），当pcur指向为空时说明遍历完了队列，跳出循环。
分析两种方法：
第一种方法时间复杂度为O(1),第二种方法需要遍历整个队列，时间复杂度为O(n),执行效率更慢，优先考虑第一种方法，代码更加简洁且效率高。
八、销毁队列
销毁队列，原队列不能为空。然后从对头依次销毁即可，别忘记头、尾指针赋NULL即可。
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}九、链队列总代码
用三个文件分装代码：
Queue.h:用于定义队列的结构以及声明实现队列各种函数功能的声明。
Queue.c:队列中各种功能代码，用于实现队列中的各种功能。
test.c:用于测试Queue.c文件中的各种功能。
Queue.h代码：
#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
#include "assert.h"
//定义队列结构
//定义节点
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
QueueNode* phead;
QueueNode* ptail;
int size;//保留队列里有效数据个数
}Queue;
//初始化
void QueueInit(Queue* pq);
//入队列，队尾
void QueuePush(Queue* pq, QDataType x);
//出队列，对头
void QueuePop(Queue* pq);
//队列为空判断
bool QueueEmpty(Queue* pq);
//取对头元素
QDataType QueueFront(Queue* pq);
//取队尾元素
QDataType QueueBack(Queue* pq);
//求队列有效数据个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);Queue.c代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//入队列，队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);//为什么，队列不可以为空吗？ 这不是队列不可以为空的判断
//判断队列是否满了（先申请新的节点）
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//入队列
//考虑队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
//队列不为空
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;//尾指针后移
}
pq->size++;
}
//队列为空判断
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL &&pq->ptail==NULL;
}
//出队列，对头
void QueuePop(Queue* pq)
{
assert(pq);
//首先考虑队列是否为空
assert(!QueueEmpty(pq));
//当队列只有一个节点时，单独考虑，避免ptail变为野指针
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* p = pq->phead->next;
free(pq->phead);
pq->phead = p;
}
pq->size--;
}
//取对头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//求队列有效数据个数
int QueueSize(Queue* pq)
{
assert(pq);
/*int size = 0;
QueueNode* pcur = pq->phead;
while (pcur)
{
size++ ;
pcur = pcur->next;
}
return size;*/
return pq->size;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}test.c代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void Test01()
{
Queue q;
QueueInit(&q);
//入栈
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//出栈
QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//printf("head:%d\n", QueueFront(&q));
//printf("tail:%d\n", QueueBack(&q));
printf("size:%d\n", QueueSize(&q));
QueueDestroy(&q);
}
int main()
{
Test01();
return 0;
}欢迎各位佬指正错误。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
48
0- 0
已为社区贡献1条内容
所有评论(0)