当前位置:   article > 正文

队列详解(C语言实现)_c语言实现队列

c语言实现队列

写在前面

本片文章详细介绍了另外两种存储逻辑关系为 “一对一” 的数据结构——栈和队列中的队列,并使用C语言实现链队列。
队列C语言实现源码:队列源码
以队列在存储数据时具有特殊的顺序规则:
队列:使用队列存储数据,遵循 “先进先出” 的原则,即最先进队列的数据最先出队列。队列也可以分为顺序队列(基于数组实现)和链队列(基于链表实现)。
在这里插入图片描述

队列的实现方式分为顺序和链式结构,分别适用于不同的场景。顺序结构在内存中占据一块连续的空间,而链式结构通过节点之间的指针连接。这使得栈和队列在实际应用中更灵活,可以根据具体需求选择不同的实现方式。

1 队列的定义

链式队列的实现其实和之前单链表的实现很类似,只不过队列中数据的进出要遵循 “先进先出” 的原则。
链式队列节点的定义:

typedef int QDataType;

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

队列的定义通常包括两个指针和一个整型,一个指针front指向队列的头,一个指针tail指向队列的尾,还有一个整型size用来记录队列的数据个数。
下面是队列结构的定义:

typedef struct Queue
{
	QNode* front;//指向队列头部的指针
	QNode* tail;//指向队列尾部的指针
	int size;//记录队列中元素个数
}Queue;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2 队列的初始化

刚开始队列为空,头指针front和尾指针tail指向NULL,此时队列中元素个数为0,因此将size初始化为0。
代码如下:

void QueueInit(Queue* pq)
{
	assert(pq);//检查参数有效性

	pq->front = pq->tail = NULL;
	pq->size = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

3 数据入队列

数据入队列分为一下两种情况:

  1. 队列为空时,新建节点,并用要入队列的数据初始化节点,此时front 和 tail都指向新插入的节点,同时将size+1。
  2. 队列不为空时,新建节点,并用要入队列的数据初始化节点,此时tail->next指向新插入的节点,更新tail指向新插入的节点。

数据1 2 3 4 入队列图解:
在这里插入图片描述
代码如下:

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);//检查参数有效性
	//创建新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush->malloc");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	//入队列
	//1. 队列为空
	//2. 队列不为空
	if (pq->front == NULL)
	{
		assert(!pq->tail);// 队列为空时,tail front都为空
		pq->front = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

4 数据出队列

我们知道,队列只能在队尾一端入数据,出数据时只能出队头的数据。因为它要保证有数据元素需要出队时,按照 “先进先出” 的原则。
数据出队的步骤如下:

  1. 在执行数据出队列操作之前,需要检查队列是否为空。如果队列为空(即没有数据),则无法执行出队列操作。
  2. 如果队列不为空,即存在数据,就可以执行出队列操作。
    此时数据出队列又分为两种情况:
    • 队列中只有一个数据:
      此时只需要将该数据所在节点释放,并将 front 和 tail 置为NULL即可。
    • 队列中有两个及以上数据:
      保存头节点下一个节点的地址,释放头节点,更新front,使front指向新的队头元素。

数据1 2 3 4 出队列图解:
在这里插入图片描述

代码如下:

void QueuePop(Queue* pq)
{
	assert(pq);//检查参数有效性
	assert(!QueueEmpty(pq));//检查队列是否为空,为空不能pop

	//出队列
	//1. 队列只有1个元素
	//2.队列有2个以上元素
	if (pq->front->next == NULL)
	{
		free(pq->front);
		pq->front = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->front->next;
		free(pq->front);
		pq->front = next;
	}
	pq->size--;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

5 获取队头元素

获取队头元素的步骤如下:

  1. 在执行取队头元素操作之前,需要检查队列是否为空。如果队列为空(即没有数据),则无法执行此操作。
  2. 头指针front指向的就是队头元素,如要获取队头元素,因此只需返回front->val即可。

在这里插入图片描述代码如下:

QDataType QueueFront(Queue* pq)
{
	assert(pq);//检查参数有效性
	assert(!QueueEmpty(pq));//检查队列是否为空,为空不能取队头元素

	return pq->front->val;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

6 获取队尾元素

获取队尾元素的步骤如下:

  1. 在执行取队尾元素操作之前,需要检查队列是否为空。如果队列为空(即没有数据),则无法执行此操作。
  2. 尾指针tail指向的就是队头元素,如要获取队尾元素,因此只需返回tail->val即可。

在这里插入图片描述
代码如下:

QDataType QueueBack(Queue* pq)
{
	assert(pq);//检查参数有效性
	assert(!QueueEmpty(pq));//检查队列是否为空,为空不能取队尾元素

	return pq->tail->val;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

7 获取队列元素个数

队列中的size记录的就是队列中元素的个数,如要获取队列元素个数,返回size即可。
代码如下:

int QueueSize(Queue* pq)
{
	assert(pq);//检查参数有效性

	return pq->size;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

8 判断队列是否为空

根据队列初始化函数,我们知道,队列为空时,front 和 tail 都指向NULL。
此时size=0,也可以用size来判断,这里作者选择用front 和 tail 来进行判断。
在这里插入图片描述
代码如下:

bool QueueEmpty(Queue* pq)
{
	assert(pq);//检查参数有效性
	return pq->front == NULL && pq->tail == NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5

8 队列的销毁

链队列用来存储数据的节点都是动态申请的,因此队列销毁时,只需要遍历该链队列,依次释放每个节点。最后将 front 和 tail 置为NULL,size 置为0即可。
代码如下:

void QueueDestroy(Queue* pq)
{
	assert(pq);//检查参数有效性
	QNode* cur = pq->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->front = pq->tail = NULL;
	pq->size = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

至此,本片文章就结束了,若本篇内容对您有所帮助,请三连点赞,关注,收藏支持下。
创作不易,白嫖不好,各位的支持和认可,就是我创作的最大动力,我们下篇文章见!
如果本篇博客有任何错误,请批评指教,不胜感激 !!!
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/811801
推荐阅读
相关标签
  

闽ICP备14008679号