队列的顺序存储结构之循环队列

大家好，又见面了，我是你们的朋友全栈君。

一、队列的定义 队列( queue )是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。如图所示：

在这里插入图片描述

二、循环队列的引出 为了避免当队中只剩一个元素的时候，队头队尾重合使处理变得麻烦。所以我们引入两个指针，front指针指向队头元素，rear指针指向队尾元素。这样当front=rear时，队列中不是只剩一个元素，而是它是一个空队列。而且这样也大大方便了我们删除队头元素。这样就当我们删除队头元素时就只需要移动front指针，这样可以大大降低算法的时间复杂度。 但是当删除元素的时候，front不断后移，前面的位置不断空出来。插入元素时rear指针 b不断后移。对于一个有限的队列来说，在不断得插入元素时rear最终会指向一个无效位置。具体情况如下图所示： 删除元素时：

在这里插入图片描述

插入元素时：

在这里插入图片描述

用循环队列可以巧妙得解决这个问题。 三、循环队列 1、循环队列的定义 **我们把队列的这种头尾相接的顺序存储结构称为循环队列。**如下图所示： 循环队列满时：

在这里插入图片描述

循环队列空时：

在这里插入图片描述

判断循环队列空的条件是：

front == rear;

判断循环队列满的条件是：

(rear+1)%6==front

为了区别判空和判满的状态，我们总在插入元素时牺牲一个空间来区别这两种状态，这也是为啥判满的时候是(rear+1)%6==front 2、循环队列的简单实现 （1）循环队列的整体结构的设计

typedef int ElemType;
#define MAX_SIZE 10
typedef structc Queue
{ 
   
	ElemType arr[MAX_SIZE];
	int front;//队头指针
	int rear;//队尾指针
};Queue,pQueue

2、初始化(init) 初始化的时候我们只需要将我们的头指针和尾指针置成0即可。

void init(pQueue pqu)
{ 
   
	if(pqu != NULL)
	{ 
   
	pqu->front = pqu->rear = 0;
	}
} 

3、入队操作(enqueue) 在进行入队操作之前我们首先应该对队列进行判满的操作。如果队列是满的，我们就插入不了元素。如果队列不满我们就可以进行我们的入队操作。 判满

int full(pQueue pqu)
{ 
   
	return (pqu->rear + 1)%MAX_SIZE == front ? 1 : 0;
}

插入元素 插入元素时，我们只需要将这个队列中的rear指针的下标置成我们要插入的元素即可。

int enqueue(pQueue pqu,ElemType val)
{ 
   
	if(full(pqu))
	{ 
   
	return 0;
	}
	pqu->arr[pqu->rear] = val;
	pqu->rear = (pqu->rear + 1)%MAX_SIZE;
	return 1;
}

4、出队操作(dequeue) 在进行出队操作时，我们首先要判断的是队列是否为空。若队列中的元素为空，则就无法进行出队的操作。 判空

int empty(pQueue pqu)
{ 
   
	return (pqu->rear == pqu->front) ? 1 : 0;
}

出队操作

int dequeue(Pqueue pqu)//只是删除元素
{ 
   
	if(empty(pqu))
	{ 
   
	return 0;
	}
	pqu->front = (pqu->front + 1) % MAX_SIZE;
	return 1;
}

5、获取队头元素(front)

int front(pQueue pqu)
{ 
   
	if(empty(pqu))
	{ 
   
	return -1;//牺牲一个数值位
	}
	return pqu->arr[pqu->front];
}

6、获取队尾元素(back)

int back(pQueue pqu)
{ 
   
	if(empty(pqu))
	{ 
   
	return -1;//队列为NULL
	}
	return pqu->arr[(pqu->rear + MAX_SIZE - 1)%MAX_SIZE];
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/143020.html原文链接：https://javaforall.cn