广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言数据结构与算法之队列的实现详解
  • 896

0
分享到

C语言数据结构与算法之队列的实现详解

C语言数据结构队列C语言队列实现C语言队列 2022-11-13 18:11:14 896人浏览 安东尼
摘要

目录队列的概念及结构队列的实现Queue.hQueue.cTest.c队列的概念及结构 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FI

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的原则

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

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

队列的结构在生活中非常地常见，比如排队时的抽号机就是一个典型的队列结构。那队列如何实现呢？我们一起来看一下。

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些。因为如果使用数组的结构，出队列在数组头上出数据，需要挪动数据，时间复杂度为O(N)，效率会比较低。

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* 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->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}

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

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

	// 队列中没有节点
	if (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(!QueueEmpty(pq));

	// 队列中只有一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

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

	return pq->size == 0;
	//return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

初始化队列

头指针和尾指针都指向空，队列元素个数初始化为0

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

销毁队列

利用while循环将申请的节点一一释放掉，然后头指针pq->head和尾指针pq->tail指向空，栈的数据个数置为 0pq->size = 0

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}

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

数据入队

1.申请新的节点newnode newnode->data = x,newnode->next = NULL

2.数据入队：当pq->tail == NULL时，队列中没有节点，那么头指针和尾指针都赋值为newnode pq->head = pq->tail = newnode；当pq->tail != NULL时，队列中有节点，那么尾部链接上新节点newnode，然后newnode成为新的尾结点。

3.队列数据个数加一pq->size++

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

	// 队列中没有节点
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

数据出队

1.判断队列是否为空

2.数据出队：当pq->head->next == NULL时，队列中只有一个节点，释放该节点，头指针和尾指针都指向空；当pq->head->next != NULL时，释放让头指针指向当前节点的下一个节点，释放原来的头节点

3.队列数据个数减一pq->size--

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	// 队列中只有一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL;
	}

	pq->size--;
}

返回队头数据

先判断队列是否为空，不为空时，返回队头数据。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

返回队尾数据

先判断队列是否为空，不为空时，返回队尾数据。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

判断队列是否为空

判断队列是否为空有两种方式：1.判断pq->size等不等于 0；2.判断头指针pq->head和尾指针pq->tail是否等于空指针NULL

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

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

队列中数据的个数

直接返回队列数据的个数pq->size

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

	return pq->size;
}

Test.c

以下为测试函数接口的代码，大家可以参考一下。需要注意的是，打印队列中的数据是通过打印队头数据、Pop掉队头数据的方式来实现的。

#include "Queue.h"

void QueueTest()
{
	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);
	QueuePush(&q, 6);

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

	QueueDestroy(&q);
}

int main()
{
	QueueTest();

	return 0;
}

以上就是C语言数据结构与算法之队列的实现详解的详细内容，更多关于C语言数据结构 队列的资料请关注编程网其它相关文章！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言数据结构与算法之队列的实现详解

本文链接: https://www.lsjlt.com/news/169591.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言数据结构与算法之队列的实现详解
    目录队列的概念及结构队列的实现Queue.hQueue.cTest.c队列的概念及结构 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FI...
    99+
    2022-11-13
    C语言数据结构 队列 C语言 队列实现 C语言 队列
  • C语言数据结构之队列算法详解
    目录一、前言二、基本概念三、顺序队列四、链队列五、循环队列六、总结与提高一、前言 队列在程序设计中经常出现，如：操作系统中的排队问题。 这篇文章主要介绍了队列的...
    99+
    2022-11-12
  • C语言数据结构之队列的定义与实现
    目录一、队列的性质二、队列的结构三、代码实现头文件功能函数一、队列的性质 上次我们学习栈，了解到栈储存释放数据的方式是：先进后出 而队列与其相反，队列是：先进先出，后进后出。 二、队...
    99+
    2022-11-13
  • C语言数据结构之栈与队列的相互实现
    目录一、用对列实现栈代码实现二、用栈实现队列代码实现一、用对列实现栈 题干要求： 细节分析：队列是先进先出； 要实现的栈是先进后出。 解题思路：假设：先用一个队列储存数据 N 个，...
    99+
    2022-11-13
  • C利用语言实现数据结构之队列
    目录一、链队列二、链队的表示三、链队的基本操作1. 链队的初始化2. 链队的销毁3. 入队4. 出队四、顺序队列五、循环队列1. 初始化2. 求队列长度3. 入队4. 出队 前言： ...
    99+
    2022-11-12
  • C语言数据结构之队列怎么定义与实现
    今天小编给大家分享一下C语言数据结构之队列怎么定义与实现的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。一、队列的性质上次我们...
    99+
    2023-07-02
  • c语言数据结构之栈和队列详解(Stack&Queue)
    目录简介栈一、栈的基本概念1、栈的定义2、栈的常见基本操作二、栈的顺序存储结构1、栈的顺序存储2、顺序栈的基本算法3、共享栈（两栈共享空间）三、栈的链式存储结构1、链栈2、链栈的基本...
    99+
    2022-11-13
  • C语言数据结构之栈与队列怎么相互实现
    本篇内容介绍了“C语言数据结构之栈与队列怎么相互实现”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！一、用对列实现栈题干要求：细节分析：队列是...
    99+
    2023-07-02
  • C语言数据结构与算法之字符串详解
    目录串的定义串的比较 串的抽象数据类型串的初始化相关定义初始化定长类初始化串的堆式顺序存储结构（Heap）初始化堆字符串 赋值操作比较两个堆字符串的大小 串的定义...
    99+
    2022-11-12
  • C语言数据结构不挂科指南之队列详解
    目录队列队列基本概念循环队列顺序队列的 C 语言实现链式队列的 C 语言实现自考要点队列 这篇博客主要介绍一下队列的概念，并且采用 C 语言，编写两种存储实现方式：顺序存储和链式存储...
    99+
    2022-11-13
  • JS数据结构与算法中的队列结构详解
    目录队列结构一.认识队列二.队列的应用三.队列类的创建四.队列的常见操作五.击鼓传花六.优先级队列七.优先级队列的实现队列结构 一.认识队列 受限的线性结构:我们已经学习了一种受限的...
    99+
    2022-11-13
    JS数据结构与算法 JS队列结构
  • C语言数据结构算法基础之循环队列示例
    目录说明示例代码1. 首先定义结构体：2. 定义各种算法：3. 测试：4. 最后的结果：说明 循环队列是一种先进先出的，首尾相连的队列。 大致的结构如下图： 用数组来抽象的表示一下...
    99+
    2022-11-13
  • C语言数据结构进阶之栈和队列的实现
    目录栈的实现：一、栈的概念和性质二、栈的实现思路三、栈的相关变量内存布局图四、栈的初始化和销毁五、栈的接口实现：1.入栈2.出栈3.获取栈顶的数据4.获取栈的元素个数5.判断栈是否为...
    99+
    2022-11-12
  • Java数据结构与算法之循环队列的实现
    目录概述循环队列循环队列实现改变队列大小enqueue 方法dequeue 方法main完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章...
    99+
    2022-11-12
  • Python的数据结构与算法的队列详解(3)
    目录模拟打印机任务队列过程主要模拟步骤：​构建队列程序模拟打印程序模拟打印过程（有注释）总结模拟打印机任务队列过程 计算机科学中也有众多的队列例子。比如计算机实验室有10台计算机，它...
    99+
    2022-11-13
  • Python数据结构与算法中的队列详解(1)
    目录什么是队列？构建一个队列总结什么是队列？ 队列，与栈类似，是有序集合。添加操作发生在 “尾部”，移除操作只发生在 “头部&...
    99+
    2022-11-13
  • Python数据结构与算法中的队列详解(2)
    传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景。考虑这样一个游戏：传土豆。在这个游戏中，成员们围成一圈，并依次尽可能快地传递一个土豆。在某个时刻，大家停止传...
    99+
    2022-11-13
  • Python数据结构与算法的双端队列详解
    目录什么是双端队列​​用Python实现双端队列运用双端队列构建回文检测器总结什么是双端队列​ 双端队列是与队列类似的有序集合。它有一前、一后两端，元素在其中保持自己的位置。与队列不...
    99+
    2022-11-13
  • C语言数据结构不挂科指南之栈&队列&数组详解
    目录学习目标栈基本概念栈的基本运算栈的顺序实现双栈栈的链接实现考试要点小结学习目标 自考重点、期末考试必过指南，这篇文章让你理解什么是栈、什么是队列、什么是数组 掌握栈、队列的顺序存...
    99+
    2022-11-13
  • C++数据结构的队列详解
    目录前言1.队列的概念及结构2.队列的实现2.1queue.h2.2queue.c2.3test.c总结前言 hello，大家好，这期文章我们来分享数据结构关于队列的知识。希望对大家...
    99+
    2022-11-12
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作