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 、Queue.c 和 Queue.h 三个文件进行实现，可以更加方便操作，也可以避免代码全放在一个文件中显得冗余。

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");elseprintf("队列不为空\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;elsereturn 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
解析：出队操作，一定会影响头指针，因为出队是删除队头元素，如果出队时队列只有一个元素，会影响头指针也会影响尾指针。