🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍
目录
- 🐼前言
- 🐼队列
- 🐼初始化队列
- 🐼入队列
- 🐼队列判空
- 🐼出队列
- 🐼取队头数据
- 🐼取队尾数据
- 🐼队列有效元素个数
- 🐼销毁队列
- 🐼全部源码
- 🐼文末
🐼前言
🌟在上一节我们实现了栈，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 栈，这一节小编给大家介绍另一种特殊的线性表：队列
🐼队列
✨ 队列也是一种特殊的线性表，队列规定：只允许在⼀端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
入队列:插入元素的一端我们称为队尾。
出队列:删除元素的一端我们称之为队头。
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
✨在实现队列时，我们底层用什么数据结构比较好呢？是链表还是数组呢？答案是都可以。队列可以用数组和链表的结构实现，使用链表的结构实现更优⼀些，因为如果使用数组的结构，出队列在数组头上需要挪动数据，效率会比较低。
✨为了让队列这个数据结构得以管理。我们创建了两个节点指针(phead和ptail)。分别指向队列的头和尾。这样队列就可以被这两个指针很好的维护起来了。为了统计队列中有效元素的个数，多加了一个成员变量size.
链式队列定义如下:
//定义队列节点结构
typedef int QueueDatatype;
typedef struct QueueNode
{struct QueueNode* next;QueueDatatype data;
}QNode;//定义队列结构
typedef struct Queue
{QNode* head;QNode* tail;int size;//队列中有效元素个数
}Queue;
下面我们实现队列
🐼初始化队列
//初始化队列
void InitQueue(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
🌻代码解析
我们将队列的头指针和尾指针初始情况都置为空，将有效元素size置为空.
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🐼入队列
//入队列
void PushQueue(Queue* pq,QueueDatatype x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->data = x;if (pq->head == NULL){//队列为空pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}++pq->size;
}
🌻代码解析
💫 因为队列中的每个元素，都是一个节点，因此入队列需要先申请新节点。因为没有带头结点，这里要对队列是否为空进行处理，如果为队列为空，队头和队尾就是插入的新节点，否则，在队尾插入新节点，并更新队尾。最后，更新有效元素size。
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🍂画图剖析:
🍀测试结果:
🐼队列判空
//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}
🌻代码解析
通过布尔类型的返回值，如果队头或者队尾为空，就是空队列，这里随意返回一个就可以;
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🐼出队列
//出队列
void PopQueue(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head == pq->tail){//如果只有一个节点，单独处理，避免tail变成野指针free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}🌻代码解析
💫断言保证队列不为空，注意:这里要对队列只有一个节点和多个节点进行分开处理，先处理多个节点:更新队头指针的指向，并更新队头指针；如果只有一个节点:直接释放队头，并将队头和队尾指针置为空，这样做的目的是:避免释放了队头指针而队尾指针变成野指针
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🍂画图剖析:
🐼取队头数据
QueueDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
🌻代码解析
断言保证队列不为空。直接返回队头数据。
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🐼取队尾数据
//取队尾数据
QueueDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail ->data;
}
🌻代码解析
断言保证队列不为空。直接返回队尾数据。
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🐼队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->size;
}
🌻代码解析
断言保证队列不为空。直接返回有效元素个数size。
💫时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🐼销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->head;while (pcur){QNode* next = pcur ->next;free(pcur);pcur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}🌻代码解析
让pcur保存当前节点，next保存下一个节点，释放pcur,让pcur走到next,直到pcur为空。最后将队头和队尾指针置为空。
💫时间复杂度为O(N),遍历一次队列，空间复杂度为O(1),只创建有效个变量
🍂画图剖析: 
🍀整体测试代码:
🐼全部源码
Queue.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义队列节点结构
typedef int QueueDatatype;
typedef struct QueueNode
{struct QueueNode* next;QueueDatatype data;
}QNode;//定义队列结构
typedef struct Queue
{QNode* head;QNode* tail;int size;//队列中有效元素个数
}Queue;//初始化队列
void InitQueue(Queue* pq);//入队列
void PushQueue(Queue* pq, QueueDatatype x);//出队列
void PopQueue(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QueueDatatype QueueFront(Queue* pq);
//取队尾数据
QueueDatatype QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);
Queue.c
#include"Queue.h"//初始化队列
void InitQueue(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//入队列
void PushQueue(Queue* pq,QueueDatatype x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->data = x;if (pq->head == NULL){//队列为空pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}++pq->size;
}
//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}
//出队列
void PopQueue(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head == pq->tail){//如果只有一个节点，单独处理，避免tail变成野指针free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//取队头数据
QueueDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//取队尾数据
QueueDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail ->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->head;while (pcur){QNode* next = pcur ->next;free(pcur);pcur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}test.c
#include "Queue.h"void test01()
{Queue ql;InitQueue(&ql);PushQueue(&ql, 1);PushQueue(&ql, 2);PushQueue(&ql, 3);PushQueue(&ql, 4);while (!QueueEmpty(&ql)){printf("%d->", QueueFront(&ql));PopQueue(&ql);}printf("\n");QueueDestroy(&ql);}
int main()
{test01();return 0;
}
🐼文末
感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️
