数据结构之队列

@TOC

前言

本文章讲述的是数据结构的特殊线性表——队列

一.什么是队列，队列的特点

队列是数据结构中的一种特殊的线性表，它与栈不同，

队列的基本图例如上图： 显然，队列的特点就是:

先进先出First In First Out

那么我们使用什么样的方式来实现队列呢？

基于队列的特点，使用链表而不是数组来实现队列是比较合适的 使用数组来实现队列的缺点：

出队时需要挪动数据，效率不高。

使用链表来实现队列的优点：入队出队效率高，不需要挪动数据。 使用链表来进行入队出队时，就需要链接起来和释放节点，所以我们最好定义头指针和尾指针指向队头和队尾。

把头指针和尾指针放在一个结构体中，更方便操作，如下图：

二、队列相关操作

队列的相关操作声明

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

void QueueDestroy(Queue* pq);//销毁队列

void QueuePush(Queue* pq,QDataType x);//插入数据

void QueuePop(Queue* pq);//删除数据

int QueueSize(Queue* pq);//记录队列有多少人

bool QueueEmpty(Queue* pq);//判断队列是否为NULL

QDataType QueueFront(Queue* pq);//取出队头数据

QDataType QueueBack(Queue* pq);//取出队尾数据

队列的创建

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
//队列更适合用链表写,因为如果用顺序表来写，出列的时候需要挪动数据

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
//队伍的每个人的结构体

typedef struct Queue
{
	struct QueueNode* head;
	struct QueueNode* tail;
}Queue;
指向队头和队尾的两个指针放在一个结构体里面

1.队列的初始化

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

初始化指向队头和队尾的两个指针为NULL

2.对队列进行销毁

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

3.判断队列是否为空队列

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

4.入队操作

解读：队列的实现方式是链表，不需要检查容量不足，每入队一个人就申请一个节点即可

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode != NULL);
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//第一次入队的时候，就作为队头，头指针指向它
	pq->tail->next = newnode;
	pq->tail = newnode;

}

5.出队操作

//记住队列是先进先出，所以队头先出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//队头为空，说明删完了
	QNode* newhead = pq->head->next;//先记录队头的下一个人
	
	//删到最后的时候，tail没有置空，是野指针，所以这里要判断
	if (newhead == NULL)
	{
		pq->tail = NULL;
	}

	free(pq->head);
	pq->head = newhead;
}

6.取出队头数据

注意出队的时候，并没有拿出该人数的节点的值

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

7. 取出队尾数据

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

8.计算队伍的人数

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

总结

文章讲述简单队列的实现，复杂队列后续会讲。