初阶数据结构【TOP】-6. 队列的实现

前言

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

一、什么是队列？

★ 概念：只允许在一端进行插入数据的操作 ， 另一端删除数据的操作的一种特殊线性表 。
● 队头：删除数据的一端叫做 ：队头（出队）
● 队尾：插入数据的一端叫做 ：队尾（入队）
★ 特点：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;

}

总结

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