详解数据结构之队列、循环队列(源码)

队列属于线性表

队列：就好比如，我们在排队买东西时排队，第一个先来的第一个买，最后一个到的最后一个买，这里的队列也是满足先进先出，后进后出的规律（First In First Out），允许插入数据的一端叫做队头简称入队列，允许删除数据的一端叫做队尾简称出队列。

队列的存储形式：

顺序存储结构，实现循环队列，队列长度时固定的
链式存储结构，实现不循环队列，队列长度理论上是无限大的

两种存储结构实现的队列复杂度：

时间复杂度 O(1)
空间复杂度 O(1)

队列

使用链式结构实现的队列，其基本结构类似于单链表。使用next指针将每一个节点链接。主要区别在于没有使用一个指针来指向节点，这里定义了两个指针指针单链表，一个phead指针指向单链表的头，一个ptail指针指向单链表的尾。

单链表的头为队列的队头，单链表的尾为队列的队尾。

在这里插入图片描述

有了指针指向链表的最后一个节点，就不再需要使用循环遍历到链表的最后一个节点，将入栈的时间复杂度从O(N)优化到O(1)。

typedef int QueueDataType;
typedef struct QueueNode//节点
{
	QueueDataType val;
	struct QueueNode* next;

}QueueNode;
struct Queue
{
	QueueNode* phead;//指向队头的指针
	QueueNode* ptail;//指向队尾的指针
	int size;//统计单链表的节点个数
};
typedef struct Queue Queue;

功能实现

//初始化
void QueueInit(Queue* p);
//销毁
void QueueDestory(Queue* p);
//入队列，队尾,不就是尾插
void QueuePush(Queue* p, QueueDataType x);
//出队列，队头
void QueuePop(Queue* p);
//取队头数据
QueueDataType QueueFront(Queue* p);
//取队尾数据
QueueDataType QueueBack(Queue* p);
//判空
bool QueueEmpty(Queue* p);
//获取有效数据个数
int QueueSize(Queue* p);

初始化、销毁

初始化

初始化指向队列的两个指针，和对统计节点个数大小的size，由于传递的是地址就不需要返回值。

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

销毁

将队列的节点一一销毁，其操作逻辑与单链表相似。

销毁链表，需要对每一个节点进行释放，而只使用一个指针pcur，释放当前的节点就找不到下一个节点了，这里需要使用两个指针。

一个指针用来释放（pcur），一个指针用来指向待释放之后的节点（next）。

当释放完pcur节点后，更新pcur的位置 pcur = next;，用来释放下一个节点，next指针也需要更新用来指向下一个节点 next = pcur->next;，用来对pcur进行更新。直到pcur指向空指针时释放完所有节点，跳出循环。而 phead和ptail指针，还没有置为空，这时候时野指针，最后一步 p->phead = p->ptail = NULL;。

void QueueDestory(Queue* p)
{
	assert(p);
	QueueNode* pcur = p->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	p->phead = p->ptail = NULL;
	p->size = 0;
}

判空

判断队列的节点是否为空并返回一个布尔值。

如上对队列的初始化，两个头尾指针指向的都为空，此时队列就是空，队列为空返回true，不为返回false。

函数起始别忘了对指针p判空，为空则说明队列不存在了。

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

入队列、出队列

入队列

想要进行尾插首先得有一个指针指向最后一个节点，然后将创建的新节点插入到该节点后面，最后更新ptail指针指向的位置

入队列有两种情况：

队列为空

此时phead和ptail都指向空，插入一个新节点，phead和ptail均指向它。

队列不为空

在ptail指针后插入一个新节点，通过节点的next指针连接，然后更新ptail指针，让其指向新的尾。
在这里插入图片描述

最后别忘了将统计节点个数的size加1。

//入队列，队尾,不就是单链表的尾插
void QueuePush(Queue* p, QueueDataType x)
{
	assert(p);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//创建新节点
	if (newnode == NULL)//判空，有无开辟成功
	{
		perror("malloc");
		return;
	}
	newnode->val = x;//赋值
	newnode->next = NULL;
	
	if (p->phead == NULL)//phead和ptail为空时
	{
		p->phead = p->ptail = newnode;
	}
	else//两者不为空
	{
		p->ptail->next = newnode;
		p->ptail = newnode;
	}
	p->size++;//别忘了记录新加入的节点
}

出队列

出队列的逻辑并不复杂，前提是指针p不为空，为空则说明队列不存在、队列不为空，为空则说明没有节点可删，接下来就是对空指针解引用。

它同样分为两种情况：

只有一个节点

即phead和ptail指向同一个节点时，将该节点释放，然后将phead和ptail指针指向空。

有许多个节点

一，保存phead之后的节点 QueueNode* Next = phead->next;二，然后释放第一个节点 free(phead);三，最后将 Next 赋给 phead，更新头节点的位置。

最后将size减1。
在这里插入图片描述

//出队列，队头,这不就是单链表的头删吗
void QueuePop(Queue* p)
{
	assert(p);
	assert(!QueueEmpty(p));
	if (p->phead == p->ptail)
	{
		free(p->phead);
		p->phead = p->ptail == NULL;
	}
	else
	{
		QueueNode* Next = p->phead->next;
		free(p->phead);
		p->phead = Next;
	}
	p->size--;
}

取队头数据、取队尾数据

取对头数据

取对头数据那是相当简易，只需要将头指针指向的节点的value值返回即可。需要注意的是对指针p和队列的判空，以及返回数据的类型。

//取队头数据
QueueDataType QueueFront(Queue* p)
{
	assert(p);
	assert(!QueueEmpty(p));
	return p->phead->val;
}

取队尾数据

有了之前定义的ptail指针，就不需要像单链表一个一个节点的遍历到最后一个节点，取队尾数据，只需将尾指针指向的节点的value值返回即可，它需要注意的点与取对头数据相同。

//取队尾数据
QueueDataType QueueBack(Queue* p)
{
	assert(p);
	assert(!QueueEmpty(p));
	return p->ptail->val;
}

取队列有效数据个数

将队列的size返回，返回值为int，因为它只是用来统计个数的。

//获取有效数据个数
int QueueSize(Queue* p)
{
	assert(p);
	return p->size;
}

源码

Queue.h

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

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType val;
	struct QueueNode* next;

}QueueNode;
struct Queue
{
	QueueNode* phead;//指向队头的指针
	QueueNode* ptail;//指向队尾的指针
	int size;
};
typedef struct Queue Queue;
 
//初始化
void QueueInit(Queue* p);
//销毁
void QueueDestory(Queue* p);
//入队列，队尾,不就是尾插
void QueuePush(Queue* p, QueueDataType x);
//出队列，队头
void QueuePop(Queue* p);
//取队头数据
QueueDataType QueueFront(Queue* p);
//取队尾数据
QueueDataType QueueBack(Queue* p);
//判空
bool QueueEmpty(Queue* p);
//获取有效数据个数
int QueueSize(Queue* p);

Queue.c

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

循环队列

循环队列，就类似将链表的头尾节点链接在一起了。

使用顺序存储结构的优缺点：

优

数组支持随机访问，在O(1)时间内访问任意元素（速度）
数组的操作和使用简单好理解
不需要使用额外空间存储节点指针

缺

数组的大小在创建时就确定了

typedef int CQDataType;
typedef struct CircularQueue
{
	CQDataType* arr;
	int front;//指向队头元素
	int rear;//指向队尾的下一个位置
	int capacity;//空间大小
}CQueue;

在这里插入图片描述

初始情况下，front和rear指向同体块空间时，队列为空，入队列后front不变，rear向后加1，如下图。
在这里插入图片描述

当插入a5时rear将指向数组外的空间，然后在插入a6，rear继续指向数组之外的空间。纳尼？？都指向数组之外的空间了，那不是越界访问了吗？

在这里插入图片描述

现在假设不存在这种问题，插入a5数据后rear指向front，此时有没有发现又乱套了。front和rear指向了同一块空间，前文以及说过当frong和rear指向同一块空间时队列为空，那这种情况又该咋办呢~。
在这里插入图片描述

为了解决以上两种情况，这里将数组空出一块空间，不插入a5此时队列就是满队列的情况。

而想要实现rear为4时在加上1能够循环到0，可以使用求模运算操作符。

在这里插入图片描述

初始条件下开辟给数组capacity+1的空间，多余的1是给rear用的，防止font和rear相等无法判断是否满队列还是空队列的情况。假设此时capacity为4，那就得开辟空间大小为5的数组，如上图。

pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;如上图，此时rear为4，capacity为4，都加1后 5 % 5结果为刚好等于front此时满队列，而不是如同之前的情况，rear和front的尴尬情况。

在这里插入图片描述

实现rear加1后能够在 0 ~ 4内循环，而不造成数组越界访问使用取模操作符，如上图，当rear为4时加1为5，但它指向了0，根据pcq->rear = pcq->rear % pcq->capacity + 1;不能得出此时 5 % 5的结果为0，然后将0赋给rear重置了rear的位置。

功能实现

//开辟空间，n指开辟大小
void CQCreat2(CQueue* pcq, int n);
//判断队列空否
bool CQEmpty(CQueue* pcq);
//判断队列满否
bool CQFull(CQueue* pcq);
//入队列
void CQPush(CQueue* pcq, CQDataType x);
//出队列
void CQPop(CQueue* pcq);
//取队头元素
CQDataType CQFront(CQueue* pcq);
//取队尾元素
CQDataType CQBACK(CQueue* pcq);
//销毁队列
void CQDestory(CQueue* pcq);

开辟空间、销毁队列

开辟空间、初始化

开辟大小为n + 1的空间，让后将front和rear置0，将n赋给capacity，表示了rear和front的最大取值。

void CQCreat2(CQueue* pcq, int n)
{
	pcq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (n + 1));
	pcq->front = pcq->rear = 0;
	pcq->capacity = n;
}

销毁队列

销毁队列，将arr数组释放，让后置空（此时为野指针），需要注意的是对 pcq->arr，的判空，若它为空指针就不需要释放数组。

//销毁队列
void CQDestory(CQueue* pcq)
{
	assert(pcq);
    if(pcq->arr)
		free(pcq->arr);
	pcq->arr = NULL;
	pcq->front = pcq->rear = pcq->capacity = 0;
}

判断队列满否、空否

判断队列是否被放满

前文以及提过，判空后队列满返回真，队列未满返回假，使用assert断言避免pcq为空指针，从而造成对空指针的解引用。

//判断队列满否
bool CQFull(CQueue* pcq)
{
	assert(pcq);
	return (pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;
}

判断队列是否为空队列

front与rear相等队列为空返回真，不相等返回假。

//判断队列空否
bool CQEmpty(CQueue* pcq)
{
	assert(pcq);
	return pcq->front == pcq->rear;//相等为空
}

入队列、出队列

入队列

入队列不难理解，只需要找到对应得数组标然后放进去即可。但需要严重关注的是在入队列前对数组是否满了进行判断，以及成功入了一个元素rear加1后，对rear重新修正大小，避免造成数组越界。

//入队列
void CQPush(CQueue* pcq, CQDataType x)
{
	assert(pcq);
	assert(!CQFull(pcq));
	pcq->arr[pcq->rear++] = x;
	pcq->rear %= pcq->capacity + 1;
}

出队列

出队列，同理出队列，想要出队列那就不可能对一个空队列出元素，那得先调用判断队列是否为空队列的函数，然后在出队列，想要实现出队列，只需要让front加1即可，前front指向的数据被放弃掉是无效的，将front加1后同rear一样需要对其重新修正大小，避免造成数组越界。

//出队列
void CQPop(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	pcq->front++;
	pcq->front %= pcq->capacity + 1;
}

取对头数据、取队尾数据

取对头数据

只需将front指向的数据返回。

//取队头元素
CQDataType CQFront(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	return pcq->arr[pcq->front];
}

取队尾数据

只需将rear指向的数据返回。

//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	int ret = pcq->rear - 1;
	if (pcq->rear == 0)
	{
		ret = pcq->capacity;
	}
	return pcq->arr[ret];
}

源码

CircularQueue.h

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

typedef int CQDataType;
typedef struct CircularQueue
{
	CQDataType* arr;
	int front;
	int rear;
	int capacity;
}CQueue;

//开辟空间，n指开辟大小
CQueue* CQCreat(int n);
void CQCreat2(CQueue* pcq, int n);
//判断队列空否
bool CQEmpty(CQueue* pcq);
//判断队列满否
bool CQFull(CQueue* pcq);
//入队列
void CQPush(CQueue* pcq, CQDataType x);
//出队列
void CQPop(CQueue* pcq);
//取队头元素
CQDataType CQFront(CQueue* pcq);
//取队尾元素
CQDataType CQBACK(CQueue* pcq);
//销毁队列
void CQDestory(CQueue* pcq);

CircularQueue.c

#include "Queues.h"
//开辟空间，n指开辟大小
void CQCreat2(CQueue* pcq, int n)
{
	pcq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (n + 1));
	pcq->front = pcq->rear = 0;
	pcq->capacity = n;
}
//判断队列空否
bool CQEmpty(CQueue* pcq)
{
	assert(pcq);
	return pcq->front == pcq->rear;//相等为空
}
//判断队列满否
bool CQFull(CQueue* pcq)
{
	assert(pcq);
	return (pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;
}
//入队列
void CQPush(CQueue* pcq, CQDataType x)
{
	assert(pcq);
	assert(!CQFull(pcq));
	pcq->arr[pcq->rear++] = x;
	pcq->rear %= pcq->capacity + 1;
}
//出队列
void CQPop(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	pcq->front++;
	pcq->front %= pcq->capacity + 1;
}
//取队头元素
CQDataType CQFront(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	return pcq->arr[pcq->front];
}
//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	int ret = pcq->rear - 1;
	if (pcq->rear == 0)
	{
		ret = pcq->capacity;
	}
	return pcq->arr[ret];
}
//销毁队列
void CQDestory(CQueue* pcq)
{
	assert(pcq);
	free(pcq->arr);
	pcq->arr = NULL;
	pcq->front = pcq->rear = pcq->capacity = 0;
}


Type x)
{
	assert(pcq);
	assert(!CQFull(pcq));
	pcq->arr[pcq->rear++] = x;
	pcq->rear %= pcq->capacity + 1;
}
//出队列
void CQPop(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	pcq->front++;
	pcq->front %= pcq->capacity + 1;
}
//取队头元素
CQDataType CQFront(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	return pcq->arr[pcq->front];
}
//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{
	assert(pcq);
	assert(!CQEmpty(pcq));
	int ret = pcq->rear - 1;
	if (pcq->rear == 0)
	{
		ret = pcq->capacity;
	}
	return pcq->arr[ret];
}
//销毁队列
void CQDestory(CQueue* pcq)
{
	assert(pcq);
	free(pcq->arr);
	pcq->arr = NULL;
	pcq->front = pcq->rear = pcq->capacity = 0;
}