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

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

一、队列的定义
队列( 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];
}