---

前言

本篇文章笔者将会对 “ 队列 ” 进行细致的讲解 ， 从队列的介绍 - 队列的选择 - 队列的实现 ， 逐一进行。

一、什么是队列？

★ 概念：只允许在一端进行插入数据的操作 ， 另一端删除数据的操作的一种特殊线性表 。
● 队头：删除数据的一端叫做 ：队头（出队）
● 队尾：插入数据的一端叫做 ：队尾（入队）
★ 特点：FIFO(First In First Out) 先进先出

● 图例：

★ 区分：栈是在一端进行操作 ， 队列是两端进行操作 。

---

二、队列的选择

要实现队列该如何选择呢 ？ 数组？ 链表？
★ 数组：队列要符合先进先出 ，两端进行操作 ，而用数组实现一端插入一端删除是有难度的 ， 在考虑删除时队列每出一个元素 ，该元素所在的空间就不能使用了 ，会造成空间浪费。

★ 链表：用链表实现两端操作就很方便 ，队列的实现大多选用链表实现的方式。
● 选择：因为我们只需要进行头和尾的操作 ， 所以相比双向链表我们倾向 用单链表来实现队列。

---

二、队列的实现

Queue.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//队列的声明 
//队列的特点 ： 先进先出 
//队头  队尾 //单链表实现
typedef int QueueDateType;typedef struct QueueNode
{QueueDateType x;struct Queue* next;}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//改结构体即可达到改链表的目的//初始化队列
void QueueInit(Queue* que);//队尾插入
void QueuePush(Queue* que , QueueDateType x);
//队头删除
void QueuePop(Queue* que);
//获取队尾元素
QueueDateType QueueBack(Queue* que);
//获取队头元素
QueueDateType QueueFront(Queue* que);
//获取队列中的有效元素
int QueueSize(Queue* que);
//队列判空
bool QueueEmpty(Queue* que);
//销毁队列
void QueueDestory(Queue* que);

Queue.c

#include "Queue.h"//初始化队列
void QueueInit(Queue* que)
{assert(que);que->phead = que->ptail = NULL;que->size = 0;
}//队尾插入
void QueuePush(Queue* que, QueueDateType x)
{assert(que);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fali!");exit(1);}newnode->x = x;newnode->next = NULL;if(que->phead == NULL){que->phead = que->ptail = newnode;}else{que->ptail->next = newnode;que->ptail = newnode;}que->size++;
}
//队头删除
void QueuePop(Queue* que)
{assert(que && que->size );//一个节点if(que->phead == NULL){free(que->phead);que->phead = que->ptail = NULL;}//多个节点else{QNode* next = que->phead->next;free(que->phead);que->phead = next;}que->size--;
}
//获取队尾元素
QueueDateType QueueBack(Queue* que)
{assert(que && que->ptail);return que->ptail->x;
}
//获取队头元素
QueueDateType QueueFront(Queue* que)
{assert(que && que->phead);return que->phead->x;
}
//获取队列中的有效元素
int QueueSize(Queue* que)
{assert(que);return que->size;
}
//队列判空
bool QueueEmpty(Queue* que)
{assert(que);return que->size == 0;
}
//销毁队列
void QueueDestory(Queue* que)
{assert(que);QNode* cur = que->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}que->phead = que->ptail = NULL;que->size = 0;
}

Test.c

#include "Queue.h"int main()
{Queue q; // 创建一个队列QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);bool ret = QueueEmpty(&q);printf("Empty ..result = %d\n", ret);int num = QueueSize(&q);printf("size = %d\n", num);int n = QueueBack(&q);printf("QueueBack = %d\n", n);int m = QueueFront(&q);printf("QueueFront = %d\n", m);printf("\n");while (!QueueEmpty(&q)){//取队头元素int ret = QueueFront(&q);printf("%d ", ret);QueuePop(&q);}printf("\n");return 0;}

总结

以上是关于队列的相关知识,希望对大家有所帮助!