数据结构队列的实现

这篇具有很好参考价值的文章主要介绍了数据结构队列的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构队列的实现,数据结构
本章介绍数据结构队列的内容,我们会从队列的定义以及使用和OJ题来了解队列,话不多说,我们来实现吧

队列

1。队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出
FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。
我们来看一下下面的这张图,让我们更好的理解它
数据结构队列的实现,数据结构
我们从队尾入,队头出,只能是这样入栈和出栈

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

那队列的实现我们是用链式结构来实现的,因为用数组下标的话,出栈的时候要往前挪动数据,会更麻烦,这样队列的意义就下降了,所以我们这里用的方法是链式结构。

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType* next;
	QueueDataType data;
}QueueNode;

typedef struct Queue
{
	QueueDataType* head;
	QueueDataType* tail;
}Queue;

这里我们定义的结构体Queue有很大的作用,因为队列不是像单链表那样,队列是有它的特点的,其中最大的一个特点就是入栈只能从尾入,出栈就是头出,所以我们在这里定义head和tail有很大的作用,定义在结构体当中会方便不少,那我们现在继续往下看我们的接口函数吧。

给大家看一下下面实现队列的接口函数,然后我们一步一步的来实现他们

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

队列的初始化

void QueueInit(Queue* q); 

初始化我们初始的是结构体Queue中的内容

void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
}

首先要判断传过来的指针是否是为空,然后将头指针和尾指针都置为NULL。

销毁队列

void QueuePush(Queue* q, QueueDataType data)

首先我们要创造一个节点将它放入,创造节点的结构体就是QueueNode,然后我们要更新后面节点中的head和tail,这里大家肯定有疑问,我们竟然是更新指针,那我们应该传指针的地址才能起到作用,一级指针只能改变结构体的内容,那我们在这里传的话,难道不会产生问题吗?答案是不会,我们的结构体中放的就是指针,那我们只需要改变结构体的内容,就是head和tail就行,竟然是这样的话,我们传一个一级指针就可以起到我们的作用,所以传的是一级,那现在我们在插入函数中先创造一个节点,因为只能从队列的尾插入,而且有了这个指针,我们就不需要像单链表那样再去找尾,我们每次插入都会更新尾。

void QueuePush(Queue* q, QueueDataType data)
{
	assert(q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}

有了入栈就有出栈,出栈的话是从我们的队列最开始的地方出队,我们来实现一下吧!

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* headnext = q->head->next;
	free(q->head);
	q->head = headnext;

}
/

这里的空是因为如果我们的队列都是空的话,我们哪里还有数据进行删除呢
所以要先检查一下是不是为空,那接着我们把这个函数也实现一下吧

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}

这个很好理解,如果为空就代表一个数也没有,那我们就不能再对队列进行操作了,那再来看我们下面的接口函数吧。

// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
	assert(q);
	return q->head->data;
}

有头就有尾,希望我们的人生也是
那我再来实现一下取尾的接口吧

QueueDataType QueueBack(Queue* q)
{
	assert(q);
	return q->tail->data;
}

我们继续往下走,实现一下我们后面的接口函数,这些基本上都很简单,我就也不再解释了,看代码就能理解的

int QueueSize(Queue* q)
{
	assert(q);
	int count = 0;
	QueueNode* cur = q->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

销毁队列

void QueueDestroy(Queue* q)
{
	while (!QueueEmpty(q))
	{
		QueueNode* headnext = q->head->next;
		free(q->head);
		q->head = headnext;
	}

}

统计我们队列节点的数量我们遍历一遍就可以实现了,定义一个cur指针进行遍历,那其他的我们也都讲完了,后面分享栈和队列的OJ题给大家,看完之后对队列有了更深的理解

完整代码

#include"Queue.h"

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{
	assert(q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}
// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* headnext = q->head->next;
	free(q->head);
	q->head = headnext;

}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
	return q->head->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{
	return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	int count = 0;
	QueueNode* cur = q->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	while (!QueueEmpty(q))
	{
		QueueNode* headnext = q->head->next;
		free(q->head);
		q->head = headnext;
	}

}

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

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType* next;
	QueueDataType data;
}QueueNode;

typedef struct Queue
{
	QueueDataType* head;
	QueueDataType* tail;
}Queue;

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

今天的分享就到这里了,我们下次再见文章来源地址https://www.toymoban.com/news/detail-675472.html

到了这里,关于数据结构队列的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——队列的实现

    队列 ,又称为伫列(queue),计算机科学中的一种抽象资料类型,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。 这段代码使用 typedef 定义了一个

    2024年02月10日
    浏览(35)
  • 【数据结构】:队列的实现

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如

    2024年02月07日
    浏览(36)
  • 【数据结构—队列的实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、队列 1.1队列的概念及结构 二、队列的实现 2.1头文件的实现—Queue.h 2.2源文件的实现—Queue.c 2.3源文件的测试—test.c 三、测试队列实际数据的展示 3.1正常队列的出入 3.2入队列的同时存

    2024年02月04日
    浏览(40)
  • 【数据结构】队列及其实现

    目录 😎前言 认识队列 队列的初始化 队列判空 数据队尾入队 数据队头出队 取队头数据 取队尾数据 队列数据的个数 队列销毁 总结 上次我们学习了栈及其实现,当然也少不它的好兄弟队列啦,今天我们开始队列的学习 队列的性质是 先进先出 ,就比如车辆进出隧道一般,它

    2024年02月09日
    浏览(43)
  • 数据结构 | 队列的实现

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如

    2024年02月05日
    浏览(41)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、

    2024年01月20日
    浏览(45)
  • 【数据结构】 队列(Queue)与队列的模拟实现

    队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有==先进先出FIFO(FirstIn First Out) ==入队列: 进行插入操作的一端称为 队尾(Tail/Rear) 出队列: 进行删除操作的一端称为 队头(Head/Front) 在Java中, Queue是个接口,底层是通过链表实现

    2024年02月11日
    浏览(49)
  • 数据结构——队列(C++实现)

    目录 队列的概念及结构  队列的实现 队列的代码实现 完整的源文件代码 总结 推荐题目巩固知识 队列:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,队列最重要的特性是 先进先出 (First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列

    2024年02月07日
    浏览(41)
  • 数据结构-用栈实现队列

    前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否

    2023年04月08日
    浏览(89)
  • 数据结构:线性表(队列实现)

    队列:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,队列具有先进先出(FIFO)的特性. 进行插入操作的一端称为 队尾 ;进行删除操作的一端叫做 队头 队列应用于 解决公平性排队(抽号机) 广度优先遍历(BFS) 和栈一样,队列也可以使用两种物理结构进行存储

    2024年02月09日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包