详解数据结构之队列、循环队列(源码)
队列属于线性表
队列:就好比如,我们在排队买东西时排队,第一个先来的第一个买,最后一个到的最后一个买,这里的队列也是满足先进先出,后进后出的规律(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;
}