目录

队列的简介

函数声明

函数定义

使用示例

---

队列的简介

其实本篇中还有好多C的影子，我以后还会出一个使用更多C++语法的版本

队列是一种常见的数据结构，它的特点是先进先出（亦可以称为公平性），可以在诸如排队的场景中运用（因为队列公平性的特点），我现在使用链表的形式实现。

为何不使用数组而是使用链表呢？

因为我们要实现先入先出，如果使用数组的话会出现不够灵活的问题。

我们所使用的数组的大小是固定的，虽然可以使用realloc来实现扩容来勉强解决大小固定的问题，但是我们在头删后空出来的空间就不知道该如何处理了。

（如果想用重复利用就要将整个数组中的数据全都移动位置，这个代价是相当高的）

如果将数组删除的节点空置，不仅仅会导致空间的浪费，其逻辑也是很乱的。

综上所述，使用数组实现是不合理的，我们这里使用单链表实现

函数声明

我在正式开始写之前在头文件声明下面使用typedef将int重命名为NodeType，这是为了获得更好的兼容性，想要改变储存的数据类型只要在typedef后面改一下就行

我这里将节点和队列本身各自封装了一个结构体

struct Queuenode//节点的结构体
{
	int x;
	Queuenode* next;
};

struct Queue//链表的结构体
{
	Queuenode* phead;
	Queuenode* ptail;
	int size = 0;
};

#pragma once
#include<iostream>
#include<cassert>
typedef int NodeType;

struct Queuenode//节点的结构体
{
	int x;
	Queuenode* next;
};

struct Queue//链表的结构体
{
	Queuenode* phead;
	Queuenode* ptail;
	int size = 0;
};

Queue* QueueInit();//队列初始化

void QueueAdd(Queue* qt, NodeType x);//添加元素(其实应该是push的,懒得改了)

NodeType QueuePop(Queue* qt);//出一个元素

NodeType Queuesize(Queue* qt);//读取队列的元素总量

NodeType QueueFront(Queue* qt);//读取队列头的元素

NodeType QueueTail(Queue* qt);//读取队列尾的元素

void QueueDisplayFront(Queue* qt);//从头开始依次打印元素

void QueueDestory(Queue* & qt);//摧毁队列

函数定义

#include"Queue.h"


Queue* QueueInit()//队列初始化
{
	Queue* qt = (Queue*)malloc(sizeof(Queue));
	if (qt == nullptr)
	{
		perror("Init");
		return nullptr;
	}
	qt->phead = nullptr;
	qt->ptail = nullptr;
	qt->size = 0;
	return qt;
}

void QueueAdd(Queue* qt, NodeType x)//添加元素
{
	Queuenode* newnode = (Queuenode*)malloc(sizeof(Queuenode));
	if (nullptr == newnode)
	{
		perror("malloc");
		return;
	}
	newnode->next = nullptr;
	if (nullptr == newnode)
	{
		perror("malloc");
		return;
	}
	if (nullptr == qt->phead && nullptr == qt->ptail)
	{
		qt->phead = newnode;
		qt->ptail = newnode;
	}
	else
	{
		qt->ptail->next = newnode;
		qt->ptail = newnode;
	}
	newnode->x = x;
	qt->size++;
}

NodeType QueuePop(Queue* qt)//出元素(带删除)
{
	if (nullptr == qt || nullptr == qt->phead)
	{
		std::cout << "还没有存储数据，无法删除" << std::endl;
		return;
	}
	if (nullptr == qt->phead->next)
	{
		free(qt->phead);
		qt->phead = nullptr;
		qt->ptail = nullptr;
	}
	else
	{
		Queuenode* next = qt->phead->next;
		free(qt->phead);
		qt->phead = next;
	}
	qt->size--;
}

int Queuesize(Queue* qt)//获得队列的元素数量
{
	return qt->size;
}

NodeType QueueFront(Queue* qt)//读取队列头的函数
{
	assert(qt);
	if (nullptr == qt || nullptr == qt->phead)
	{
		std::cout << "没有存入数据，无法读取" << std::endl;
		return -1;
	}
	return qt->phead->x;
}

NodeType QueueTail(Queue* qt)//读取队列尾的数据
{
	assert(qt);
	if (nullptr == qt || nullptr == qt->phead)
	{
		std::cout << "没有存入数据，无法读取" << std::endl;
		return -1;
	}
	return qt->ptail->x;
}

void QueueDisplayFront(Queue* qt)//从头开始展示
{
	if (nullptr == qt )
	{
		std::cout << "没有存入数据，无法读取" << std::endl;
		return;
	}
	Queuenode* pcur = qt->phead;
	while (pcur)
	{
		std::cout << pcur->x << "  ";
		pcur = pcur->next;
	}
	std::cout << std::endl;
}

void QueueDestory(Queue* & qt)//销毁队列
{
	if (nullptr == qt)
	{
		std::cout << "队列为空，无需删除" << std::endl;
		return;
	}
	else if (nullptr == qt->phead)
	{
		std::cout << "队列为空，无需删除" << std::endl;
		return;
	}

	Queuenode* next = nullptr;
	Queuenode* pcur = qt->phead;
	while (pcur)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(qt);
	qt = nullptr;
}

使用示例

#include"Queue.h"


int main()
{

	Queue* qt = QueueInit();
	if (nullptr == qt)
	{
		perror("Init");
		return 1;
	}
	QueueAdd(qt, 1);
	QueueAdd(qt, 2);
	QueueAdd(qt, 3);
	QueueAdd(qt, 4);
	QueueAdd(qt, 5);
	QueueDisplayFront(qt);
	QueuePop(qt);
	QueueDisplayFront(qt);
	QueueDestory(qt);
	QueueDisplayFront(qt);

	return 0;
}