广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言 队列的实现全解析
  • 236

0
分享到

C语言 队列的实现全解析

2024-04-02 19:04:59 236人浏览 八月长安
摘要

目录队列的实现基本概念创建结构体初始化结构体销毁队列结构体入队出队判断队列是否为空访问对头的值访问队尾的值返回队列的长度Queue.hQueue.cTest.c队列的实现 基本概念

队列的实现

基本概念

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

FIFO(First In First Out)

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

在这里插入图片描述

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低需要挪动数据O(N)。而链表结构头删只需要O(1)。尾插定义一个尾指针，也只需要O(1)。

在这里插入图片描述

创建结构体

这是一个嵌套结构体。

实参q的地址传给了形参pq。pq就是一个指向结构体Queue的指针。Queue里面的head是指向队列对头的指针，tail是指向队尾的指针。

在这里插入图片描述

int main()
{
//创建结构体变量q
//需要传q的地址过去。
	Queue q;

	return 0;
}

定义一个尾指针tail方便入队的尾插。头指针head方便出队时的头删。

typedef int QDataType;
//节点结构体
typedef struct Queuenode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
//头指针和尾指针的结构体
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

初始化结构体

才开始还没有创建队列的空间，所以只需要初始化第一个结构体就ok了。队列初始状态需要对头和队尾指向同一位置，且都是空。

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

销毁队列结构体

这次我把销毁结构体放在初始化结构体的后面，原因是内存泄漏很严重，但是经常会忘记销毁结构体。创建意味着就要销毁，二者对立，所以排在初始化的后面，理所应当。

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

入队

入队的时候，会创建新的节点。最好最好把新开的newnode节点初始化。把他的next置为空，方便后期求队列长度函数，和出队函数的循环条件的书写。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	//下面两个初始化很有必要
	newnode->data = x;
	newnode->next = NULL;

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

出队

因为Queue结构体不可能为空,所以需要断言

还需要断言pq->head和tail都不为空。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

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

判断队列是否为空

为空返回true，为假返回false

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

	return pq->head == NULL;
}

访问对头的值

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

	return pq->head->data;
}

访问队尾的值

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

	return pq->tail->data;
}

返回队列的长度

长度不可能为负数，所以返回类型为size_t

size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

Queue.h

#pragma once

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

typedef int QDataType;

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

typedef struct Queue
{
	QNode* head;
	QNode* tail;

	//size_t size;
}Queue;

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

Queue.c

#include "Queue.h"

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

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);

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

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

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

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

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


	return pq->head == NULL;
}

size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

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

	return pq->head->data;
}

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

	return pq->tail->data;
}

Test.c

void TestQueue()
{
	Queue q;
	QueueInit(&q);

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

	QueuePush(&q, 3);
	QueuePush(&q, 4);

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

int main()
{

	TestQueue();

	return 0;
}

到此这篇关于C语言 队列的实现全解析的文章就介绍到这了,更多相关C语言 队列内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

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

--结束END--

本文标题: C语言 队列的实现全解析

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

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

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

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

下载Word文档
去做题
猜你喜欢
  • C语言 队列的实现全解析
    目录队列的实现基本概念创建结构体初始化结构体销毁队列结构体入队出队判断队列是否为空访问对头的值访问队尾的值返回队列的长度Queue.hQueue.cTest.c队列的实现 基本概念 ...
    99+
    2022-11-13
  • C语言循环队列与用队列实现栈问题解析
    目录循环队列题目描述题目链接思路分析代码实现用队列实现栈题目描述题目链接思路分析代码实现循环队列 循环队列： 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并...
    99+
    2022-11-13
  • C语言实现队列的示例详解
    目录前言一. 什么是队列二. 使用什么来实现栈三. 队列的实现3.1头文件3.2 函数的实现四.完整代码前言 前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链表，双向循环链...
    99+
    2022-11-13
  • C语言详解链式队列与循环队列的实现
    目录队列的实现链式队列链式队列的定义链式队列的实现循环队列循环队列的定义循环队列的实现队列的实现 队列是一种先进先出（First in First Out）的线性表，简称FIFO。与...
    99+
    2022-11-13
  • C语言队列怎么实现
    今天小编给大家分享一下C语言队列怎么实现的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。队列的实现基本概念队列：只允许在一端进...
    99+
    2023-06-29
  • C语言如何实现队列
    这篇文章主要介绍了C语言如何实现队列的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C语言如何实现队列文章都会有所收获，下面我们一起来看看吧。一. 什么是队列队列是一种特殊的线性表，特殊之处在于它只允许在表的前端...
    99+
    2023-07-02
  • C语言简明讲解队列的实现方法
    目录前言队列的表示和实现队列的概念及结构代码实现束语前言 大家好啊，我又双叒叕来水博客了，道路是曲折的，前途是光明的，事物是呈螺旋式上升的，事物最终的发展结果还是我们多多少少能够决定...
    99+
    2022-11-13
  • C语言中队列的示例分析
    这篇文章将为大家详细讲解有关C语言中队列的示例分析，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。一、队列（Queue）0x00 队列的概念 概念：① 队列只允许在一端进行插入数据操作，在另一端进...
    99+
    2023-06-29
  • C语言栈与队列相互实现详解
    目录一、本章重点二、队列实现栈三、栈实现队列四、解题思路总结一、本章重点 用两个队列实现栈用两个栈实现队列解题思路总结 二、队列实现栈  我们有两个队列：  ...
    99+
    2022-11-13
  • C语言链式队列与循环队列怎么实现
    这篇文章主要介绍了C语言链式队列与循环队列怎么实现的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C语言链式队列与循环队列怎么实现文章都会有所收获，下面我们一起来看看吧。队列的实现队列是一种先进先出（First ...
    99+
    2023-06-30
  • C语言怎么实现栈和队列
    本文小编为大家详细介绍“C语言怎么实现栈和队列”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言怎么实现栈和队列”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。什么是栈栈：一种特殊的线性表，其只允许在固定的一端...
    99+
    2023-06-30
  • C语言栈和队列如何实现
    这篇文章主要讲解了“C语言栈和队列如何实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C语言栈和队列如何实现”吧！一、栈与队列以及双端队列的概念1.1 栈的概念及结构栈：一种特殊的线性表，...
    99+
    2023-06-30
  • C语言中用栈+队列实现队列中的元素逆置
    下面举例代码： 提到的Q是一个队列,S是一个空栈,实现将队列中的元素逆置的算法 #include<stdio.h> #define MaxSize 10 typedef ...
    99+
    2022-11-13
  • C语言实现链队列基本操作
    队列的链式存储结构实现，相比于循环队列实现要复杂一些，但是没有队满的限制。 头文件声明 #include <stdio.h> #include <stdlib....
    99+
    2022-11-12
  • C语言超详细讲解队列的实现及代码
    目录前言队列的概念队列的结构队列的应用场景队列的实现创建队列结构队列初始化  队列销毁  入队列  出队列  队列判空  获取队列元...
    99+
    2022-11-13
  • C语言栈与队列面试题实例分析
    本文小编为大家详细介绍“C语言栈与队列面试题实例分析”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言栈与队列面试题实例分析”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。1、括号匹配问题链接直达：有效的括号题...
    99+
    2023-06-29
  • C语言用栈模拟实现队列问题详解
    目录题目描述题目链接思路分析代码实现题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。 你只能使用标准的栈操作...
    99+
    2022-11-13
  • C语言分别实现栈和队列详解流程
    目录什么是栈栈的结构图示栈的实现创建栈的结构体初始化栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空栈的销毁什么是队列？队列的实现创建队列结构体初始化队列队尾入队列队头出队列...
    99+
    2022-11-13
  • C语言实现顺序循环队列实例
    目录一、队列和循环队列基本概念二、代码实操总结一、队列和循环队列基本概念 队列: 和栈相反，队列是一种先进先出（FIFO）的线性表。只允许在一端插入，在另一端删除。 允许插入的叫&...
    99+
    2022-11-13
  • C语言超详细讲解栈与队列实现实例
    目录1.思考-12.栈基本操作的实现2.1 初始化栈2.2 入栈2.3 出栈2.4 获取栈顶数据2.5 获取栈中有效元素个数2.6 判断栈是否为空2.7 销毁栈3.测试3.1 测试3...
    99+
    2022-11-13
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作