数据结构—队列的实现

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

前言:上次我们已经学习了数据结构中一个重要的线性表—栈,那么我们这一次就来学习另外一个重要的线性表—队列。

数据结构—队列的实现,数据结构,数据结构,c语言

目录:

一、
队列的概念
二、
队列的实现:
1.队列的创建
三、
队列的操作
1.初始化队列
2.队尾入队列
3.队头出队列
4.获取队列头部元素
5.获取队列队尾元素
6.获取队列中有效元素个数
7.检测队列是否为空,如果为空返回非零结果,如果非空返回0
8.销毁队列
四、
完整代码展示

队列的概念

队列的概念及结构:队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。
数据结构—队列的实现,数据结构,数据结构,c语言

队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
数据结构—队列的实现,数据结构,数据结构,c语言
我们用三个文件来完成对它的操作。

队列的创建:

typedef int QDataType;
// 链式结构:表示队列
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

队列的实现:

队列的初始化:

void QueueInit(Queue* pq)
{
	assert(pq);
	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->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

如果我们的队尾元素为空,那么我们的队尾就是newnode,如果我们的队尾不为空,我们的ptail的下一个指向newnode,现在的队尾就为newnode。

队头出队列:

void QueuePop(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;

	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}

如果我们直接删除队头元素那么我们就无法访问下一个元素,所以我们先把队头元素保存起来,让现在的队头元素为原来队头元素的下一个元素,在给原来的队头元素删除。

获取队列头部元素:

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	return pq->phead->val;
}

获取队列队尾元素:

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->ptail);

	return pq->ptail->val;
}

获取队列中有效元素个数:

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

size就是我们有效元素的个数,这里返回size就可以了。

检测队列是否为空,如果为空返回非零结果,如果非空返回0:

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

队列为空返回0,不为空返回非0,后面测试代码的循环条件就是不为0,就输出,为0就跳出循环。

销毁队列:

void QueueDestroy(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;
}

完整代码展示:

Queue.h:

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

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

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

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

Queue.c:

#include"Queue.h"

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

void QueueDestroy(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->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;

	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->ptail);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

代码测试:
test.c:

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

	QueuePush(&q, 4);
	QueuePush(&q, 5);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	QueueDestroy(&q);

	return 0;
}

这里我们先入队1,2,3,队头就是1,队尾就是3,我们在出队,先输出1,在把1出队,这样我们就访问2,在输出2之后把2出队,入队4,5,如果我们的队列不为0就输出3,4,5。最后输出的结果如下图:
数据结构—队列的实现,数据结构,数据结构,c语言

相信大家一定可以完美的拿捏队列,感谢各位小伙伴的支持,我们下期再见!文章来源地址https://www.toymoban.com/news/detail-759921.html

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

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

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

相关文章

  • 数据结构-队列的实现(C语言版)

    前言         队列是一种特殊的线性表,它只允许在一端对数据进行插入操作,在另一端对数据进行删除操作的特殊线性表,队列具有先进先出的(FIFO)的 特性,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。         队尾:元素在队尾入队。插入操作。

    2024年02月13日
    浏览(48)
  • 数据结构-队列(C语言的简单实现)

    队列也是一种数据结构,队列也可以用来存放数字 每次只能向队列里将入一个数字,每次只能从队列里获得一个数字 在队列中,允许插入的一段称为入队口,允许删除的一段称为出队口 它的原则是先进先出(FIFO: first in first out),先进入队列的数据先出去,后进入的后出去。

    2024年02月13日
    浏览(46)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(41)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(40)
  • (详解)数据结构-----------栈与队列 c语言实现

    本章将会详细讲解以下知识点: 目录 一:栈         1:栈的定义,栈的特点         2:用什么结构来实现栈与原因的分析?         3:  (超详解)栈的常用接口并且附上测试用例 二:队列         1:队列的定义,队列的特点         2:用什么结构来实现队列与原因的分析

    2024年02月11日
    浏览(44)
  • 入门数据结构,c语言实现循环队列实现(详细篇)。

    目录 一、前言 二、循环队列的概念 三、实现循环队列 1、头文件与特殊函数介绍 2、循环队列的结构体 3、队列的初始化 4、判断队列是否为空 5、队列的进队操作 6、队列的出队操作 7、返回队头 8、返回队列长度 9、放回队列容量大小 10、销毁队列 四、完成队列(队列完整代

    2024年02月06日
    浏览(45)
  • 【数据结构】队列基本操作的实现(C语言)

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🐌 个人主页:蜗牛牛啊 🔥 系列专栏:🛹数据结构、🛴C++ 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与

    2024年02月16日
    浏览(49)
  • 数据结构入门(C语言版)栈和队列之队列的介绍及实现

    什么是队列呢?我们先看下面的图: 我们可以理解成高速公路上的隧道,根据这个图的描述 我们把需入队的元素看作一辆车,把队列看作隧道,由此我们可以看出 队列的特点是 只允许从一端进入,从另一端离开。 队列就是只允许在一端进行插入数据操作,在另一端进行删

    2023年04月15日
    浏览(38)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(55)
  • 【数据结构】详谈队列的顺序存储及C语言实现

    大家好,很高兴又和大家见面啦!!! 在上一篇内容中,我们在介绍完队列的基本概念、重要术语以及基本操作后,又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。 队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义

    2024年01月21日
    浏览(73)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包