C语言数据结构之队列

1.队列的概念及结构

与栈不同的是，队列的出栈顺序是先入先出，就像我们出火车站，先排队的人排在前面，就先出站（插队不算奥，队列不可以插队，要做守规则的宝宝）。

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

御翮