白日去如箭，达者惜今阳。 –朱敦儒
目录
🚁前言：
前几天我们对栈进行了实现，栈是数据先进后出，而今天我们要是实现的队列是完全相反的，队列
是数据先进先出。而在栈中我们使用的顺序表(数组)来实现的。而队列却用单链表来实现是更加合适的。
在队列入数据的时候，相当于是尾插，而队列出数据的时候相当于是头删。
- 队列的顺序结构
入队，不需要移动任何元素，时间复杂度为O(1)。
出队，所有元素需要往前移动，时间复杂度为O(N)。 - 队列的链式结构
首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点。
入队（尾插），时间复杂度为O(1)。
出队（头删），时间复杂度为O(1)。
结论：所以我们使用单链表来实现队列。
🏝️一.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行数据操作的特殊线性表，队列具有先进先出FIFO(Frist in First out)。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为对头。
队列的初始结构：单链表实现
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;//单链表
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;//队列头
QNode* tail;//队列尾
}Queue;🌻二.队列各种功能的实现
🍍1.队列的初始化
这里我们实现的单链表是无头不循环的单链表。所以我们把队列头和队列尾初始化为空指针。
//初始化
void QueueInit(Queue* ps)
{
assert(ps);
ps->head = ps->tail = NULL;
}🏝️2.队列的尾入
对于队列的尾入，我们要分为两种情况：
第一种：第一次尾入数据的时候，队列头和队列尾都是指向的同一个位置，并且都是空，当我们要尾入的时候创建一个新的结点，把新结点赋值给队列的头和队列的尾。
第二种：队列已经有数据了，我们把新的结点链接到尾后面，然后再把新结点赋值为新的结点，也就是更新队列的尾。总结：队列头是一直不变的，队列尾入一个数据就需要把队列尾往后面移动一位。
//队尾入
void QueuePush(Queue* ps,QDataType x)
{
assert(ps);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的结点
if (newnode == NULL)
{
perror("malloc\n");
return;
}
newnode->data = x;
newnode->next = NULL;
if ( ps->tail == NULL)//第一种情况
{
ps->head=ps->tail = newnode;//新结点就是队列尾和队列头
}
else//第二种情况
{
ps->tail->next = newnode;//队列尾链接新的结点
ps->tail = newnode;//更新队列尾
}
}🍉3.队列头的元素
需要知道队列头的元素是非常简单的，只需要返回队列头的元素即可。
//头的元素
QDataType QueueFront(Queue* ps)
{
assert(ps);
assert(ps->head);
return ps->head->data;
}🍁4.队列的头出
队列的头出也是分为两种情况：
第一种：当队列只有一个结点的时候，直接free掉第一个结点即可，然后把队列头和对列尾赋值尾空即可。
第二种：当队列有两个及两个以上的结点的时候，我们先保存队列头的下一个结点，然后free掉队列头即可。
//对头出
void QueuePop(Queue* ps)
{
assert(ps);
assert(ps->head);
if (ps->head->next == NULL)//当队列只有一个结点时
{
free(ps->head);
ps->head = ps->tail = NULL;
}
else//当队列有两个或者两个以上的结点时
{
QNode* next = ps->head->next;
//free掉第一个结点时，先保存下一个结点
free(ps->head);
ps->head = next;
}
}🍀5.判断是否为空
在队列出的时候，我们出一个数据就要判断一下队列是否为空，如果为空，我们就不能出数据了。
我们还是和栈的判断空一样，使用bool值来判断。
//判断是否为空
bool QueueEmpty(Queue* ps)
{
assert(ps);
return ps->head == NULL;
}
有了上面的代码我们就可以把出队列的数据给打印一下。
很明显这和队列的结构时一致的，即先进先出。
🚲6.队列尾的元素
//尾的元素
QDataType QueueBack(Queue* ps)
{
assert(ps);
assert(ps->head);
return ps->tail->data;
}
🪂7.销毁队列
最后退出程序，我们再把队列给销毁一下。
//销毁队列
void QueueDestroy(Queue* ps)
{
assert(ps);
QNode* cur = ps->head;
while (cur)
{
QNode* next = cur->next;
free(ps->head);
ps->head = next;
cur = next;
}
ps->head = ps->tail == NULL;
}最后我们再把队列的功能给实现一下：
🌴三.队列的全部代码
🌻1.Queue.h：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* ps);
//队尾插
void QueuePush(Queue* ps,QDataType x);
//队头出
void QueuePop(Queue* ps);
//头的元素
QDataType QueueFront(Queue* ps);
//尾的元素
QDataType QueueBack(Queue* ps);
//队列的元素个数
int QueueSize(Queue* ps);
//判断是否为空
bool QueueEmpty(Queue* ps);
//销毁队列
void QueueDestroy(Queue* ps);
🍌2.Queue.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QueueInit(Queue* ps)
{
assert(ps);
ps->head = ps->tail = NULL;
}
//队尾入
void QueuePush(Queue* ps,QDataType x)
{
assert(ps);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc\n");
return;
}
newnode->data = x;
newnode->next = NULL;
if ( ps->tail == NULL)
{
ps->head=ps->tail = newnode;
}
else
{
ps->tail->next = newnode;
ps->tail = newnode;
}
}
//对头出
void QueuePop(Queue* ps)
{
assert(ps);
assert(ps->head);
if (ps->head->next == NULL)//当队列只有一个结点时
{
free(ps->head);
ps->head = ps->tail = NULL;
}
else//当队列有两个或者两个以上的结点时
{
QNode* next = ps->head->next;
//free掉第一个结点时，先保存下一个结点
free(ps->head);
ps->head = next;
}
}
//头的元素
QDataType QueueFront(Queue* ps)
{
assert(ps);
assert(ps->head);
return ps->head->data;
}
//尾的元素
QDataType QueueBack(Queue* ps)
{
assert(ps);
assert(ps->head);
return ps->tail->data;
}
//队列的元素个数
int QueueSize(Queue* ps)
{
int count = 0;
QNode* cur = ps->head;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
//销毁队列
void QueueDestroy(Queue* ps)
{
assert(ps);
QNode* cur = ps->head;
while (cur)
{
QNode* next = cur->next;
free(ps->head);
ps->head = next;
cur = next;
}
ps->head = ps->tail == NULL;
}
//判断是否为空
bool QueueEmpty(Queue* ps)
{
assert(ps);
return ps->head == NULL;
}
🍈3.test.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("对于队列 1 2 3 4 出的数据为：\n");
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueuePush(&q, 5);
QueuePush(&q, 6);
QueuePush(&q, 7);
QueuePush(&q, 8);
printf("\n");
printf("队列的元素为 5 6 7 8\n");
printf("队列头的元素为：\n");
int first = QueueFront(&q);
printf("%d\n", first);
printf("队列尾的元素为:\n");
int tail = QueueBack(&q);
printf("%d\n", tail);
printf("队列的元素的个数为：\n");
int count = QueueSize(&q);
printf("%d\n", count);
QueueDestroy(&q);
printf("退出程序\n");
printf("队列已经被销毁……\n");
return 0;
}文章出处登录后可见！
已经登录？立即刷新
