•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!
1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的原则。 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
与栈不同的是，队列的出栈顺序是先入先出，就像我们出火车站，先排队的人排在前面，就先出站（插队不算奥，队列不可以插队，要做守规则的宝宝）。
2.队列的实现逻辑
和栈一样，队列也可以用顺序表和链表来实现，但是我们要实现出队列，就相当于要实现头删数据的操作，对顺序表来说头删一个数据需要把后面的每一个数据都往前移动，消耗太大了，而对于链表而言只需要操作一个节点，比较简单，所以我们选择使用链表来实现队列。
关于队列，我们要实现以下几个接口：
//初始化队列
void Init_Queue(Queue* ptr);
//打印队列里面的数据
void Print_Queue(Queue* ptr);
//数据入队列
void Push_Queue(Queue* ptr, QDatatype val);
//数据出队列
void Pop_Queue(Queue* ptr);
//获取队头的数据
QDatatype Queue_Front(Queue* ptr);
//获取队尾的数据
QDatatype Queue_Back(Queue* ptr);
//获取队列储存的元素个数
int Queue_Size(Queue* ptr);
//判断队列是否为空
int Check_Empty(Queue* ptr);
//销毁队列
void Destroy_Queue(Queue* ptr);
3.队列的代码实现
test.c
#include "Queue.h"
void menu()
{
printf("******************************************\n");
printf("*************** 请选择 ***************\n");
printf("****** 1.PushQueue 2.PopQueue ******\n");
printf("****** 3.Print 4.QueueFront ******\n");
printf("****** 5.QueueBack 6.QueueSize ******\n");
printf("****** 7.CheckEmpty 0.Exit ******\n");
printf("******************************************\n");
}
int main()
{
int input = 0;
QDatatype value = 0;
Queue que;
Init_Queue(&que);
do
{
menu();
scanf("%d", &input);
switch (input)
{
case 1:
printf("请输入你要入队的值>:");
scanf("%d", &value);
Push_Queue(&que, value);
break;
case 2:
Pop_Queue(&que);
break;
case 3:
Print_Queue(&que);
break;
case 4:
if (que.head == NULL)
{
printf("队列为空\n");
break;
}
printf("队列头部元素为%d\n", Queue_Front(&que));
break;
case 5:
if (que.tail == NULL)
{
printf("队列为空\n");
break;
}
printf("队列尾部元素为%d\n", Queue_Back(&que));
break;
case 6:
printf("队列中有效元素的个数为%d\n", Queue_Size(&que));
break;
case 7:
if (Check_Empty(&que))
printf("队列为空\n");
else
printf("队列不为空\n");
break;
case 0:
Destroy_Queue(&que);
printf("队列销毁成功\n");
break;
default:
printf("选择错误，请重新选择\n");
break;
}
} while (input);
return 0;
}
Queue.c
#include "Queue.h"
//初始化队列
void Init_Queue(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
ptr->head = ptr->tail = NULL;
}
//销毁队列
void Destroy_Queue(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
QNode* cur = ptr->head;
while (ptr->head != NULL)
{
cur = ptr->head;
ptr->head = ptr->head->next;
free(cur);
}
ptr->tail = NULL; // 所有空间释放完后尾指针要置空，不然就是野指针
}
//开辟新节点
QNode* Buy_Node()
{
QNode* tmp = (QNode*)malloc(sizeof(QNode));
return tmp;
}
//打印队列里面的数据
void Print_Queue(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
QNode* cur = ptr->head;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//数据入队列
void Push_Queue(Queue* ptr,QDatatype val)
{
assert(ptr); // ptr要解引用，不能为空指针
QNode* newnode = Buy_Node();
if (newnode == NULL) // 可能开辟空间失败，失败会返回NULL，则终止后面的程序
{
perror("Push_Queue\n");
exit(1);
}
newnode->data = val; // 新节点要初始化好，把要储存的值赋进去
newnode->next = NULL;
if (ptr->head == NULL) //当队列为空时，头节点和尾节点都要赋值
{
ptr->head = ptr->tail = newnode;
}
else
{
ptr->tail->next = newnode;
ptr->tail = newnode;
}
}
//获取队列储存的元素个数
int Queue_Size(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
int count = 0;
QNode* cur = ptr->head;
while (cur != NULL)
{
cur = cur->next;
count++;
}
return count;
}
//数据出队列
void Pop_Queue(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
if (ptr->head == NULL)
{
printf("队列中没有元素\n");
return;
}
if (Queue_Size(ptr) == 1)
{
free(ptr->tail);//如果删完了但是没有将tail置为NULL，则case 5 会发生错误，显示队尾元素随机值。
ptr->tail = NULL;
ptr->head = NULL;
return;
}
QNode* pop = ptr->head;
ptr->head = ptr->head->next;
free(pop);
}
//获取队头的数据
QDatatype Queue_Front(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
return ptr->head->data;
}
//获取队尾的数据
QDatatype Queue_Back(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
return ptr->tail->data;
}
//判断队列是否为空
int Check_Empty(Queue* ptr)
{
assert(ptr); // ptr要解引用，不能为空指针
if (Queue_Size(ptr))
return 0;
else
return 1;
}
Queue.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>
typedef int QDatatype; // 队列储存的数据类型
typedef struct QNode
{
struct QNode* next; // 指向下一个节点
QDatatype data; // 节点储存的数据
}QNode;
typedef struct Queue
{
QNode* head; //指向队列的第一个节点
QNode* tail; //指向队列的最后一个节点
}Queue;
//初始化队列
void Init_Queue(Queue* ptr);
//打印队列里面的数据
void Print_Queue(Queue* ptr);
//数据入队列
void Push_Queue(Queue* ptr, QDatatype val);
//数据出队列
void Pop_Queue(Queue* ptr);
//获取队头的数据
QDatatype Queue_Front(Queue* ptr);
//获取队尾的数据
QDatatype Queue_Back(Queue* ptr);
//获取队列储存的元素个数
int Queue_Size(Queue* ptr);
//判断队列是否为空
int Check_Empty(Queue* ptr);
//销毁队列
void Destroy_Queue(Queue* ptr);
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现（链表实现要更简单一点），在下一篇博客中讲解一下。
4.相关例题
选择题
1.以下（ ）不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
答案：B
解析：队列只能从队头删除元素。
2.下列关于队列的叙述错误的是（ ）
A.队列可以使用链表实现
B.队列是一种“先入先出”的数据结构
C.数据出队列时一定只影响尾指针
D.数据入队列时一定从尾部插入
答案：C
解析：出队操作，一定会影响头指针，如果出队之后，队列为空，会影响尾指针。
