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

理论

• 存在的意义：
  将序次队列从逻辑上视为一个环。解决“假溢出”（出队入队连续操作后两个指针均到数组末了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;
  
• 区分队满的三种解决办法
  

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

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

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

代码练习

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

1. class CircularQueue:
2.     def __init__(self, n):
3.         # do intialization if necessary
4.         self.arr = [None]*n
5.         self.head, self.tail = 0, -1 #队尾先+1再放元素
6.         self.size = n
7.     """
8.     @return:  return true if the array is full
9.     """
10.     def isFull(self):
11.         return self.head == (self.tail + 1) % self.size and not self.arr[self.tail] is None
12.         
13.     """
14.     @return: return true if there is no element in the array
15.     """
16.     def isEmpty(self):
17.         return self.arr[self.tail] is None #队尾始终指向最后一个元素
18.         
19.     """
20.     @param element: the element given to be added
21.     @return: nothing
22.     """
23.     def enqueue(self, element):
24.         self.tail = (self.tail + 1) % self.size
25.         self.arr[self.tail] = element
27.     """
28.     @return: pop an element from the queue
29.     """
30.     def dequeue(self):
31.         ele = self.arr[self.head]
32.         self.arr[self.head] = None
33.         self.head = (self.head + 1) % self.size
34.         return ele

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。