【数据结构】队列的实现

白日去如箭，达者惜今阳。                                                   --朱敦儒

目录 

🚁前言：​

🏝️一.队列的概念及结构 

🌻二.队列各种功能的实现

🍍1.队列的初始化

🏝️2.队列的尾入

🍉3.队列头的元素

🍁4.队列的头出

🍀5.判断是否为空

🚲6.队列尾的元素

🪂7.销毁队列

🌴三.队列的全部代码 

🌻1.Queue.h：

🍌2.Queue.c：

🍈3.test.c：

---

🚁前言：

前几天我们对栈进行了实现，栈是数据先进后出，而今天我们要是实现的队列是完全相反的，队列
是数据先进先出。而在栈中我们使用的顺序表(数组)来实现的。而队列却用单链表来实现是更加合适的。

在队列入数据的时候，相当于是尾插，而队列出数据的时候相当于是头删。

• 队列的顺序结构
  入队，不需要移动任何元素，时间复杂度为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 = ps->head->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 = ps->head->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()
{QNode 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;
}