【数据结构】队列详解网站首页 技术杂谈

【数据结构】队列详解

王笃笃 2024-06-17 11:19:14

简介【数据结构】队列详解

本篇要分享的内容是队列的解析和增删查改的使用，以下为本篇目录

1.队列的概念及结构

队列的结构和栈完全相反，栈只能再栈顶进再从栈顶出，遵从后进先出（LIFO）；而队列

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，遵循的是先进先出，后进后出。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头，队列的图示如下

那这里有一个小问题，如果入队列的顺序是1，2，3，4，那出队列的顺序也是1，2，3，4吗？

是的，出队列的顺序一定是1，2，3，4，并且无论在什么情况下都是1，2，3，4，永远都能保持先进先出，所以抽号机的原理就是用队列来实现的。

当然队列也分数组队列和链式队列，在这里我们研究链式队列是会对实际操作更方便一些的，因为队列需要操作的是队头和队尾，所以就要涉及到头部删除和尾部插入，而链表的插入和删除相对较容易一些，所以我们选择研究链式队列。

2.队列的结构

既然是链式队列，并且只能头出尾进

那自然就会想到单链表的结构，所以我们可以先定义一个单链表的结构

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

但是仅仅这一个结构体是不够的，为什么呢？

我们要从测试的角度来看

int main()
{
	QNode* phead = NULL;
	QNode* tail = NULL;
	int size = 0;
	return 0;

}

首先我们需要定义两个结构体，从命名上不难看出一个指向队头，一个指向队尾，当然也可以定义size来测量队列的大小。

如果我的队列中要存放多个数据该如何操作呢？

单链表中的每个结点都有两个部分组成：一个Data和一个next，

我们不妨在定义一个结构体，将整个队列的队头和队尾都记录下来，代码如下

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

那这串代码就记录的是整个队列的头和尾了

结合图示来看就是这个样子，应该不难理解。

3.队列的初始化

初始化是非常简单的，只需要将队列内置空即可

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

4.队列空间释放

释放队列空间也非常简单，因为是单链表式的结构所以要一个一个的释放空间，代码如下

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail=NULL;
	pq->size = 0;
}

首先用asset来断言整个链表是否为空；

然后使用结构体指针cur来保存phead的位置，然后操作cur；

当cur不为空的时候就用结构体指针再定义一个next用来保存cur的next；

然后释放掉当前的cur的空间，再用next赋给cur，这样next就成为了新的cur，完成迭代；

当然如果cur为空时，那么整个队列也为空（QNode* cur = pq->phead），所以phead和ptail就可以直接置空，size也为0；

队列的置空和单链表的置空并没有太大差异，如果忘记了操作可以复习单链表销毁空间的操作。

5.入队

和单链表尾插大差不差，同样要判断链表中是否为空，这里不仅要判断队头还要判断队尾

void QueuePush(Queue* pq, QDataType x)
{
	
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;


    //只有一个结点的情况
	if (pq->ptail == NULL)
	{
		assert(pq->phead==NULL);
		pq->phead = pq->ptail = newnode;

	}
    
    //多个节点
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

入队和单链表中的尾插操作大差不差，所以要先找尾，然后malloc一段新的空间出来再插入数据、并且成为新的尾结点；

需要注意的时phead和ptail都需要判断，这样才能知道哪个结点是空；

所以还需要分成一个结点和多个结点的情况来讨论。

6.出队

出队和单链表的头部删除操作相似，所以还是要分一个结点和多个结点的情况来讨论。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

当只有一个结点时我们需要判断phead的next是否为空，也就是第二个结点是否为空，如果第二个结点没有数据那就为空，所以直接free掉第一个结点（pq->next）即可。

如果有多个结点的话，那就再定义一个新的结点，来保存当前节点的下一个结点；

再把当前节点的空间free掉；

再将新的结点赋值给phead使其成为新的头节点；

最后要给队列中元素的计数size--；

7.获取队头和队尾元素

获取元素类似于查找函数，所以要注意函数的返回值是最开始typedef好的类型；

代码也非常简单，只需要用结构体访问数据内容即可；

获取对头

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;
}

相信代码不难看懂；

8.计算队列元素

只需用结构体访问size即可

int QueueSize(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->size;
}

9.判空

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

思路也非常简单，根据图标来看判断头节点为空即可。

也可以使用size来看

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	/*return pq->phead == NULL;*/
	return pq->size==0;
}

当然如果是要用size来判空的话入队和出队的代码一定要记录好size，不要忘记给size的自加和自减。10.队列元素展现

和栈的展现相似，我们需要边出队边将其内容展现，以下是测试代码

#include"Queue.h"
int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("
");


	QueueDestory(&q);
	return 0;

}

可以看到这里和队列展现的方式是相同的，需要访问一个弹出一个,运行结果如下。

当我们中途将数据弹出会怎样呢？

结果是一样的，因为队列的入栈顺序规定的就是先入先出。

11.本篇所有代码展示

Queue.c

#include"Queue.h"
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	/*return pq->phead == NULL;*/
	return pq->size == 0;
}


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail=NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
	
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		assert(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->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* 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);
	assert(!QueueEmpty(pq)); 
	return pq->size;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

test.c

#include"Queue.h"
int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("
");


	QueueDestory(&q);
	return 0;

}

以上就是本篇所要分享关于队列的增删查改的所有内容，如果对你有所帮助还请三连支持，感谢您的阅读。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。