循环队列

佚名 6年前 (2019-04-12) 随笔 1162人围观抢沙发百度已收录

大概大姨妈来了，脑子有点昏，一个循环队列想了一晚上，也算是把各种情况都遍历了...

队列强调 先进先出。如果使用单向队列就会浪费空间，因此建议使用循环队列。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

队列涉及到的操作就是 插入、删除、读取头/尾元素、判断是否为空/满。

队列的初始化就是队列的大小，因此队列类的定义就包括数据数组、头尾指针（head/tail）、以及数组大小。

常规来说，当head == tail 就判断为空，当(tail + 1)%size == head就判断为满，但这样做有问题。首先，初始化的时候head = tail，当插入第一个数据时，head和tail要不要同时加1呢，肯定不能同时加啊，加完head=tail就会被判断为空，也就是说，在这种判断是否为空/满的准则下，当只有一个元素的时候head和tail肯定不能相等。那就让它们错开一位吧，让head指向头元素的前一位，tail指向尾元素。

但问题继续来了，假设数组大小为size，现在已经插入size-1个元素了，此时 (tail + 1)%size = head啦，就会被判断为满，不能再进行插入了，也就是说，如果让head和tail错开一位，就只能插入size-1个元素，这样的类构建出来会让使用者觉得纳闷吧。解决方法就是，当初始化要求数组大小为size，我们就构建一个大小为size+1的数组！

class MyCircularQueue { private: int * data; int head; int tail; int size; public: /** Initialize your data structure here. Set the size of the queue to be k. */ MyCircularQueue(int k) { data = new int[k+1]; head = 0; tail = 0; size = k+1; } /** Insert an element into the circular queue. Return true if the operation is successful. */
        bool enQueue(int value) { if(!isFull()){ tail = (tail + 1)%size; data[tail] = value; return true; } return false; } /** Delete an element from the circular queue. Return true if the operation is successful. */
        bool deQueue() { if(!isEmpty()){ head = (head + 1)%size; return true; } return false; } /** Get the front item from the queue. */
        int Front() { if(!isEmpty()){ return data[(head+1)%size]; } return -1; } /** Get the last item from the queue. */
        int Rear() { if(!isEmpty()){ return data[tail]; } return -1; } /** Checks whether the circular queue is empty or not. */
        bool isEmpty() { if(head == tail) return true; return false; } /** Checks whether the circular queue is full or not. */
        bool isFull() { if((tail+1)%size == head) return true; return false; } };

总体来说，造成上面那么多问题都是由构建判断是否为空/满的准则导致的。那有没有什么别的准则呢？还是有的。

看leetcode官方代码时看到了这样一种准则：当head == -1时就判断为空，当(tail + 1)%size == head就判断为满。初始化的时候就让head = tail = -1，然后每次添加元素时判断数组不为满后还要判断数组是不是空，如果为空就让head = 0，删除元素判断数组不为空后还要判断head和tail是否相等，如果相等就让head = tail = -1，相当于重置啦。还是有点绕。