数据结构-->设计循环队列（OJ）

标签：10 obj OJ -- oss process 数据结构 image

各位好友，今天我们着重讲解，如何设计出一个循环队列，以及一些大坑如何避免与规避 ！！

题目如下：

数据结构-->设计循环队列（OJ）_循环队列

本道 OJ 稍微有些复杂了。可以说，是前面几期的 栈与队列的试金石

至于思路，在这里特别强调一下，千万别用 --->链表去实现，因为贼恶心！！太难控制，以及不好操作

比如，若用链表，那么你在找尾的时候贼难受，以及你在插入数据的时候也会不方便！

所以，我们都是学习者，大佬的做法是，用数组去实现！这是最为简单的操作了，逻辑以及理解上也都更容易些！

好了，废话不多讲！开始我们的代码之旅吧！！

//匿名结构体
typedef struct
{
  int* a;
  int front;	//头部
  int rear;		//尾部
  int k;			//数组长度
}MyCircularQueue;

//创建循环队列准备工作
void MyCircularQueueCreate()
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue* obj));
  obj ->front = 0;
  obj ->rear = 0;		//此处用数字 0 进行初始化，别用 NULL 因为 OJ 上的要求还是相当严格的，前面结构头定义处用了 int 而不是 指针类型
  obj ->a = (int*)malloc(sizeof(int) * (k + 1));		//稍后解释为什么是 k + 1
  return obj;
}

//布尔判空
bool MyCircularQueueEmpty(MyCircularQueue* obj)
{
	return obj ->rear == obj ->front;
}

//布尔判满
bool MyCircularQueueIsFull(MyCircularQueue* obj)
{
		return (obj ->rear + 1) % (obj -> k + 1) == obj ->front;
}

//入队列, 插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
	if(MyCircularQueueIsFull(obj))
    return -1;
  
  obj ->a[obj ->rear++] = value;
  obj ->rear %= (obj ->k + 1);
  return true;
}

各位老友，写到这里，我必须要吐槽一下，这里的代码面板！！刚刚就挺不方便的，应该是出了 BUG

在括号内书写代码的时候，或者按下空格键的时候，会将后面的括号给吞并了！！太令人气愤了！！说真的，前些时候，这里的博客，我在书写的时候就出现过这样的问题。

当时心想着，过段时间会有人给官方反馈，可是如今看来问题仍然存在！！太 * 了！！忍不住想爆粗口！！

现在让我们继续进行我们的代码之旅吧！！

//继续前进

//移除对列内的元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
	if(MyCircularQueueEmpty(obj))
    	return -1;
    
    ++obj ->front;
    obj ->front %= (obj ->k + 1);
    return true;
}

//头部元素
int MyCircularQueueFront(MyCircularQueue* obj)
{
	if(MyCircularQueueEmpty(obj))
    {
		return -1;    
    }
    
    return obj ->a[obj ->front];
}

//尾部元素
int MyCircularQueueRear(MyCircularQueue* obj)
{
	if(MyCircularQueueEmpty(obj))
    {
    	return -1;
    }
    
    return obj ->a[obj ->rear -1 + obj ->k + 1 % (obj ->k + 1)];
}

//销毁
void MyCircularQueueDestroy(MyCircularQueue* obj)
{
	free(obj ->a);
    free(obj);		//前面有两次的空间的开辟，那忘记释放，防止内存泄露！！别让以后的面试官把你给问倒了！
}

好了，各位老友！！我们的循环队列设计代码已经手搓完了！！为了方便老友们的观感体验！！特此附上有色彩的代码图样：

数据结构-->设计循环队列（OJ）_OJ_02

接下来，将对一些出现的大坑进行讲解与规避

另外，我还想说明一点儿！！在 OJ 上看别人写的代码，让我有一种 “压力”，说白了，就是写的太挫了！！就算有错误也是可以谅解的！！但是有些人，非要与众不同，比如，创建数组的时候，可以用一个字母 ‘a’ 就完全可以，而且简单明了！！非要有人偏偏写成 element 哈，难不成你是在秀你的英语水平吗！！这种代码，就是太挫了！！当然了，拼音的就更挫了，不能提！！希望作为一名程序员，踏入了这个行业，自身的素养还是要提高的

毕竟以后，进入公司之后！！讲究的是一种团队合作精神！！自个儿单干，写的代码，想那*啥似的！！可别怪当时候有人另眼相看了！！扯了，这么多，让我们回归正题吧！！

下面的坑，有好几个，我会分成几个模块讲解的！！

模块一：

数据结构-->设计循环队列（OJ）_OJ_03

这部分的代码，有一两处需要额外注意！！比如，为何数组 a 的开辟空间要多一个整形空间

这里数组 a 的最大存储数据个数就是 K 个，而 K+ 1 的目的是方便后期的维护，以及尾部头部指向位置的确定

简单说，如果数组存储数据过程中，要是满的话，用上述的方法，尾部位置确定就会变得方便许多，只需要将尾部模除一下，即 (rear + 1) % (K + 1) 结果是不是与头部位置相等了，也就是说，在这里实现了循环操作

显然代码 “obj ->a = k” 意即，数组 a 的最大存储数据个数为 k

模块二：

以下是挖坑写法：

数据结构-->设计循环队列（OJ）_OJ_04

这样造成的结果是，内存上有问题，如果深入探究，最终的结果是尾部的位置存在问题，如图所示：

数据结构-->设计循环队列（OJ）_循环队列_05

而这里的用例，可以当做一个很好的技巧来找寻错误。不用进行调试，我们这样能找到错误的根源！！

最后输入的用例：

数据结构-->设计循环队列（OJ）_OJ_06

我们可以删除掉最后一个 “Rear”, 会出现一个不错的结果：

数据结构-->设计循环队列（OJ）_OJ_07

此时，我们竟然发现大体上能跑起来了！！虽然还有随机数，以及布尔判断不对应，那个待会再讲解，属于下一个模块内容

此时的问题，我们已经锁定住了，就出现在 “Rear”上，即，尾部

那么，该究竟如何修正呢？这里，我们需要细致的考虑，尾部函数的实现，究竟存在着怎样的BUG

为了方便讲解，请看下面的图示样例：

数据结构-->设计循环队列（OJ）_循环队列_08

从上图中，我们可以看出，当删除队列内的元素之后，在寻找尾部后，会发现 rear 指向了 -1 的位置，此时就是相当严重的越界了！！因此会出现上述的乱码现象！！

那么，我们应该如何修正呢？

----->修正

当然就是先举例子，之后类比验证，发现规律就好了！比如，下图所示：

数据结构-->设计循环队列（OJ）_循环队列_09

我们要找到，rear 指向的位置 3 那么，具体的数学思想是什么呢？

----->

数据结构-->设计循环队列（OJ）_OJ_10

显然，各位老友们，我们带个数验证一下就可以了！！（3 - 1 + 4 + 1）% （4 + 1）模除结果，仍然是我们想要的正确位置 3 ，当然了，还有一种情况，那就是，rear 的位置在 front 之后，此时模除之后就调整到 front 前面了。此时的思想更加符合循环的味道了！！其实这种思想简直就是大佬的思想，当然了，我只是一个学习者！！

如此，我们这块的大坑就算是填装好了！！接下来，让我们进入下一个模块，布尔判断的对应关系！！

模块三：

请看下列尾部实现环节的图示：

数据结构-->设计循环队列（OJ）_循环队列_11