数据结构之《队列》

在数据结构之《栈》章节中学习了线性表中除了顺序表和链表外的另一种结构——栈，在本篇中我们将继续学习另一种线性表的结构——队列，在通过本篇的学习后，你将会对栈的结构有充足的了解，在了解完结构后我们还将进行栈的实现。一起加油吧！！！

 

---

 1.队列的结构与定义

概念：只允许在一端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

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

那么在队列的底层结构应该选择的是数组还是链表呢？接下来就来分析看看

在使用数组作为队列的底层结构时，由于队列的性质要求先进先出，所以可以使用size来表示数组内的有效元素个数，这样在入队列时就可以直接在数组的size位置插入数据，但是在出队列时为了将数组内的首个元素也就是数组下标为0的位置移除，这就需要将数组从下标为1的位置开始整体都向前移动一位，所以在出队列的时间复杂度为O(N) 

在使用单链表作为队列的底层结构时，由于队列的性质要求先进先出，所以如果只用一个phead指针指向链表的第一个节点，那么就会使得在入队列时要找到链表的尾节点就需要通过遍历链表才能实现，这就会使得时间复杂度为O(N),所以为了解决以上这种缺陷，就在创建一个指针指向链表的尾节点，在入队列是就可以直接找到尾节点，这样就可以使得无论是入队列还是出队列时间复杂度都为O(1)

通过以上的分析就可以得出在实现队列时底层结构选择单链表是最优解

 

2.队列的实现

在实现队列的代码中，在Queue.h头文件中定义队列的结构以及队列中各个函数的声明，在Queue.c文件内完成各个函数的定义，在test.c文件内对实现的各个函数进行测试

2.1队列结构的定义

在队列结构的定义中，创建一个结构体QueueNode来表示节点，该节点内部有两个成员变量，data来存放节点的数据，next指针来存放下一个节点的地址；之后还需再创建一个结构体Queue来存放指向链表的第一个节点和尾节点的指针，并且在这个结构体内还创建一个成员变量size来表示链表中节点的个数，这样是为了在之后的计算队列有效数据个数时直接将size的值提取出来就可实现了

//队列结构的定义
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;//节点内的数据
	struct QueueNode* next;//指向下一个节点的指针
	
}QueueNode;
 
typedef struct Queue
{
	struct QueueNode* phead;//指向第一个节点的指针
	struct QueueNode* ptail;//指向尾节点的指针
	int size;//节点的个数
 
}Queue;

 

2.2队列的初始化

要完成队列的初始化函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueInit，函数的参数为存放指向头尾节点指针的结构体指针

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

 

2.2判断队列是否为空

要完成队列判空函数首先要在Queue.h内完成函数的声明

bool QueueEmpty(Queue* pq);

将该函数命名为QueueEmpty，函数的为存放指向头尾节点指针的结构体指针，函数的放回类型是布尔类型，当队列为空时放回true，不为空就放回false

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言

在队列为空时就是指向第一个队列的指针phead和指向队列的尾部的指针ptail都为空，所以该函数的返回值就为pq->phead ==NULL && pq->ptail == NULL

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead ==NULL && pq->ptail == NULL;
}

 

2.3入队列 

要完成入队列函数首先要在Queue.h内完成函数的声明

//入队列
void QueuePush(Queue* pq, QDataType x);

将该函数命名为QueuePush，函数的参数有两个，第一个为存放指向头尾节点指针的结构体指针,第二个为要插入的数据

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
在实现数据的入队列前要为数据申请新的节点空间，在此使用malloc来实现，申请完之后在将要入队列的数据x存放到新节点newnode中，之后在将新节点插入到链表时要分以下两种情况，一种是phead指针指向为空时也就是这时链表内一个节点都没有，这时就要将phead和ptail都newnode；另外一种情况是phead指针指向不为空时，这时就先使得ptail的next指针指向newnode，之后再将ptail指向新节点newnode
最后在完成以上操作后要将有效个数size+1

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead== NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

 

2.4出队列 

要完成出队列函数首先要在Queue.h内完成函数的声明

//出队列
void QueuePop(Queue* pq);

将该函数命名为QueuePop，函数的参数为存放指向头尾节点指针的结构体指针

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言

之后在出队列也就是删除单链表的第一个节点时分为以下两种情况，第一种是指针phead和指针ptail指向同一个节点也就是链表中只有一个节点，这时就直接释放该节点，之后再将phead和ptail置为空；另外一种情况是指针phead和指针ptail不相同，这时就先创建一个新的指针变量Next指向原来的phead的next指针指向的节点，之后将phead指向的节点释放后，在将phead指针置为Next指向的节点

最后在完成以上操作后要将有效个数size-1

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* Next = pq->phead->next;
		free(pq->phead);
		pq->phead = Next;
	}
	pq->size--;
 
}

 

2.5取队列头数据 

要完成取队列头数据函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueFront，函数的参数存放指向头尾节点指针的结构体指针，函数的放回值就为队列的头数据也就是单链表的第一个节点存放的数据

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言
在队列中的头数据就为phead指针指向的节点内存放的数据
因此该函数直接放回pq->phead->data即可

//取队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

 

2.6取队尾数据

要完成取队列尾数据函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueBack，函数的参数为存放指向头尾节点指针的结构体指针，函数的放回值就为队列的尾数据也就是单链表的最后一个节点存放的数据

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言
在队列中的尾数据就为ptail指针指向的节点内存放的数据
因此该函数直接放回pq->ptail->data即可

//取队列尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

 

2.7队列有效数据个数 

要完成队列有效数据个数函数首先要在Queue.h内完成函数的声明

//队列有效数据个数
int QueueSize(Queue* pq);

将该函数命名为QueueSize，函数的参数为存放指向头尾节点指针的结构体指针，函数的返回值就为队列内有效的数据个数

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
因为队列内的有效数据个数就为结构体Queue内的成员变量size的值
所以该函数直接放回pq->size即可

//队列有效数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

 

2.8队列的销毁 

要完成队列的销毁函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueDestory， 函数的参数为存放指向头尾节点指针的结构体指针

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言

在销毁过程中通过遍历的方法来用free释放链表的所有节点，最后再将指针phead和指针ptail置为空，将有效数据个数赋值为0

//销毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

 

3.队列实现完整代码 

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//队列结构的定义
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;//节点内的数据
	struct QueueNode* next;//指向下一个节点的指针
	
}QueueNode;
 
typedef struct Queue
{
	struct QueueNode* phead;//指向第一个节点的指针
	struct QueueNode* ptail;//指向尾节点的指针
	int size;//节点的个数
 
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队列头数据
QDataType QueueFront(Queue* pq);
//取队列尾数据
QDataType QueueBack(Queue* pq);
//队列有效数据个数
int QueueSize(Queue* pq);

 

Queue.c

#include"Queue.h"
 
//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
 
//销毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
 
//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead ==NULL && pq->ptail == NULL;
}
 
 
 
//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead== NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
 
 
 
 
 
//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* Next = pq->phead->next;
		free(pq->phead);
		pq->phead = Next;
	}
	pq->size--;
 
}
 
//取队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
 
//取队列尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
 
}
 
//队列有效数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}