622 设计循环队列——Leetcode天天刷【循环队列，数组模拟，双指针】（2022.8.2）

前言

简单写了今天的题目，是一道典型的数据结构模拟题，要求我们模拟循环队列。

啥，问我为啥，昨天的没写，因为昨天的太简单了。。。

题目信息

题目链接：622. 设计循环队列 - 力扣（LeetCode）

很简单，就是需要我们不使用内置的队列库，来实现一个 循环队列。

啥是循环队列？

循环队列 其实就是相较于 一般的队列而言，可以循环使用队列内部的空间。队列，它是具有 先进先出 特性的数据结构，在插入和删除的过程中，队列会往队列尾部插入元素，队列首部删除元素，而如果我们对 静态顺序表 即 数组 这一数据结构熟悉的话，删除 这个操作其实并不是直接删除元素，而是把队首的指针向后移动。那么这样就会有一个问题：删除位置的空间被浪费。

循环队列就是基于这样的一个问题而诞生的，通过循环队列，可以有效地利用队列的空间，删除的位置还可以继续使用。

输入与输出

这次做了本地调试，所以稍稍根据示例设计了下样例。

我们根据leetcode的这段注释来设计样例

/** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue* obj = new MyCircularQueue(k); * bool param_1 = obj->enQueue(value); * bool param_2 = obj->deQueue(); * int param_3 = obj->Front(); * int param_4 = obj->Rear(); * bool param_5 = obj->isEmpty(); * bool param_6 = obj->isFull(); */

输入

我们先输入整数k，表示循环队列的尺寸。

然后接下来，输入参数，1~6表示对应的操作，如果是1，即 插入，我们还需要输入 插入数值。

输出

我们根据，操作是否成功来对应输出，详见样例。

样例

input

3
1 1
1 2 
1 3
1 4
4
6
2
1 4
4
2
2
2
2
6
5

output

insert success!
insert success!
insert success!
insert failed!
queue is fulled!
delete success!
insert success!
4
delete success!
delete success!
delete success!
delete failed!
queue isn't fulled!
queue is empty!

题目提示

• 所有的值都在 0 至 1000 的范围内；
• 操作数将在 1 至 1000 的范围内；
• 请不要使用内置的队列库。

解题思路——数组模拟，双指针

其实这道题也可以使用链表来实现，但是个人认为使用数组会更加有挑战性，链表的实现很简单，有兴趣的同学可以试一下。

可以先看下，下列示意图

用ppt画的，个人作画水平有限，看个抽象就行。

我们可以看到，数组是一个环形，有两个指针front 和 rear，分别指向队列头和尾，基于这样子的一个机制，我们就可以设计并实现出循环队列，以及相关的函数。

特别的，我们需要知道队列中队首或者队尾的元素是否为空，这时我们需要做特殊值判断。回顾题目提示，输入的值都在0到1000之间，我们只要使用一个不在这个范围内的值，比如-1，去表示这个位置为空即可。

通过效果

100%，不愧是我！

code（c++）

#include<iostream>
#include<vector>

using namespace std;

class MyCircularQueue
{
    
private:
	int len;
	vector<int> myQue;
	int front, rear;
public:
	// 初始化容器，尺寸，队首和队尾的下标位置
	MyCircularQueue(int k)
	{
    
		// 初始化各项成员属性
		len = k;
		myQue = vector<int>(k, -1);		// 初始化为-1
		front = rear = 0;
	}

	// 插入数值--尾插
	bool enQueue(int value)
	{
    
		// 判断是否队列已满, 如果满了就返回false
		if (isFull())
		{
    
			return false;
		}
		myQue[rear++] = value;
		rear %= len;
		return true;
	}

	// 删除元素,这里应该是删除队首元素
	bool deQueue()
	{
    
		// 需要先判断是否为空
		if (isEmpty())
		{
    
			return false;
		}
		// 如果不为空,则执行删除
		myQue[front++] = -1;
		front %= len;
		return true;
	}

	// 获取队首
	int Front()
	{
    
		// 这里可以不用判断,因为为空时,我们会将元素设置为空
		return myQue[front];
	}

	// 获取队尾
	int Rear()
	{
    
		int index = (rear - 1 + len) % len;
		// 和队首获取同理
		return myQue[index];
	}

	// 判断队列是否为空
	bool isEmpty()
	{
    
		// 和判断队满类似, 利用下标和尺寸即可, 可以结合元素值是否-1
		if (front == rear && myQue[front] == -1)
		{
    
			return true;
		}
		return false;
	}

	// 判断是否满了
	bool isFull()
	{
    
		// 利用队首和队尾的下标判断
		if (rear == front && myQue[front] != -1)
		{
    
			return true;
		}
		return false;
	}
};

/** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue* obj = new MyCircularQueue(k); * bool param_1 = obj->enQueue(value); * bool param_2 = obj->deQueue(); * int param_3 = obj->Front(); * int param_4 = obj->Rear(); * bool param_5 = obj->isEmpty(); * bool param_6 = obj->isFull(); */

int main()
{
    
	int k;
	cin >> k;
	MyCircularQueue* obj = new MyCircularQueue(k);
	int op;
	int value;
	while (cin >> op)
	{
    
		switch (op)
		{
    
		case 1:		// 执行插入操作,需要先输入插入的数值
		{
    
			cin >> value;
			if (obj->enQueue(value))
			{
    
				cout << "insert success!" << endl;
			}
			else
			{
    
				cout << "insert failed!" << endl;
			}
			break;
		}
		case 2:		// 执行删除
		{
    
			if (obj->deQueue())
			{
    
				cout << "delete success!" << endl;
			}
			else
			{
    
				cout << "delete failed!" << endl;
			}
			break;
		}
		case 3:		// 获取队首
		{
    
			cout << obj->Front() << endl;
			break;
		}
		case 4:		// 获取队尾
		{
    
			cout << obj->Rear() << endl;
			break;
		}
		case 5:		// 判断是否为空
		{
    
			if (obj->isEmpty())
			{
    
				cout << "queue is empty!" << endl;
			}
			else
			{
    
				cout << "queue isn't empty!" << endl;
			}
			break;
		}
		default:	// 判断是否满了
		{
    
			if (obj->isFull())
			{
    
				cout << "queue is fulled!" << endl;
			}
			else
			{
    
				cout << "queue isn't fulled!" << endl;
			}
		}
		}
	}

	return 0;
}

后话

最近好累，好想睡觉。。。