【数据结构】循环队列原理与代码

理论

• 存在的意义：
  将顺序队列从逻辑上视为一个环。解决“假溢出”（出队入队连续操作后两个指针均到数组末端maxsize-1处，虽然队里没有元素但无法让元素进队）。
• 两种定义
  1.题目是队列非空时队头指针和队尾指针分别指向队头元素和队尾元素时，则初始时front=0,rear=n-1，每次入队时rear++再放新元素。
  这种情况下 q.front=(q.rear+maxsize-q.length+1)%maxsize
  2.而队尾指针指向队尾元素的下一个时，则front=rear=0，每次入队时先放新元素再rear++;
  这种情况下 q.front==(q.rear+maxsize-q.length)%maxsize

总结：front初始只有可能为0！

• 严蔚敏版的定义
  【严书规定】初始front=rear=0；非空队列中头指针始终指向队头，尾指针始终指向队尾的下一个位置。
  初始：Q.front=Q.rear=0;
  进队：Q.rear=(Q.rear+1)%MaxSize;
  出队：Q.front=(Q.front+1)%MaxSize;
  队列长度 (Q.rear-Q.front+MaxSize)%MaxSize;
• 区分队满的三种解决办法

1. 牺牲一个单元，入队时少用一个队列单元，否则队空队满的判断条件相同导致无法确定。
   队满条件：(Q.rear+1)%MaxSize==Q.front;//rear所指的单元始终为空。
   队空条件：Q.rear=Q.front;
   队列长度:(Q.rear-Q.front+MaxSize)%MaxSize;
2. 增设表示元素个数数据成员Q.size
3. 增设tag，删除时tag=0;入队时tag=1;当Q.front==Q.rear时可区分。（操作完后检查空满并赋值tag）

注意：出队入队之前的检查空满的条件

• 循环链队判空：rear->next ==rear

代码练习

https://www.lintcode.com/problem/955/

class CircularQueue:def __init__(self, n):# do intialization if necessaryself.arr = [None]*nself.head, self.tail = 0, -1 #队尾先+1再放元素self.size = n"""@return:  return true if the array is full"""def isFull(self):return self.head == (self.tail + 1) % self.size and not self.arr[self.tail] is None"""@return: return true if there is no element in the array"""def isEmpty(self):return self.arr[self.tail] is None #队尾始终指向最后一个元素"""@param element: the element given to be added@return: nothing"""def enqueue(self, element):self.tail = (self.tail + 1) % self.sizeself.arr[self.tail] = element"""@return: pop an element from the queue"""def dequeue(self):ele = self.arr[self.head]self.arr[self.head] = Noneself.head = (self.head + 1) % self.sizereturn ele