投稿
  1. 首页
  2. C

数据结构--队列--顺序循环队列的 *** 作实现（C语言）

code•2022-4-19•C•阅读42

数据结构--队列--顺序循环队列的 *** 作实现（C语言）,第1张

文章目录
  • 🎄队列是个什么样的数据结构？
  • 🎄循环队列
  • 🎄顺序循环队列的实现
    • ⭐1.创建初始化队列
    • ⭐2.入队
    • ⭐3.出队
    • ⭐4.队列遍历打印
    • ⭐5.清空队列
    • ⭐6.判断队列空
    • ⭐7.判断队列满
    • ⭐8.动态内存释放
  • 🎄总结

本文中涉及的完整代码及各 *** 作测试代码均已提交至Gitee，大家可以点击链接参考。


鄙人乃是一介初学者，文中及代码中难免出错，请同志们批评指正！

🎄队列是个什么样的数据结构？

我们前面介绍过栈，栈乃是一个只有一个口的直筒子。

那么队列，其实是一个两端开口的直筒子。


其实这里的队列就基本相当于我们生活中的队列。

举例一个场景：我们最近经常要做核酸排长队，队伍从队头做完核酸退出队列，新来的人从队尾加入队列。

这也是数据结构中队列的数据插入、删除的 *** 作。

我们来给队列下一个定义：

队列( queue )是只允许在一端进行插入 *** 作，而在另一端进行删除 *** 作的线性表。

队列是一种先进先出(First In First Out)的线性表，简称FIFO。

允许插入的一-端称为队尾，允许删除的一端称为队头。

假设队列是q= ( a1, a2, … an),那么a1就是队头元素，而an是队尾元素。

这样我们就可以删除时，总是从a1开始，而插入时，列在最后。

这也比较符合我们通常生活中的习惯，排在第一一个的优先出列， 最后来的当然排在队伍最后。



🎄循环队列

在介绍循环队列之前，我们先来考虑最普通最容易想到的队列的实现流程。


1.入队：
我们假定有一个数组，这个数组可以放5个元素，其下标从0到4，其中下标为0的地方我们称之为队头。

如果要往里面放入元素，就从队尾开始追加。

队尾的位置是当前最后一个元素所在位置。

如下图。



2.出队：
如果要出队列，因为只允许从队头开始删除元素，所以下标为0的元素被删除。

为了能让队头不空，后面的元素需要向前移动，这和顺序表的表头删除 *** 作一模一样，其时间复杂度为O(n)。



3.改善
上面 *** 作因为需要把元素整体移动，如果元素较多，这种移动无疑会耗费大量的时间，影响性能。

那能不能不移动元素，而是移动队头呢？当下表为0的元素删除后，队头从下标为0的位置移动到下标为1的位置。

这样使得队列的性能大大提高。

因为其时间复杂度变为O(1)了。



4.问题
为了表示队头、队尾的位置，我们在程序中设定两个变量：front、rear。

规定front指向队头元素的位置；rear指向队尾元素的下一个位置。



如上图中左图，当队列为空时，front和rear指向同一个位置，那么在编程时，当front==rear时，我们可以判定队列为空队列。

向空队列中继续放入元素，直到rear指向数组最后一个空位。


此时我们进行出队 *** 作，但是只移动队头，即front的位置，当我们删除两个元素后，front指向了下标为2的位置，如下图左图：

但是，如果我们继续向队列中放入元素，那么依旧是从队尾进行插入，然而，当我们放入一个元素后，队尾指针rear竟然指向了数组之外，这就造成了数组越界的问题。

可能你会想，既然如此，我们就规定rear的位置指向下标为4的位置的时候判定队列为满，不允许继续插入就好了。

但是，rear指针告诉我们队列已满，实际上我们队列的前面两个地方还空着呢，队列并没有满，这不是造成了很大的空间浪费吗？实际上，这种情况被称为“假溢出”。

那么为了解决这样的问题，需要同时考虑到时间复杂度和数组越界，该如何解决呢？

5.问题的解决：循环队列
那么解决上面的问题，我们可以这样想：既然后面满了，而前面还空着，为什么不让新增的元素从头开始存储呢？这样，整个本来是直筒子的队列形成了一个头尾相接的圆环。

我们把队列的这种头尾相接的顺序存储结构称为循环队列。


入上图，当想要放入a5 元素时，我们将其放入到队列中的最后一个空位中，但是队尾指针指向了最最开始的队头，也就是下标为0的位置。

这样数组访问有址可循，不会出现数组越界访问的问题。

接下来，我们继续向里面放入元素：

可以看到，当我们放入a7时，队尾rear追上了队头front。

因为我们之前说判断队列为空的条件是：rear == front，那这种情况下，也会将已经满了的队列判断为空队列，继续往里面放元素，那不是把之前的数据都给覆盖了吗？这可乱了套了！

基于这种问题的出现，设计数据结构的老前辈想出了这样一个点子：既然如此，我干脆舍弃一个空间，当队列中还剩一个空闲位置时就判断队列已满吧，如图1：

也就是说，当整个队列只剩下这一个空闲空间的时候，就判断队列已满。


6.新的问题和解决：
虽然这种循环队列的判满方式在逻辑上解决了队列满没满的问题，但是我们还是会比较纠结于如何去判断队列中只剩一个空闲位置。


对于图1中的队列满了的情况，我们可以使用front-rear == 1这个判断条件，但如果是下面图2这种情况呢？

因为front比rear小，而且相减之后的绝对值也相差蛮多，所以无法使用front-rear == 1这个判断条件。


这时考虑使用这样的一个条件：假定队列最大元素个数为maxSize，判满条件为：(rear + 1) % maxSize == front。


对于图1：rear=1 front=2，而(1+1)%5== 2 == front。


对于图2：rear=4 front=0，而(4+1)%5== 0== front。


两者都被判断为满。


总结一下，队列判空和判满的条件分别是：
队列为空：rear == front
队列为满：(rear + 1) % maxSize == front

有了上面的分析，下面让我们来具体实现一个顺序存储结构的循环队列吧！

🎄顺序循环队列的实现

首先我们来想想怎么样用C语言构建一个循环队列模型。


第一，我们要有存储数据的变量，这和顺序结构中一样，可以是一个指针来方便我们动态开辟内存。

其中这个数据变量的类型应该是可改的，所以我们依旧使用typedef来给某个变量类型取个名字，方便以后程序的修改；
第二，我们要有队头和队尾的指针，这里考虑用两个int类型变量来方便我们指向队头队尾，front、rear
第三，需要一个变量来确定我们整个队列的大小，maxsize。


模型构建如下：

typedef int data_t;

typedef struct sequeue
{
	data_t* data;//存放数据
	int front;//队头
	int rear;//队尾
	int maxsize;//队列最大元素个数
}sequeue, * ptrsq;

创建好队列的模型后，我们需要实现以下几个基本 *** 作：

  1. 创建初始化队列 ；
  2. 入队；
  3. 出队；
  4. 队列遍历打印；
  5. 清空队列 ；
  6. 判断队列空；
  7. 判断队列满；
  8. 动态内存释放；

⭐1.创建初始化队列

因为这里我们用的是一个指针而非固定大小的数组来表示数据，所以应该在初始化时malloc两次空间，一个用来管理维护结构体，另一个用来管理维护队列中的数据data。

为了能让用户根据自己的需要创建队列的大小，我们由用户来指定数据的个数。

比如用户在调用这个初始化函数时传入参数100，在该函数内部将需要实现开辟一块能存下100个data_t类型数据大小的空间，应为我们这里判满的特殊规则，实际上这块空间能存下99个data_t类型的数据。

当空间开辟成功，需要对队列的队头、队尾以及大小进行初始化。


函数的返回值应该返回创建好的队列指针。

请看代码：

//1. 创建队列 
/***
****@return      sq:队列指针
****@para        size:用户指定的队列最大容量 
***/
ptrsq queue_init(int size)
{
	//给结构体申请空间
	ptrsq sq = (ptrsq)malloc(sizeof(sequeue));
	if (sq == NULL)
	{
		perror("queue_init: malloc failed");
		return NULL;
	}

	//给数据申请空间：
	sq->data = (data_t*)malloc(size * sizeof(data_t));
	if (sq->data == NULL)
	{
		perror("queue_init: data malloc failed");
		free(sq);
		sq = NULL;
		return NULL;
	}
	//初始化
	memset(sq->data, 0, size * sizeof(data_t));
	sq->front = sq->rear = 0;
	sq->maxsize = size;
	return sq;
}

main函数中这样使用：
ptrsq sequeue = queue_init(5);//初始化的队列sequeue最多可以存放4个data_t类型数据

⭐2.入队

入队，实际上就是将数据存入到队尾指针所指的那块空间去，也就是data[rear]，当存储结束后，队尾要向后移一位，但是这里不能简单的rear++，为什么呢？下面我们举例说明，我们举例这个队列最大容量为6，下标就是从0-5：
因为我们的队列是一个循环结构，rear指向最后一位下标为5的位置时，将数据存入到data[5]中，如果简单的rear++，那么real将指向data[6]，但是，data[6]是一个未知空间，这显然不行。

而我们前面也分析过，既然这是一个循环队列，那么rear应该从5变到0，重新从头开始。

如何实现呢？
这里我们可以用一个if-else语句来判断rear是不是走到了最后一个位置，如果走到了最后一个位置rear == maxsize-1就让rear = 0。

如果没有，就正常rear++。


但是我们之前分析了一个取余的办法，其实这里可以用取余来实现，也就是让rear = (rear + 1) % maxsize。

使用这个公式，如果rear == 5，那么下一个rear = (5+1)%6 = 0。

这是一个很巧妙的方法。

注意，在执行上面 *** 作前，应该先判断队列存不存在、队列满了没满。

下面来看代码：

//2. 入队
/***
**** @return      0:success     -1:failed
**** @para        sq:队列指针    val:data_t类型数据
***/
int enqueue(ptrsq sq , data_t val)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return -1;
	}
	//再判断队列满没满
	if ((sq->rear + 1) % sq->maxsize == sq->front)
	{
		printf("\nqueue is full\n");
		return -1;
	}
	//开始从队尾进入队列
	sq->data[sq->rear] = val;//先给队尾当前所在位置放上元素
	
	//注意判断队尾走到最后了没，如果走到最后，应该让队尾从头再来
	//如果没有走到最后，就正常加一位
	//这里的实现不能用简单的rear++，可以使用取余的思想：
	sq->rear = (sq->rear + 1) % sq->maxsize;

	return 0;
}

⭐3.出队

出队就是让队头指针向后循环一位。

为了让用户知道删除的是哪一个元素，让这个函数返回删除的元素。


注意，因为我们是循环队列，所以和入队时rear面对的问题一样，front也面临着一个走到最后如何从头再来的问题，那么处理方法和rear的处理方法一模一样，也可以用取余的思想。

注意：在执行上述 *** 作之前，也要先判断队列存不存在、队列空不空。

请看代码：

//3. 出队
/***
**** @return      data_t tmp:出队的数据     -1:failed
**** @para        sq:队列指针  
***/
data_t dequeue(ptrsq sq)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return -1;
	}

	//再判断队列空不空
	if (sq->front == sq->rear)
	{
		printf("\nqueue is empty\n");
		return -1;
	}

	//从队头删除一个元素
	//删除前先记录一下：
	data_t tmp = sq->data[sq->front];
	
	//注意判断队头走到最后了没，如果走到最后，应该让队头从0再来
	//如果没有走到最后，就正常加一位
	//这里的实现不能用简单的front++，可以使用取余的思想：
	sq->front = (sq->front + 1) % sq->maxsize;

	return tmp;
}

⭐4.队列遍历打印

同样，先判断队列存不存在、队列空不空。

如果不空，那么开始循环遍历队列中的元素并打印。


但是，我们依旧是那个问题，如何循环这个循环队列？其实解决思路和上面一样，我们让这个用来遍历的变量i也取余i = (i + 1) % maxsize，也就实现了循环遍历。

那么i从哪儿开始，从哪儿停下来呢？我们说应该从队头front开始，到队尾rear结束。


请看代码：

//4. 队列遍历打印
/***
**** @return      0:success     -1:failed
**** @para        sq:队列指针    val:data_t类型数据
***/
int queue_show(ptrsq sq)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return -1;
	}

	//再判断队列空不空
	if (sq->front == sq->rear)
	{
		printf("\nqueue is empty\n");
		return -1;
	}

	//开始遍历：
	printf("\ndata in queue:");
	int i = sq->front;
	while ( i != sq->rear )
	{
		printf("%d ", sq->data[i]);
		i = (i + 1) % sq->maxsize;
	}

	return 0;
}

⭐5.清空队列

简单，直接让队头=队尾=0。

和初始化中做的一样，而且这里还不需要使用memset函数把队列中每个字节置0。

//5. 清空队列 
int queue_clear(ptrsq sq)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return -1;
	}
	sq->front = sq->rear = 0;
	return 0;
}

⭐6.判断队列空

我们在前面分析的时候就说过判断循环队列的空和满的条件
队列为空：rear == front
队列为满：(rear + 1) % maxSize == front
那么按照这个就可以直接判断，为了简洁，这里可以使用三目运算符：

//6. 判断队列空
/***
**** @return      1:not empty      0:empty      -1:failed
**** @para        sq:队列指针 
***/
int queue_empty(ptrsq sq)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return -1;
	}
	return (sq->front == sq->rear) ? 0 : 1;
}

⭐7.判断队列满

队列为空：rear == front
队列为满：(rear + 1) % maxSize == front

//7. 判断队列满
/***
**** @return      1:full      0:not full      -1:failed
**** @para        sq:队列指针   
***/
int queue_full(ptrsq sq)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return -1;
	}
	return (sq->front == (sq->rear + 1) % sq->maxsize) ? 1 : 0;
}

⭐8.动态内存释放

记住，有几个malloc就有几个free，而且是：先malloc的后free！

//8.动态内存释放
ptrsq queue_free(ptrsq sq)
{
	//先判断队列存不存在
	if (sq == NULL)
	{
		printf("\nqueue is not exist\n");
		return NULL;
	}
	free(sq->data);
	sq->data = NULL;
	free(sq);
	sq = NULL;
	return NULL;
}

🎄总结

为了解决顺序存储结构中队列实现时时间复杂度的问题，我们采用了循环队列并实现了其基本的入队、出队等 *** 作。

那么和栈一样，队列作为一个逻辑为线性结构的数据结构，除了使用顺序存储实现，还可以使用链式存储实现，那么下一篇就来记录链式队列的实现过程。

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/673439.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
codecode管理员组
00
上一篇 2022-04-19
下一篇2022-04-19

发表评论

登录后才能评论

评论列表（0条）

    保存