顺序存储队列 不循环队列和循环队列

2022-08-22 13:17:56

队列的特点:先进先出

视频链接地址:https://www.bilibili.com/video/BV18p4y167Md?p=99.

顺序存储的不循环队列

我们使用两个标记来记录数组下标的位置,以方便入队和出队。

这两个标记呢,可以使用指针变量,也可以使用数组的下标(int类型的变量),我们通常称之为队头指针(head 或 front)和队尾指针(rear 或tail)。

(下图中的队头指针和队尾指针都是指向下标为0的数组区域。)
在这里插入图片描述
我们可以使用队头指针来入队也可以使用队尾指针来入队,但是当队头指针来入队之后,队尾指针就只能负责出队了,反过来也是一样。

下面,来介绍一下不循环队列的实现。
在这里插入图片描述
一开始,让入队指针和出队指针都是指向下标为0的数组区域,然后移动入队指针来完成入队操作。不出队,当入队指针指向数组最后一个区域外时候,就说明队列满了。

还有一种方法,我们可以让入队指针和出队指针的值都为-1,当每次入队之后,都让入队指针的值加1。不出队,当入队指针的值为最后一个数组下标值的时候,也就说明队列满了。
在这里插入图片描述
我们会发现,不循环队列中的空间只会使用一次。作用并不是很大,因此,我们将重点研究循环队列。

顺序存储的循环队列

来看下循环队列又是怎样实现的呢?

我么先采用下面这种方式来入队和出队。

一开始,让入队指针和出队指针都指向数组下标为0的地方。入队时数据先入队,再移动入队指针。出队时,数据先出队,再移动出队指针。(这种入队出队方式是有问题的。)

这里演示下入队和出队。

我们让tail为入队指针,head为出队指针。一开始都指向数组下标为0的地方。

入队演示如下:
在这里插入图片描述
出队演示如下:
在这里插入图片描述
入队时,若入队指针已经指向最后一个区域时,入队指针重新指向0的位置。出队也是一样。

下面总结下这种方式入队和出队之后,判断队列为空的条件在这里插入图片描述
但这样就会产生这样一个问题,如下图。
在这里插入图片描述
我们说,当head == tail时,队列为空,上述就是head == tail的一种情况,但队列此时是满的,也就是说采用上面这种入队和出队方式,分辨不出来队空和队满的情况。

为了避免这种情况,我们进行了改进。我们人为的规定,我们让出队指针指向的区域始终不存储数据。

改进后的出入队方式如下:

同样,我们让tail为入队指针,head为出队指针。一开始都指向数组下标为0的地方。

但指针移动顺序有变化,依然是,入队时数据先入队,再移动入队指针。但出队时变了,变成了先移动出队指针,数据再出队。

入队:
在这里插入图片描述
出队:
在这里插入图片描述
总结下
在这里插入图片描述
那此时再来判断队列为满的条件会不会和队列为空的条件,产生冲突呢?

假设,当前处于这种情况,队列满了,此时入队指针和出队指针并没有指向同一个位置。与队列空的条件并不冲突。
在这里插入图片描述
入队指针是tail,为4,出队指针是head,为0,数组长度为5,计算一下
(4+1)%5 == 0,所以队列满了。

还有这种情况也表示队列为满的情况。
在这里插入图片描述
此时入队指针和出队指针并没有指向同一个位置。所以与队列空的条件也并不冲突。

入队指针是tail,为1,出队指针是head,为2,数组长度为5,计算一下
(1+1)%5 == 2,所以队列满了。

这两种队满能用一个规律来总结吗。
我们可以用下面判断条件来判断是否队满。
(入队指针 + 1)% (数组长度) == 出队指针
等于代表满,不等于代表没有满。

当队列满了之后,就不能再入队了。只有出队之后,让出空间,才能继续入队。也就是说一次性最多只能存储数组长度减一个数。

下面,我们来编写代码。
queue.h

#ifndef _QUEUE_H_
#define _QUEUE_H_/* 顺序队列数据结构 *//* head所指向的那块空间是永远不能存有效数据的 */

#defineBUFFER_SIZE5 

typedef struct{
	int head;//队首
	int tail;//队尾
	int data[BUFFER_SIZE];//数组的首地址,模拟队列}queue_t;//创建队列voidqu_Create(queue_t** queue);//队列是否为空
intqu_IsEmpty(queue_t* queue);//入队
intqu_Enter(queue_t* queue,int data);//出队
intqu_Departure(queue_t* queue);//遍历队列voidqu_Traverse(queue_t* queue);//清空队列voidqu_Clear(queue_t* queue);//销毁队列voidqu_Destroy(queue_t* queue);

#endif// !_QUEUE_H_
#pragma once

queue.c

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

#include"queue.h"//创建队列voidqu_Create(queue_t** queue){if(queue==NULL){return;}
	queue_t* tmp=(queue_t*)malloc(sizeof(queue_t));if(tmp==NULL){returnNULL;}

	tmp->head=0;
	tmp->tail=0;*queue= tmp;return0;}//队列是否为空
intqu_IsEmpty(queue_t* queue){return(queue->tail== queue->head);}//入队
intqu_Enter(queue_t* queue, int data){//成立,说明满了if(((queue->tail+1)%BUFFER_SIZE)== queue->head)return-1;

	queue->tail=(queue->tail+1)%BUFFER_SIZE;
	queue->data[queue->tail]= data;return0;}//出队
intqu_Departure(queue_t* queue){
	int data;if(qu_IsEmpty(queue))return-1;

	queue->head=(queue->head+1)%BUFFER_SIZE;//出队的值为data
	data= queue->data[queue->head];return data;}//遍历队列voidqu_Traverse(queue_t* queue){
	int i;//队列为空if(queue->head== queue->tail)return;

	i=(queue->head+1)%BUFFER_SIZE;//queue->tail不会输出while(i!= queue->tail){printf("%d ", queue->data[i]);
		i=(i+1)%BUFFER_SIZE;}//queue->tail不会输出printf("%d\n", queue->data[i]);}//清空队列voidqu_Clear(queue_t* queue){
	queue->head== queue->tail;}//销毁队列voidqu_Destroy(queue_t* queue){//再释放buf所指向的堆内存if(queue!=NULL){free(queue);
		queue=NULL;}}

main.c

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

#include"queue.h"

intmain(){
	int i;
	int data;
	queue_t* queue=NULL;

	int arr[]={2,3,6,8};qu_Create(&queue);if(queue==NULL){return-1;}for( i=0; i<sizeof(arr)/sizeof(*arr); i++){qu_Enter(queue, arr[i]);}

	data=qu_Departure(queue);printf("data = %d .\n",data);

	data=qu_Departure(queue);printf("data = %d .\n", data);qu_Enter(queue,10);

	data=qu_Departure(queue);printf("data = %d .\n", data);qu_Enter(queue,15);qu_Enter(queue,20);qu_Enter(queue,21);

	data=qu_Departure(queue);printf("data = %d .\n", data);qu_Enter(queue,25);

	data=qu_Departure(queue);printf("data = %d .\n", data);qu_Enter(queue,30);qu_Traverse(queue);qu_Destroy(queue);

	queue=NULL;system("pause");return0;}

程序运行结果如下:
在这里插入图片描述

这个程序需要注意,数组遍历的顺序。
在这里插入图片描述

  • 作者:xuechanba
  • 原文链接:https://blog.csdn.net/xuechanba/article/details/120308233
    更新时间:2022-08-22 13:17:56