首页 > 其他分享 >数据结构之队列详解

数据结构之队列详解

时间：2024-07-25 21:53:43浏览次数：6  
标签：head pq cur 队列 NULL Queue 详解 数据结构

1.队列的概念以及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFo(Frist in Frist out)的特性

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

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

2.队列的实现

队列也可以使用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会很低

队列常见的基本操作：

//初始化
void QueueInit(Queue* pq);
//清空队列成员
void QueueDestroy(Queue* pq);
//队尾插入元素
void QueuePush(Queue* pq, QDataType x);
//删除队队头元素，队列先进先出
void QueuePop(Queue* pq);
//获取队头元素
int QueueFront(Queue * pq);
//获取队尾元素
int QueueBack(Queue* pq);
//获取队列中有效与元素个数
int QueueSize(Queue* pq);
//查看队列是否为空
bool QueueEmpty(Queue* pq);

每个功能的实现以及解释

实现队列这里我们使用的是动态顺序表

->1.初始化队列

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

->2.清空队列成员

//清空队列成员
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	//QNode* cur = pq->head->next;

	while (cur)
	{
		/*free(pq->head);
		pq->head = cur;
		cur = cur->next;*/
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

->3.队尾插入元素

//队尾插入元素
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (NULL == newnode)
	{
		perror("QueuePsuh::malloc");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

->4.删除队队头元素，队列先进先出

//删除队列成员，队列先进先出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

    //第一种方法
	//Queue* cur = pq->head;
	//if (cur->next == NULL)
	//{
	//	free(cur);
	//	pq->head = pq->tail = NULL;
	//}
	/*else
	{
		pq->head = cur->next;
		free(cur);
		cur = NULL;
	}*/

    //第二种方法
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}

	pq->size--;
}

->5.获取队头元素

//获取队头成员
int QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

->6.获取队尾元素

//获取队尾成员
int QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

->7.获取队列中有效元素个数

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

->8.查看队列是否为空

//查看队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0; //pq->head == NULL && pq->tail == NULL
}

3.完整代码

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>

typedef int QDataType;

typedef struct QListNode 
{
	struct QListNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	QDataType size;
}Queue;



//初始化
void QueueInit(Queue* pq);
//清空队列成员
void QueueDestroy(Queue* pq);
//队尾插入队列
void QueuePush(Queue* pq, QDataType x);
//删除队队头元素，队列先进先出
void QueuePop(Queue* pq);
//获取队头元素
int QueueFront(Queue * pq);
//获取队尾元素
int QueueBack(Queue* pq);
//获取队列中有效与元素个数
int QueueSize(Queue* pq);
//查看队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c

#include "queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

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

	QNode* cur = pq->head;
	//QNode* cur = pq->head->next;

	while (cur)
	{
		/*free(pq->head);
		pq->head = cur;
		cur = cur->next;*/
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//插入队列成员
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (NULL == newnode)
	{
		perror("QueuePsuh::malloc");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

//删除队列成员，队列先进先出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	//Queue* cur = pq->head;
	//if (cur->next == NULL)
	//{
	//	free(cur);
	//	pq->head = pq->tail = NULL;
	//}
	/*else
	{
		pq->head = cur->next;
		free(cur);
		cur = NULL;
	}*/

	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}

	pq->size--;
}

//获取队头成员
int QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

//获取队尾成员
int QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

//查看队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0; //pq->head == NULL && pq->tail == NULL
}

test.c

#include "queue.h"

int main()
{
	Queue st;
	QueueInit(&st);

	QueuePush(&st, 1);
	QueuePush(&st, 2);
	QueuePush(&st, 3);
	QueuePush(&st, 4);
	QueuePush(&st, 5);

	while (!QueueEmpty(&st))
	{
		printf("%d ", QueueFront(&st));
		QueuePop(&st);
	}
	printf("\n");

	return 0;
}

测试结果:

标签：head,pq,cur,队列,NULL,Queue,详解,数据结构
From： https://blog.csdn.net/m0_73634434/article/details/140660382

相关文章

  • Profinet转ModbusTCP网关模块的配置与应用详解
    Profinet转ModbusTCP网关模块的配置与应用详解Profinet转ModbusTCP网关模块（XD-ETHPN20）是一种常见的工业通信设备，广泛应用于现代工业自动化系统中。通过使用Profinet转ModbusTCP网关模块（XD-ETHPN20）将Profinet协议转换成ModbusTCP协议，实现了不同网络之间的互联互通。这种网关设备......
  • 多校数据结构
    多校数据结构省选选手不再需要学习新数据结构，主要需要学习数据结构题目的常见套路，训练代码能力，提升思维能力。因此，此次授课主要提供各种类型的数据结构题目，点拨解题思路，为选手在比赛中处理各类数据结构问题提供参考。[CF1039D]YouAreGivenaTree题目描述有一棵\(n\)个......
  • pdf文件压缩的有效方法，详解5个效果高效的文件压缩方法汇总！
    在现代信息社会中，PDF文件已经成为我们日常工作和学习中不可或缺的重要载体。然而，随着PDF文件内容的增多和复杂化，文件大小的膨胀也成为一个常见问题，给存储、共享和传输带来了不少挑战。本文旨在探讨如何通过有效的压缩方法来解决pdf文件过大的问题。我们将详细介绍五种高效......
  • 栈，队列，链表
     栈堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈......
  • 一文彻底搞懂浏览器事件机制、事件委托、事件冒泡、事件循环、Event Loop、react事件
    一、事件是什么？事件模型？事件是用户操作网页时发生的交互动作，比如click/move，事件除了用户触发的动作外，还可以是文档加载，窗口滚动和大小调整。事件被封装成一个event对象，包含了该事件发生时的所有相关信息（event的属性）以及可以对事件进行的操作（event的方法）。事件是用......
  • 通过“ 栈 ”实现“ 队列 ”
                  ......
  • 黑暗之魂2缺失steam_api.dll该如何处理？全面解读《黑暗之魂2》steam_api.dll丢失及高效
    在游戏的世界中，《黑暗之魂2》凭借其独特的魅力吸引了众多玩家。然而，有时玩家会遭遇steam_api.dll文件丢失的困扰，这无疑给游戏体验带来了极大的阻碍。在这篇文章中，我们将为您进行全面解读。首先深入剖析steam_api.dll文件丢失的原因。可能是由于游戏安装过程中的错误、系统更新......
  • 数据结构--第一天
    --顺序表    -顺序表的概念     顺序表实际上就是数组，数组在进行封装后，可以进行增删改查操作，就成了顺序表    -顺序表相关函数      malloc函数        框架：int* p=(int*)malloc(sizeof(int));      ......
  • 【C++】再探构造函数 - 初始化列表详解
    ......
  • 数据结构-2. 动态数组1
    动态数组设计structdynamicArray{ void**pAddr;//维护真实在堆区创建的数组的指针 intm_capacity;//数组容量 intm_size;//数组大小};数组初始化structdynamicArray*init_DynamicArry(intcapacity){ if(capacity<=0) { returnNULL; } //给数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99