C语言简明讲解队列的实现方法

来源：脚本之家时间：2022-04-22 11:52:24

前言

大家好啊，我又双叒叕来水博客了，道路是曲折的，前途是光明的，事物是呈螺旋式上升的，事物最终的发展结果还是我们多多少少能够决定的，好啦，吹水结束，这与这篇博客的主题并没有太多联系。关于栈和队列这一板块本来是想不写（就是想偷懒），但是想了想，觉得这样不太好，关于数据结构这一块可能会有缺失，所以最终还是决定写，必须补齐这一块，恰好最近有时间写博客，所以还是写了，这篇博客将介绍队列的知识点，理解链表那一块的操作后，栈和队列的相关操作还是比较容易去理解的。

队列的表示和实现

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First in First Out）

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

敲黑板，开始摸鱼：

其实也没什么重点啦，都是一些基本的概念性东西，主要有：

1.要理解FIFO代表的意思

2.什么是队尾队头，别弄混了

队列的实现有两种方法：

数组：不适合，队头出数据需要挪动数据，一般还会出现假溢出，循环队列啥的

链表：单链表较合适，头删尾插，效率较高

当然，并不是说一定要用哪种，由于课本是以数组为例，这里以单链表为例

代码实现

还是老样子，分为三部分，直接上手代码，来，跟着我一起敲

Queue.h

#pragma once
#include 
#include 
#include 
#include 
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
 //初始化
 void QueueInit(Queue* pq);
 //销毁
 void QueueDestory(Queue* pq);
 //队尾入
 void QueuePush(Queue* pq, QDataType x);
 //队头出
 void QueuePop(Queue* pq);
 //取队头数据
 QDataType QueueFront(Queue* pq);
 //取队尾数据
 QDataType QueuBack(Queue* pq);
 //个数
 int QueueSize(Queue* pq);
 //判断是否为空
 bool QueueEmpty(Queue* pq);

Queue.c

#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	//1.一个（防止野指针）
	//2.多个
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueuBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

Test.c

#include "Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestory(&q);
}
int main()
{
	TestQueue();
	return 0;
}