【数据结构】队列的实现

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

(一)队列定义

队列是一种常用的数据结构,也是一种操作受限制的线性表,特点是只允许在表的头部进行删除操作,在表的尾部进行插入操作,队列具有先进先出FIFO(First In First Out)。

入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头

我们实现可以用数组和链表结构实现,但使用链表更优,如果去用数组实现啊,出队列在数组头上出数据,效率会很低 ,需要挪动n次,时间复杂度为O(N)。

(二)队列实现

(1)创建结构体

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

我们要创建两个结构体,一个表示链式结构,即队列,第二个是队列的结构。
先使用typedef int QDateType,是为了方便改类型,在结构体里创建2个成员变量,分别表示结点的数据域和指针域,之后创建队列里的结构体,在里面创建两个指针变量分别指向队列的头部和尾部,size记录队列的个数。

(2)具体函数实现及解析

1.1 初始化队列

void QueueInit(Queue* qq)//队列初始化
{
	assert(qq);
	qq->head = qq->tail = NULL;
	qq->size = 0;

}

初始化队列,传一级指针改变的是结构体,只需要结构体指针,qq是不能为空的,所以需要断言防止人为穿空,把头指针和尾指针置空,size置0。

1.2入队列

void QueuePush(Queue* qq, QDataType x)//入队列
{
	assert(qq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	if (qq->tail == NULL)
	{
		qq->head = qq->tail = newnode;
	}
	else
	{
		qq->tail->next = newnode;
		qq->tail = qq->tail->next;
	}
	qq->size++;
}

入队列其实就是尾插,先malloc申请一个结点,再判断是否为空,再把结点数据域和指针域分别给上x和空,再进行尾插:判断尾或者头是否为空,为空则把它们指向新节点,反之,把新节点链在尾部,并更新尾部,最后插入完把size++。

1.3出队列

void QueuePop(Queue* qq)//出队列
{
	assert(qq);
	assert(!QueueEmpty(qq));
	if (qq->head->next == NULL)
	{
		free(qq->head);
		qq->head = qq->tail = NULL;
	}
	else
	{
		QNode* del = qq->head;
		qq->head = qq->head->next;
		free(del);
	}
	qq->size--;
	
}

出队列是进行头删,除了断言qq是否为空,还要判断整个队列是否为空,空的时候不能删。头删如果只有一个结点,直接free,并把头和尾置空;否则先把头部存在del指针变量中,再更新头结点,释放del。最后size个数–。

1.4取队首元素

QDataType QueueFront(Queue* qq)//取队列首元素
{
	assert(qq);
	assert(!QueueEmpty(qq));
	return qq->head->data;


}

取队首也需要断言,直接返回头部指向的数据。

1.5取队尾元素

QDataType QueueBack(Queue* qq)//取队列尾元素
{
	assert(qq);
	assert(!QueueEmpty(qq));
	return qq->tail->data;

}

取队尾直接返回尾部指向的数据。

1.6返回队列个数

int QueueSize(Queue* qq)//返回队列个数
{
	assert(qq);
	return qq->size;
}

返回队列个数,返回qq指向的个数。

1.7判断是否为空

bool QueueEmpty(Queue* qq)//判断是否为空
{
	assert(qq);
	return qq->head == NULL &&qq->tail == NULL;

}

判断是否为空,直接返回head和tail同时为空,如果同时为空返回true,有一个不为空返回false。

1.8销毁队列

void QueueDestroy(Queue* qq)//销毁队列
{
	assert(qq);
	QNode* cur = qq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	qq->head = qq->tail = NULL;
	qq->size = 0;
}

队列销毁需要把头指针存到cur中,用while循环,把cur存到del指针变量中,更新cur,并释放掉del。最后把头指针和尾指针同时置为空,size置0。

(三)队列实现代代码

(1)Queue.c

#include"Queue.h"
void QueueInit(Queue* qq)//队列初始化
{
	assert(qq);
	qq->head = qq->tail = NULL;
	qq->size = 0;

}

void QueuePush(Queue* qq, QDataType x)//入队列
{
	assert(qq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	if (qq->tail == NULL)
	{
		qq->head = qq->tail = newnode;
	}
	else
	{
		qq->tail->next = newnode;
		qq->tail = qq->tail->next;
	}
	qq->size++;
}

void QueuePop(Queue* qq)//出队列
{
	assert(qq);
	assert(!QueueEmpty(qq));
	if (qq->head->next == NULL)
	{
		free(qq->head);
		qq->head = qq->tail = NULL;
	}
	else
	{
		QNode* del = qq->head;
		qq->head = qq->head->next;
		free(del);
	}
	qq->size--;
	
}

QDataType QueueFront(Queue* qq)//取队列首元素
{
	assert(qq);
	assert(!QueueEmpty(qq));
	return qq->head->data;


}

QDataType QueueBack(Queue* qq)//取队列尾元素
{
	assert(qq);
	assert(!QueueEmpty(qq));
	return qq->tail->data;

}

int QueueSize(Queue* qq)//返回队列个数
{
	assert(qq);
	return qq->size;
}

bool QueueEmpty(Queue* qq)//判断是否为空
{
	assert(qq);
	return qq->head == NULL &&qq->tail == NULL;

}

void QueueDestroy(Queue* qq)//销毁队列
{
	assert(qq);
	QNode* cur = qq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	qq->head = qq->tail = NULL;
	qq->size = 0;
}

(2)Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue* qq);//队列初始化

void QueuePush(Queue* qq,QDataType x);//入队列

void QueuePop(Queue* qq);//出队列

QDataType QueueFront(Queue* qq);//取队列首元素

QDataType QueueBack(Queue* qq);//取队列尾元素

int QueueSize(Queue* qq);//返回队列个数

bool QueueEmpty(Queue* qq);//判断是否为空

void QueueDestroy(Queue* qq);//销毁队列

(3)test.c

#include"Queue.h"
void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 9);
	QueuePush(&q, 8);

	printf("%d ", QueueFront(&q));
	QueuePop(&q);

	QueuePush(&q, 7);
	QueuePush(&q, 6);

	printf("%d\n", QueueEmpty(&q));
	printf("%d\n", QueueFront(&q));
	printf("%d\n", QueueBack(&q));

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

	printf("%d\n", QueueSize(&q));
}
int main()
{
	test();
	return 0;
}

(四)队列测试结果

队列的实现,数据结构,java,链表,算法,开发语言文章来源地址https://www.toymoban.com/news/detail-781054.html

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

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

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

相关文章

  • 【Java数据结构】顺序表、队列、栈、链表、哈希表

    是一个有类型参数(type parameter)的范型表(generic class) 能够自动调整容量,并且不需要写额外的代码 存放数据使用数组但是可以编写一些额外的操作来强化为线性表,底层依然采用顺序存储实现的线性表,称为顺序表 创建 常见操作 一旦确认数组列表大小恒定,不再发生

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

    初始化 判断队列是否为空 入队 初始化 判断队列是否为空 入队 队满 链式存储――一般不会队满,除非内存不足

    2024年02月11日
    浏览(47)
  • 数据结构:队列(链表和数组模拟实现)

    目录 1.何为队列 2.链表模拟实现 2.1 节点和队列创建 2.2 初始化队列 2.3 入队操作 2.4 出队操作 2.5 遍历队列 2.6 获取队首和队尾元素 2.7 判断队列是否为空 2.8 完整实现 3. 数组模拟实现 3.1 创建队列 3.2 入队和出队操作 3.3 遍历队列 3.4 获取队首和队尾元素  3.5 判断队列是否为空

    2024年02月03日
    浏览(53)
  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(50)
  • Java常见的数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出,先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(45)
  • 【Java数据结构 -- 队列:队列有关面试oj算法题】

    只允许在一端进行插入数据操作,在另一端进行删除数据操作得特殊线性表,队列是 先进先出 ,入队:进行插入操作得一端称为 队尾(rear) ,出队:进行删除操作的一端称为 队头(front) 。队列Queue是个接口, 底层通过链表实现的 。 boolean offer(E e) – 入队列 E poll() – 出队

    2024年01月25日
    浏览(47)
  • 【数据结构与算法】队列的实现

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先

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

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

    2024年01月20日
    浏览(45)
  • 【数据结构与算法】用队列实现栈

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年01月15日
    浏览(37)
  • 【算法与数据结构】队列的实现详解

    队列的概念: 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列特征如

    2024年04月13日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包