循环队列

定义

概念

为了解决顺序队列“假溢出”的缺陷，所以引入了循环队列。

关于顺序队列请参考：顺序队列。

循环队列就是将顺序队列臆造成一个环状的空间（实际上不是，只是把它看成是环状的），即把存储队列元素的顺序表从逻辑上视为一个环。当队头指针 queue.front==MAXSIZE-1 时（即到数组的最后一个位置了），再前进一个位置就自动到 0，这可以利用除法取余运算（%）来实现。

通常采用数组来实现，当然也可以通过链表来实现循环队列。

关于循环队列的状态和操作如下：

• 初始化：queue.front=0; queue.rear=0;。

• 入队操作：先将新元素赋予队尾指针所指向的位置，然后队尾指针加一。但循环队列中加一操作与顺序队列有所不同：queue.rear=(queue.rear+1)%MAXSIZE。是为了当达到 MAXSIZE-1 位置后下一个位置自动到 0 去。
• 出队操作：取出队头指针所指向的位置的元素，然后队头指针加一。但循环队列中加一操作与顺序队列有所不同：queue.front=(queue.front+1)%MAXSIZE。
• 队列长度：也跟顺序队列求队列长度有所不同，是：(queue.rear-queue.front+MAXSIZE)%MAXSIZE。

循环队列最大的问题就是如何判断队空和队满。之前顺序队列判断队空的条件 queue.front==queue.rear 是无法判断循环队列是队空还是队满的，因为循环队列队空和队满时 queue.front==queue.rear 条件都成立。如图：

为什么循环队列队满时，队头指针 front 和队尾指针 rear 会重合呢？如图所示，因为队头指针始终指向队头元素，而队尾指针指向队尾元素的下一个位置，所以当队满时，它们会重合。所以 queue.front==queue.rear 是无法作为单独判断队空和队满条件。

因此，为了区分是队空还是队满的清空，有三种处理方式：

• 第一种，牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种比较普通的做法，本篇也是采用的这种做法。约定以队头指针在队尾指针的下一位置作为队满的标志。如图所示：
  • 队满条件：(queue.rear+1)%MAXSIZE==queue.front。
  • 队空条件：queue.front==queue.rear。
  • 队列种的元素个数：(queue.rear-queue.front+MAXSIZE)%MAXSIZE。

• 结构体类型中增设表示元素个数的数据成员 size。这两种情况都有 queue.front==queue.rear，但不再作为判空或判满的条件。

  • 队满条件：queue.size==MAXSIZE。
  • 队空条件：queue.size==0。

• 结构体类型中增设 tag 数据成员，用来区分是队满还是队空。约定 tag 等于 0 时，若因删除导致 queue.front==queue.rear 则为队空；当 tag 等于 1 时，若因插入导致 queue.front==queue.rear 则为队满。有一道练习题就是实现该队列：Example004-设计一个循环队列，用 front 和 rear 分别作为队头和队尾指针，另外用一个标志 tag 表示队列是空还是不空。

  • 队满条件：queue.tag==1 && queue.front==queue.rear。
  • 队空条件：queue.tag==0 && queue.front==queue.rear。

结构体

/**
 * 循环队列结构体定义
 */
typedef struct {
    /**
     * 数据域，存储循环队列中的数据
     */
    int data[MAXSIZE];
    /**
     * 指针域，存储循环队列中队头元素的位置
     */
    int front;
    /**
     * 指针域，存储循环队列中队尾元素的位置
     */
    int rear;
} CircularQueue;

特点

• front 表示队头指针，实际上就是数组下标，指向顺序队列的队头元素；rear 表示队尾指针，指向顺序队列的队尾元素的下一个位置。
• 如果队尾指针 rear 到达 MAXSIZE-1 位置，则会自动跳到 0 位置。
• 循环队列能充分利用队列中的空余空间，直到队列中所有空间（除了用来判断队空或队满的一个空间）都被使用。

基本操作

注，完整代码请参考：

• CircularQueue.c
• CircularQueue.java
• CircularQueueTest.java

概述

循环队列的常见操作如下：

• void init(CircularQueue *queue)：初始化循环队列。其中 queue 表示循环队列。
• int isEmpty(CircularQueue queue)：判断循环队列是否为空。其中 queue 表示循环队列。如果循环队列为空则返回 1，否则返回 0。
• int isFull(CircularQueue queue)：判断循环队列是否已满。其中 queue 表示循环队列。如果循环队列已满则返回 1，否则返回 0。
• int enQueue(CircularQueue *queue, int ele)：将元素入队。其中 queue 表示循环队列；ele 表示待入队的元素。如果循环队列已满则不能入队，返回 0 表示入队失败；否则如果入队成功则返回 1。
• int deQueue(CircularQueue *queue, int *ele)：将元素出队。其中 queue 表示循环队列；ele 用来保存出队的元素。如果循环队列为空则不能出队，返回 0 表示出队失败；否则如果出队成功则返回 1。
• int size(CircularQueue queue) ：获取循环队列中的元素个数。其中 queue 表示循环队列。返回循环队列中的元素个数。
• int getFront(CircularQueue queue, int *ele)：读取循环队列中的队头元素。其中 queue 表示循环队列；ele 用来保存队头的元素。如果队列为空则无法获取队头元素则返回 0，否则返回 1。
• int getRear(CircularQueue queue, int *ele)：读取循环队列中的队尾元素。其中 queue 表示循环队列；ele 用来保存队尾的元素。如果队列为空则无法获取队尾元素则返回 0，否则返回 1。
• void clear(CircularQueue *queue)：清空循环队列中所有元素。其中 queue 表示循环队列。
• void print(CircularQueue queue)：打印循环队列中所有元素。其中 queue 表示循环队列。

init

初始化循环队列。

实现步骤：

• 将队头指针 front 和队尾指针 rear 都指向 0，表示空队列。

实现代码如下：

/**
 * 初始化循环队列
 * @param queue 待初始化的循环队列
 */
void init(CircularQueue *queue) {
    // 循环队列初始时，队头指针和队尾指针仍然都指向 0，表示是空队列
    queue->front = 0;
    queue->rear = 0;
}

isEmpty

判断循环队列是否为空。如果为空则返回 1，否则返回 0 表示非空。

实现步骤：

• 判断队头指针 front 和队尾指针 rear 是否指向同一位置，即 queue.front==queue.rear。

实现代码如下：

/**
 * 判断循环队列是否为空
 * @param queue 循环队列
 * @return 如果循环队列为空则返回 1，否则返回 0 表示非空
 */
int isEmpty(CircularQueue queue) {
    // 只要队头指针和队尾指针相等，那么表示循环队列为空，无论指针在哪个位置
    if (queue.rear == queue.front) {
        return 1;
    } else {
        return 0;
    }
}

isFull

判断循环队列是否已经满队。如果已满则返回 1，否则返回 0 表示未满。

实现步骤：

• 如果满足条件 (queue.rear+1)%MAXSIZE==queue.front，那么就认为队满。

实现代码如下：

/**
 * 判断循环队列是否已满
 * @param queue 循环队列
 * @return 如果循环队列已满则返回 1，否则返回 0 表示队列非满
 */
int isFull(CircularQueue queue) {
    // 队尾指针再加上一，然后对 MAXSIZE 取余，如果等于队头指针，那么表示队满
    if ((queue.rear + 1) % MAXSIZE == queue.front) {
        return 1;
    } else {
        return 0;
    }
}

enQueue

将元素入队。如果队未满才能入队，否则返回 0 表示入队失败。如果入队成功则返回 1。以 queue=[a, b, c]; ele=x 为例如图：

实现步骤：

• 参数校验，如果队满则不能入队。返回 0 表示入队失败。
• 先进行赋值，将队尾指针所指向的位置赋予 ele 值。
• 接着队尾指针加一，指向队尾元素的下一个位置。保证队尾指针始终指向队尾元素的下一位置。
• 返回 1 表示入队成功。

实现代码如下：

/**
 * 将元素入队
 * @param queue 循环队列
 * @param ele 指定元素
 * @return 如果队列已满则不能入队返回 0 表示入队失败；否则返回 1 表示入队成功
 */
int enQueue(CircularQueue *queue, int ele) {
    // 0.参数校验，如果队满则不能入队
    if ((queue->rear + 1) % MAXSIZE == queue->front) {
        return 0;
    }
    // 1.将元素入队
    // 1.1 先进行赋值，即将新元素填充到队尾指针指向的位置。因为队尾指针指向队尾元素的下一个位置
    queue->data[queue->rear] = ele;
    // 1.2 然后将队尾指针加一。因为是循环队列，如果到了队尾，那么又要从 0 开始，所以加一后需要对 MAXSIZE 进行取余
    queue->rear = (queue->rear + 1) % MAXSIZE;
    return 1;
}

deQueue

将元素出队。如果队空则不能出队，返回 0 表示出队失败。将出队元素保存到 ele，并返回 1 表示出队成功。以 queue=[a, b, c, d, e, f, g] 为例如图所示：

实现步骤：

• 参数校验，如果队空，则不能出队。返回 0 表示出队失败。
• 将元素出队。用 ele 保存队头指针所指向的元素。
• 然后将队头指针加一，保证队头指针始终指向队头元素。
• 返回 1 表示出队成功。

实现代码如下：

/**
 * 将元素出队
 * @param queue 循环队列
 * @param ele 用来保存出队的元素
 * @return 如果队空则不能出队则将返回 0 表示出队失败；否则返回 1 表示出队成功
 */
int deQueue(CircularQueue *queue, int *ele) {
    // 0.参数校验，如果队空则不能出队
    if (queue->rear == queue->front) {
        return 0;
    }
    // 1.将队头元素出队
    // 1.1 用 ele 保存队头指针所指向的元素
    *ele = queue->data[queue->front];
    // 1.2 将队头指针加一，表示删除队头元素。因为是循环队列，所以要对 MAXSIZE 取余
    queue->front = (queue->front + 1) % MAXSIZE;
    // 1.3 返回 1 表示出队成功
    return 1;
}

size

获取循环队列中实际的元素个数。

实现步骤：

• 循环队列的元素个数即 (rear-front+MAXSIZE)%MAXISZE。

实现代码如下：

/**
 * 获取循环队列中的元素个数
 * @param queue 循环队列
 * @return 队列中的元素个数
 */
int size(CircularQueue queue) {
    // 如果是顺序队列，则元素个数是 rear-front
    // 如果是循环队列，则元素个数是 (rear-front+MAXSIZE)%MAXSIZE
    return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}

getFront

读取队头元素，但并不出队。如果队空则不能读取，则返回 0，否则用 ele 保存队头元素，返回 1 表示读取成功。

实现步骤：

• 参数校验，如果队空则没有队头元素，自然也无法获取。返回 0 表示读取失败。
• 直接读取队头指针所指向的元素。因为队头指针始终指向队头元素。

实现代码如下：

/**
 * 获取循环队列的队头元素
 * @param queue 循环队列
 * @param ele 用来保存队头元素
 * @return 如果队列为空则返回 0 表示获取失败；否则返回 1 表示获取成功。
 */
int getFront(CircularQueue queue, int *ele) {
    // 0.参数校验，如果队列为空则没有队头元素，自然无法获取，所以返回 0 表示获取失败
    if (queue.rear == queue.front) {
        return 0;
    }
    // 1.用 ele 保存队头元素，即队头指针所指向的元素
    *ele = queue.data[queue.front];
    return 1;
}

getRear

读取循环队列的队尾元素。如果循环队空为空则返回 0 表示读取失败。否则用 ele 保存队尾元素，并返回 1 读取成功。

实现步骤：

• 参数校验，如果队空，则不能读取队尾元素。返回 0 表示读取失败。
• 读取队尾指针所指向位置的前一个位置的元素，用 ele 保存。因为队尾指针始终指向队尾元素的下一个位置，所以要读取队尾元素，需要读取到队尾指针的前一个位置的元素。但并不是队尾指针单纯的减一，因为是循环队列。
• 返回 1 表示读取成功。

实现代码如下：

/**
 * 获取循环队列中的队尾元素
 * @param queue 循环队列
 * @param ele 用来保存队尾元素
 * @return 如果队列为空则返回 0 表示获取失败；否则返回 1 表示获取成功。
 */
int getRear(CircularQueue queue, int *ele) {
    // 0.参数校验，如果队列为空则没有队尾元素，自然无法获取，所以返回 0 表示获取失败
    if (queue.rear == queue.front) {
        return 0;
    }
    // 1.用 ele 保存队尾元素，由于队尾指针指向队尾元素的下一个位置，所以要队尾指针减一
    *ele = queue.data[(queue.rear - 1 + MAXSIZE) % MAXSIZE];
    return 1;
}

clear

清空循环队列。

实现步骤：

• 将双端队列的队头指针 front 和队尾指针 rear 都指向 0，表示空队列。但实际上队列中原有的元素仍然存在，并没有被重置为某个值。

实现代码如下：

/**
 * 清空循环队列
 * @param queue 循环队列
 */
void clear(CircularQueue *queue) {
    // 即将队头指针和队尾指针都指向 0，表示恢复循环队列的初始状态，即空表
    queue->front = 0;
    queue->rear = 0;
}

print

打印循环队列中的所有有效元素。

实现步骤：

• 从队头指针开始扫描整个循环队列，直到队尾指针结束，但不包括队尾指针所指向的元素。

实现代码如下：

/**
 * 打印循环队列中从队头到队尾的所有元素
 * @param queue 循环队列
 */
void print(CircularQueue queue) {
    printf("[");
    int front = queue.front;
    while (front != queue.rear) {
        printf("%d", queue.data[front]);
        if (front != (queue.rear - 1 + MAXSIZE) % MAXSIZE) {
            printf(", ");
        }
        front = (front + 1) % MAXSIZE;
    }
    printf("]\n");
}

注意事项

无。

练习题

• Example001-用两个栈 s1 和 s2 来模拟一个队列，实现队列的出队、入队、队是否为空的运算
• Example004-设计一个循环队列，用 front 和 rear 分别作为队头和队尾指针，另外用一个标志 tag 表示队列是空还是不空
• Example005-Q 是一个队列，S 是一个空栈，实现将队列中的元素逆置的算法

目录

概念

循环队列的作用

题目

注意事项

题解

用顺序表的实现

用链表的实现

---

概念

 基于队列的先进先出的原则，在确定了队列长度的前提下，另队列首尾相接而实现的一种结构。

循环队列的作用

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-circular-queue

题目

设置循环队列

注意事项

单纯把链表的首尾相接就可以吗？

那么我们来想想这样一个问题：空的循环队列是什么样的？

我们规定将头指针放在首元素的位置，尾指针放到尾元素的下一个位置，那空队列就是头指针和尾指针指向同一个位置。

那么，满的循环链表又是什么样的呢？

尾指针放在a8元素的后面，恰好又与空链表的指向完全相同。

那我们怎么解决呢？

难道在结构体放一个变量判断它是否以满吗？不是不可以，但稍微有点“笨重”。

所以我们不妨让队列多添加一个位置，这个位置不放任何元素，仅仅是为了区别空与满：

 

题解

与通常队列相似，循环队列同样也可以用链表与顺序表两种方式实现

用顺序表的实现

typedef int CQDataType;
typedef struct 
{
	CQDataType* cq;
	int head;
	int tail;
	int size;
} myCircularQueueEnQueue;
bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj);
bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj);
//构造器，设置队列长度为 k 
myCircularQueueEnQueue* myCircularQueueEnQueueCreate(int k) 
{
	myCircularQueueEnQueue* newCQ = (myCircularQueueEnQueue*)malloc(sizeof(myCircularQueueEnQueue));
	assert(newCQ);
	CQDataType* newcq = (CQDataType*)malloc(sizeof(CQDataType) * (k + 1));
	assert(newcq);
	newCQ->size = k;
	newCQ->cq = newcq;
	newCQ->head = 0;
	newCQ->tail = 0;
	return newCQ;
}
//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueueEnQueue(myCircularQueueEnQueue* obj, int value) 
{
	if (myCircularQueueEnQueueIsFull(obj))
	{
		return 0;
	}
	obj->cq[obj->tail] = value;
	obj->tail = (obj->tail + 1) % (obj->size + 1);
	return 1;
}
//从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueEnQueueDeQueue(myCircularQueueEnQueue* obj)
{
	if (myCircularQueueEnQueueIsEmpty(obj))
	{
		return 0;
	}
	//obj->head = ((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1);
	obj->head = (obj->head + 1) % (obj->size + 1);
	return 1;
}
//从队首获取元素。如果队列为空，返回 -1
int myCircularQueueEnQueueFront(myCircularQueueEnQueue* obj)
{
	if (obj->head == obj->tail)
	{
		return -1;
	}
	else
	{
		return obj->cq[obj->head];
	}
}
// 获取队尾元素。如果队列为空，返回 -1
int myCircularQueueEnQueueRear(myCircularQueueEnQueue* obj)
{
	if (obj->head == obj->tail)
	{
		return -1;
	}
	else
	{
		return obj->cq[((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1)];
	}
}
//检查循环队列是否为空
bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj) 
{
	return obj->head == obj->tail;
}
//检查循环队列是否已满
bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj)
{
	return (obj->tail + 1) % (obj->size + 1) == obj->head;
}
//释放
void myCircularQueueEnQueueFree(myCircularQueueEnQueue* obj) 
{
	free(obj->cq);
	free(obj);
}

用链表的实现

typedef int CQDataType;
typedef struct CQListNode
{
	struct CQListNode* _next;
	CQDataType _data;
}CQNode;
typedef struct 
{
	CQNode* _head;
	CQNode* _tail;
	int size;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);


MyCircularQueue* myCircularQueueCreate(int k)
{
	MyCircularQueue* CQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	assert(CQ);
	CQ->size = k;
	CQNode* head = (CQNode*)malloc(sizeof(CQNode));
	assert(head);
	CQNode* cur = CQ->_head = CQ->_tail = head;
	for (int i = 0; i < k; i++)//加上面共k+1个节点
	{
		CQNode* cq = (CQNode*)malloc(sizeof(CQNode));
		assert(cq);
		cur->_next = cq;
		cq->_next = NULL;
		cur = cur->_next;
	}
	cur->_next = head;

	return CQ;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
	if (!myCircularQueueIsFull(obj))
	{
		obj->_tail->_data = value;
		obj->_tail = obj->_tail->_next;
		return 1;
	}
	else
	{
		return 0;
	}
	
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
	if (!myCircularQueueIsEmpty(obj))
	{
		obj->_head = obj->_head->_next;
		return 1;
	}
	else
	{
		return 0;
	}
}

int myCircularQueueFront(MyCircularQueue* obj)
{
	if (!myCircularQueueIsEmpty(obj))
		return obj->_head->_data;
	else
		return -1;
}

int myCircularQueueRear(MyCircularQueue* obj)
{
	if (!myCircularQueueIsEmpty(obj))
	{
		CQNode* cur = obj->_head;
		while (cur->_next != obj->_tail)
		{
			cur = cur->_next;
		}
		return cur->_data;
	}
	else
		return -1;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
	return obj->_head == obj->_tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	return obj->_tail->_next == obj->_head;
}

void myCircularQueueFree(MyCircularQueue* obj)
{
	/*CQListNode* cur = obj->_head;
	while(cur->_next!=cur)*/
	CQNode* cur = obj->_head;
	CQNode* next = NULL;

	for (int i = 0; i < obj->size; i++)
	{
		next = cur->_next;
		free(cur);
		cur = next;
	}
	free(obj);
}

什么是队列

队列和数组，链表，栈一样都是属于线性数据结构，而队列又和栈比较相似，都属于操作受限的数据结构，其中栈是“后入先出”，而队列是“先进先出”。

和栈一样，队列也仅有两个基本操作：入队和出队（栈则是入栈和出栈）。往队列中放元素称之为入队，往队列中取元素称之为出队，然而相对于栈来说，队列又会复杂一点。

队列中通常需要定义两个指针：head 和 tail（当然，也有称之为：front 和 rear）分别用来表示头指针和尾指针。初始化队列时，head 和 tail 相等，当有元素入队时，tail 指针往后移动一位，当有元素出队时，head 指针往后移动一位。

队空和队满

根据上面的队列初始化和入队出队的过程，我们可以得到以下三个关系：

• 初始化队列时：head=tail=-1（这里也可以设置为 0，看具体实现）。
• 队列满时：tail=size-1（其中 size 为初始化队列时队列的大小）。
• 队列空时：head=tail（比如上图中的第一和第三个队列）。

队列的实现

和栈一样，队列也可以通过数组或者链表来实现，通过数组来实现的队列我们称之为“顺序队列”，通过链表实现的队列称之为“链式队列”。

数组实现队列

package com.lonely.wolf.note.queue;

/**
 * 基于数组实现自定义单向队列。FIFO(first in first out)先进先出
 * @author lonely_wolf
 * @version 1.0
 * @date 2021/12/26
 * @since jdk1.8
 */
public class MyQueueByArray<E> {
    public static void main(String[] args) {
        MyQueueByArray myQueue = new MyQueueByArray(3);
        System.out.println("队列是否为空：" + myQueue.isEmpty());//输出:true
        myQueue.enqueue(1);
        myQueue.enqueue(2);
        myQueue.enqueue(3);
        System.out.println("队列是否已满：" + myQueue.isFull());//输出:true
        System.out.println("第1次出队：" + myQueue.dequeue());//输出:1
        System.out.println("第2次出队：" + myQueue.dequeue());//输出:2
        System.out.println("第3次出队：" + myQueue.dequeue());//输出:3
        System.out.println("队列是否为空：" + myQueue.isEmpty());//输出:true
        System.out.println("队列是否已满：" + myQueue.isFull());//输出:true
    }

    private Object[] data;
    private int size;//队列长度
    private int head;//队列头部
    private int tail;//队列尾部

    public MyQueueByArray(int size) {//初始化
        this.size = size;
        data = new Object[size];
        head = -1;
        tail = -1;
    }

    /**
     * tail=size-1 表示队列已满
     * @return
     */
    public boolean isFull(){
        return tail == size - 1;
    }

    /**
     * head=tail表示队列为空
     * @return
     */
    public boolean isEmpty(){
        return head == tail;
    }


    /**
     * 元素入队，tail指针后移一位
     * @param e
     * @return
     */
    public boolean enqueue (E e){
        if (isFull()){
            return false;
        }
        data[++tail] = e;//tail 指针后移
        return true;
    }


    /**
     * 元素出丢
     * @return
     */
    public E dequeue (){
        if (isEmpty()){
            return null;
        }
        E e = (E)data[++head];//出队
        return e;
    }
}

链表实现队列

有了上面基于数组实现的简单队列例子，基于链表实现队列相信大家也能写出来，如果用链表实现队列，我们们同样需要head 指针和 tail 指针。其中 head 指向链表的第一个结点，tail 指向最后一个结点。

入队时：

tail.next = newNode;
tail = tail.next;

出队时：

head = head.next;

假溢出问题

我们回到上面数组实现的例子中，我们发现最后的两个输出语句两个都是 true，也就是队列又是空的又是满的，这看起来是一个自相矛盾的事情却在队列里面出现了，我们来看看这时候队列的示意图：

通过上图中我们发现，因为 tail=size-1，所以队列是满的；而此时又同时满足：head=tail，所以根据上面队空的条件，我们又可以得到当前队列是空的，也就是当前队列是没有元素的。这时候我们已经无法继续入队了，但是这时候队列中的其实是有空间的，有空间却不能被利用，这就是单向队列的“假溢出”问题。

那么如何解决这个问题呢？解决这个问题有两个思路。

• 思路一

前面我们学习数组的时候提到了，当数组中删除一个元素，那么这个位置之后的所有元素都需要往前移动一位，所以队列中也是同理，假如我们用数组来实现的话，当元素出队时，我们把所有元素都往前移，不过这样因为每次都需要搬移数据，导致入队的时间复杂度是 O(n)。

• 思路二

因为搬移数据会影响到入队效率，那么如何不搬移数据又能将队列的空闲空间利用起来呢？答案也很简单，那就是当再次有新元素入队时，我们把 tail 指针又重新移动到队列的最开头位置，这样也能避免出现“假溢出”问题，同时时间复杂度仍然保持为 O(1)。

循环队列

上面提到的第二种思路来解决单向队列的“假溢出”问题，实际上就构成了一个循环队列。而上面单向队列判断当前队列是否队满时仅需要满足 tail=size-1 即可，但是循环队列肯定不行，因为当 tail=size-1 时继续添加元素，tail 可能可以移动到 size=0 的位置，所以如果要实现循环队列最关键还是需要确定好队空和队满的条件。

队空和队满

在循环队列中，当初始化队列时，一般会将其设置为 0，而队空条件仍然是 head=tail，循环队列最关键的是如何确定队满条件。

下图是初始化一个长度为 6 的队列以及连续入队 5 个元素后的循环队列中 head，tail 指针示意图：

上图中第二个队列表示的是入队 5 个元素之后 tail 指针的位置，这时候如果继续入队，那么 tail 只能指向队列开头也就是元素 1 所在的位置，此时会得到下面这个示意图的场景：

这时候发现 head=tail，和队空时的条件冲突了，那么如何解决这个问题呢？主要有三种解决办法：

1. 当 (tail+1)%size=head 时就表示队列已满，这时候 tail 所在位置为空，所以会浪费一个空间（也就是第一幅图中第二个队列的场景就算队列已满）。
2. 新增一个容量 capacity 字段，并进行维护，当 capacity=size 表示队列已满。
3. 和第二个办法差不多，我们可以再维护一个标记，或者当 head=tail 时同步判断当前位置是否有元素来判断当前是队空还是队满。

这三种思路我们发现都各有缺点：方法 1 会浪费一个空间；方法 2 每次入队和出队时候都需要维护 capacity 字段；方法 3 就是不论队列空或者队列满时都要多一次判断方式。

相互比较之下，其实方法一的思路就是空间换时间，而另外两种办法当数据量并发量很大时，多一次判断其实也是会对性能有所影响，常规的循环链表会采用方法 1 进行处理，也就是选择浪费一个空间的方式。当然大家在实际开发过程中也可以自行斟酌。

实现循环队列

下面我们就以方法 1 的思路基于数组来实现一个循环队列：

package com.lonely.wolf.note.queue;

/**
 *
 * 实现循环队列
 * @author lonely_wolf
 * @version 1.0
 * @date 2021/12/26
 * @since jdk1.8
 */
public class MyCycleQueueByArray<E> {

    public static void main(String[] args) {
        MyCycleQueueByArray cycleQueue = new MyCycleQueueByArray(3);
        System.out.println("循环队列是否为空：" + cycleQueue.isEmpty());//输出:true
        System.out.println("1是否入队成功：" + cycleQueue.enqueue(1));//输出:true
        System.out.println("2是否入队成功：" + cycleQueue.enqueue(2));//输出:true
        System.out.println("3是否入队成功：" + cycleQueue.enqueue(3));//输出:false
        System.out.println("循环队列是否已满：" + cycleQueue.isFull());//输出:true
        System.out.println("第1次出队：" + cycleQueue.dequeue());//输出:1
        System.out.println("第2次出队：" + cycleQueue.dequeue());//输出:2
        System.out.println("第3次出队：" + cycleQueue.dequeue());//输出:null，因为 3 入队失败
        System.out.println("循环队列是否为空：" + cycleQueue.isEmpty());//输出:true
        System.out.println("循环队列是否已满：" + cycleQueue.isFull());//输出:false
    }

    private Object[] data;
    private int size;
    
    private int head;//队列头部
    private int tail;//队列尾部

    public MyCycleQueueByArray(int size) {
        this.size = size;
        data = new Object[size];
        head = 0;
        tail = 0;
    }

    public boolean isFull(){
        return (tail + 1) % size == head;
    }

    public boolean isEmpty(){
        return head == tail;
    }

    /**
     * 入队
     * @param e
     * @return
     */
    public boolean enqueue (E e){
        if (isFull()){
            return false;
        }
        data[tail] = e;
        tail =  (tail + 1) % size;//注意这里不能直接 tail++，否则无法循环使用
        return true;
    }


    /**
     * 出队
     * @return
     */
    public E dequeue (){
        if (isEmpty()){
            return null;
        }
        E e = (E)data[head];
        head =  (head + 1) % size;//head 也同样不能直接 head++
        return e;
    }
}

这时候我们发现，虽然队列空间有 3 个，但是实际上只能存放 2 个元素，而最后两条输出语句的输出结果也说明了循环队列不会出现单向队列的“假溢出问题”。

队列实战

队列其实在 Java 的 juc 中有广泛应用，比如 AQS 等，在这里，我们继续来看一看队列的相关算法题来加深对队列的理解。

两个栈实现队列

前面我们讲栈的时候，用了两个队列来实现栈，这道题却正好相反，是利用两个栈来实现队列。

LeetCode 第 232 题：请你仅使⽤两个栈实现先⼊先出队列，队列应当⽀持⼀般队列⽀持的所有操作（push、pop、peek、empty）。

这道题目其实相比较之前两个队列实现栈还是会更简单一点，因为栈是后入先出，所以我们只需要将入队和出队使用不同的栈就可以解决了。

具体解题思路为：将⼀个栈当作输⼊栈，⽤于压⼊（push）传⼊的数据；另⼀个栈当作输出栈，⽤于 pop（出队） 和 peek（查看队列头部元素） 操作。 每次 pop 或 peek 时，若输出栈为空则将输⼊栈的全部数据依次弹出并压⼊输出栈，再将元素从输出栈输出。

具体代码实现为：

package com.lonely.wolf.note.queue;

import java.util.Stack;

/**
 * LeetCode 232
 * 请你仅使⽤两个栈实现先⼊先出队列。队列应当⽀持⼀般队列⽀持的所有操作（push、pop、peek、empty）：
 *
 * void push(int x) 将元素 x 推到队列的末尾
 * int pop() 从队列的开头移除并返回元素
 * int peek() 返回队列开头的元素
 * boolean empty() 如果队列为空，返回 true ；否则，返回 false
 *
 * 说明：
 * 你只能使⽤标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
 * 你所使⽤的语⾔也许不⽀持栈。你可以使⽤ list 或者 deque（双端队列）来模拟⼀个栈，只要是标准的栈操作即可。
 *
 * 解题思路
 * 将⼀个栈当作输⼊栈，⽤于压⼊ push 传⼊的数据；另⼀个栈当作输出栈，⽤于 pop 和 peek 操作。
 * 每次 pop 或 peek 时，若输出栈为空则将输⼊栈的全部数据依次弹出并压⼊输出栈，
 *
 * @author lonely_wolf
 * @version 1.0
 * @date 2021/12/26
 * @since jdk1.8
 */
public class MyQueueByTwoStack<Integer> {
    private Stack<Integer> inStack;//输入栈
    private Stack<Integer> outStack;//输出栈

    /**
     * 即入队：enqueue 操作
     * @param e
     */
    public void push(Integer e){
        inStack.push(e);//压入输入栈
    }

    /**
     * 查看并移除队列头部元素，即：出队 dequeue 操作
     * @return
     */
    public Integer pop(){
        if (!outStack.isEmpty()){//输出栈不为空则直接出栈
            return outStack.pop();
        }
        while (!inStack.isEmpty()){//输出栈为空，则检查输入栈
            outStack.push(inStack.pop());//输入栈不为空，则将其压入输出栈
        }
        if (!outStack.isEmpty()){//再次检查输出栈是否有元素出栈
            return outStack.pop();
        }
        return null;
    }

    /**
     * 查看队列头部元素，相比较 pop，这里只查看元素，并不移除元素
     **/
    public Integer peek(){
        if (!outStack.isEmpty()){
            return outStack.peek();
        }
        while (!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
        if (!outStack.isEmpty()){
            return outStack.peek();
        }
        return null;
    }

    /**
     * 队列是否为空
     * @return
     */
    public boolean empty(){
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

总结

本文主要讲述了队列这种操作受限的数据结构，文中通过一个例子说明了单向链表为什么会存在“假溢出“问题，并最终引出了循环链表，而循环链表的实现同样有三种不同思路，并通过以空间换时间的方法基于数组实现了一个简单的循环链表。最后我们还讲述了如何利用两个栈来实现一个队列。