顺序表之队列

上一篇博客我们学习了栈的实现，这一篇我们继续学习队列，让我们开始吧！

1.认识队列

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

2.入队列：进行插入数据的一端叫做队尾

3.出队列：进行删除数据的一端称为队头

4.结构：

这里我已经直接画出实现队列所用的结构了，但我们要知道为什么用链表结构。

2.实现队列的结构

我们有两种结构供选择，数组和链表

数组：它每次头出数据都要挪动后面的一堆数据，太繁琐

还有增容，需要频繁增容，增小不够，增大又会造成空间浪费

链表：链表就很合适，没有浪费空间的问题，头删时，只需要改变头指针，不需要挪动数据。

所以选链表

3.队列的实现

我们采用链表，选用单链表就可以很简单的实现。

Queue.h文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int ADataType;//定义数据类型
//定义队列结构体，里面存放组成队列的成员
typedef struct QueueNode
{
	ADataType data;
	struct QueueNode* next;
}QNode;
//创建队列的队头和队尾,也是结构体
typedef struct Queue
{
	//因为定义的是队列的头和尾，所以它们的类型是队列结构体
	QNode* head;
	QNode* tail;
}Queue;

//队列初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestory(Queue* pq);
//尾插数据
void QueuePush(Queue* pq, ADataType x);
//头删数据
void QueuePop(Queue* pq);
//返回队头数据，打印数据时，需要我们从头出
ADataType QueueFront(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, ADataType x)
{
	assert(pq);
	//创建新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//开始插入
	if (pq->head == NULL)
	{
		pq->head =pq->tail =newnode;
	}
	pq->tail->next = newnode;
	//指向新的尾
	pq->tail = newnode;
}
//头删数据
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	//只有一个节点，我们直接释放
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* cur = pq->head->next;
		free(pq->head);
		pq->head = cur;
	}
}
//返回队头数据，打印数据时，需要我们从头出
ADataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
//求队列存放了多少数据
int QueueSize(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	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"


//队列的实现
//队列的性质：先进先出
//我们用单链表就可以实现，在入队列时，我们采取尾插的办法，在出队列的时候，采用头出
//队头在数据出队列的时候，我们要把队头指向新的队头数据
//队尾在入数据时，队尾要指向新的队尾
//为了测试方便，我们所有操作在Test（）中实现

void Test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 11);
	QueuePush(&q, 22);
	QueuePush(&q, 3);
	QueuePush(&q, 5);
	QueuePush(&q, 9);
	QueuePush(&q, 7);
	QueuePush(&q, 27);
	QueuePush(&q, 77);
	QueuePush(&q, 100);
	int Queuesize = QueueSize(&q);
	printf("队列一共存放了 %d 个数据\n", Queuesize);
	//开始判断和打印
	while (!QueueEmpty(&q))
	{
		//出一个，删除一个数据,从头删
		printf(" %d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestory(&q);
}

int main()
{

	Test();
	return 0;
}