首页 > 电脑常识 > 云计算

【数据结构从青铜到王者】第四篇:数据结构之队列

admin 云计算 2021-04-27 10:13:48 队列   数据结构  
后台-系统设置-扩展变量-手机广告位-内容正文底部

在这里插入图片描述

系列文章目录


文章目录

  • 系列文章目录
  • 前言
  • 一、队列的概念及结构
      • 1.队列的概念
      • 2.队列的结构
  • 二、队列的实现
      • 1.定义用链表表示的队列struct QueueNode
      • 2.定义队列的队头、队尾指针struct Queue
      • 3.队列的初始化函数QueueInit
      • 4.队列的销毁函数QueueDestroy
      • 5.队列的队尾入数据函数QueuePush
      • 6.队列的队头出数据函数QueuePop
      • 7.队列的取出队头数据函数QueueFront
      • 8.队列的取出队尾数据函数QueueBack
      • 9.队列是否为空函数QueueEmpty
      • 10.队列的长度函数QueueSize
  • 总结


前言


在这里插入图片描述

一、队列的概念及结构

1.队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。

2.队列的结构

在这里插入图片描述

二、队列的实现

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

在这里插入图片描述

1.定义用链表表示的队列struct QueueNode

代码如下:

typedef int QDataType;
struct QueueNode             //队列结构,用链表来表示
{
	struct QueueNode* next;
	QDataType data;
};

2.定义队列的队头、队尾指针struct Queue

代码如下:

struct Queue                //队列头尾指针
{
	struct QueueNode* head;
	struct QueueNode* tail;
};

3.队列的初始化函数QueueInit

代码如下:

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

4.队列的销毁函数QueueDestroy

遍历队列,记住free前先存储下一个节点的地址。
代码如下:

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

5.队列的队尾入数据函数QueuePush

先开辟一个结点,在分两种情况,一种情况队列一个节点都没有,那可以直接当节点,第二种情况队列一开始有节点,尾插数据即可。
代码如下:

void QueuePush(struct Queue* pq, QDataType x)   //队尾入数据
{
	assert(pq);
	struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
	if (newnode == NULL)
	{
		printf("开辟失败!\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)   //无节点
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

6.队列的队头出数据函数QueuePop

代码如下:

void QueuePop(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next==NULL)  //只有一个节点
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		struct QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

7.队列的取出队头数据函数QueueFront

记住每次取数据前判断队列是否为空,不为空才进行下一步。
代码如下:

QDataType QueueFront(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

8.队列的取出队尾数据函数QueueBack

记住每次取数据前判断队列是否为空,不为空才进行下一步。
代码如下:

QDataType QueueBack(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

9.队列是否为空函数QueueEmpty

代码如下:

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

10.队列的长度函数QueueSize

代码如下:

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

总结

以上就是今天要讲的内容,本文仅仅简单介绍了队列的使用,对于队列提供了一些简便方法帮助我们解题,能使我们快速便捷地处理数据的函数和方法。另外这个结构虽然相比链表更简单,使用代码实现起来更容易写,但我们也要认真学习,以后会发现队列结构会带来很多优势,我们务必掌握。另外,如果有需要源码的私信我即可。还有,如果上述有任何问题,请懂哥指教,不过没关系,主要是自己能坚持,更希望有一起学习的同学可以帮我指正,但是如果可以请温柔一点跟我讲,爱与和平是永远的主题,爱各位了。
在这里插入图片描述

文章来源:https://blog.csdn.net/qq_44918090/article/details/116137889

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://jcdi.cn/diannaochangshi/yunjisuan/923.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码