数据结构之队列（循环队列）

循环队列

又称为环形队列，有如下4个特点：

• 在循环队列的定义中规定了两个索引指针：front 和 rear。front 指向第一个有效元素的位置，而rear 可以理解为用来记录队尾元素的下一个位置。
• 当队列为空时，front == rear;
• 当队列满时，(rear + 1) % n = front. 这样可以让队列看起来像一个环状结构，并使得 front 和 rear 可以循环使用。
• 队列的大小为 n - 1 个元素（n-1是队列真实的容量），其中一个空位留给判断队列为空的条件。

循环队列是一种特殊的线性表，它的内部用数组来实现。

与普通的队列不同的是，如果队满时再入队一个元素，并不会导致队列溢出，而是继续从队头插入，覆盖原有元素。

相对于链式存储结构的队列，数组实现的循环队列更加高效。

Java

 1 package org.allen.data.structure.queue;
 2 
 3 import javax.swing.plaf.synth.SynthOptionPaneUI;
 4 
 5 /**
 6  * 循环队列
 7  * <pre>
 8  *     出队：front指向第一个有效元素，删除即可。
 9  *           注意：
10  *               (1)不要吧front直接设置为下标0，防止头尾指针混乱，无法判断队列为空还是已满
11  *               (2)当尾指针指向队列的最后一个位置时，再插入一个数据，tail则指回到下标0，重新计算
12  *               (3)对尾指针求模运算的结果需要加上队列长度，否则可能越界
13  *     入队：rear指向下一个空位，插入数据，更新rear值
14  *           注意：由于有空位，所以不会覆盖原始数据
15  * </pre>
16  */
17 public class CircularQueue {
18 //    private int N;// 队列长度
19     protected int N;  // 队列长度,是其真实容量 + 1
20     private int[] array; // 存放数据的数组
21     private int start; // 队列头部
22     private int end; // 队列尾部
23 
24     public CircularQueue(int capacity) {
25         this.N = capacity + 1;
26         this.array = new int[N];
27         this.start = 0;
28         this.end = 0;
29     }
30 
31     public boolean isEmpty() {
32         return start == end;
33     }
34 
35     public boolean isFull() {
36         return (end + 1) % N == start;
37     }
38 
39     public int size() {
40         if (end > start) {
41             return end - start;
42         } else {
43             return N - start + end;
44         }
45     }
46 
47     public Integer peek() {
48         if (isEmpty()) {
49             throw new RuntimeException("Queue is empty");
50         }
51 
52         return array[start];
53     }
54 
55     public void enqueue(int item) {
56         if (isFull()) {
57             throw new RuntimeException("Queue is full");
58         }
59 
60         array[end] = item;
61         end = (end + 1) % N;
62     }
63 
64     public int dequeue() {
65         if (isEmpty()) {
66             throw new RuntimeException("Queue is empty");
67         }
68 
69         int temp = array[start];
70         start = (start + 1) % N;
71 
72         return temp;
73     }
74 
75     public static void main(String[] args) {
76         CircularQueue circularQueue = new CircularQueue(3);
77 //        1. 测试队列满
78 //        circularQueue.enqueue(1);
79 //        circularQueue.enqueue(2);
80 //        circularQueue.enqueue(3);
81 //        circularQueue.enqueue(4);
82 
83         circularQueue.enqueue(1);
84         circularQueue.enqueue(2);
85         circularQueue.enqueue(3);
86         System.out.println(circularQueue.size()); // 3
87         System.out.println(circularQueue.peek()); // 1
88         System.out.println(circularQueue.isFull()); // true
89         System.out.println(circularQueue.isEmpty()); // false
90         System.out.println(circularQueue.N); // 4
91 
92         System.out.println(circularQueue.dequeue());  // 1
93         System.out.println(circularQueue.dequeue());  // 2
94         System.out.println(circularQueue.dequeue());  // 3
95         System.out.println(circularQueue.dequeue());  // 报错 Queue is empty
96 
97     }
98 
99 }

输出：

3
1
true
false
4
1
2
3
Exception in thread "main" java.lang.RuntimeException: Queue is empty
	at org.allen.data.structure.queue.CircularQueue.dequeue(CircularQueue.java:66)
	at org.allen.data.structure.queue.CircularQueue.main(CircularQueue.java:95)
Disconnected from the target VM, address: '127.0.0.1:57545', transport: 'socket'

Python

 1 class MyCircularDeque:
 2     def __init__(self, k: int):
 3         self.capacity = k + 1  # 额外空出一个位置作为约定
 4         self.circularDeque = [0] * (k + 1)
 5         self.front = 0
 6         self.rear = 0
 7 
 8     def is_empty(self) -> bool:
 9         return self.front == self.rear
10 
11     def is_full(self) -> bool:
12         return (self.rear + 1) % self.capacity == self.front
13 
14     def insertFront(self, value: int) -> bool:
15         if self.is_full():
16             return False
17         self.front = (self.front - 1 + self.capacity) % self.capacity
18         self.circularDeque[self.front] = value
19         return True
20 
21     def insertLast(self, value: int) -> bool:
22         if self.is_full():
23             return False
24         self.circularDeque[self.rear] = value
25         self.rear = (self.rear + 1) % self.capacity
26         return True
27 
28     def deleteFront(self) -> bool:
29         if self.is_empty():
30             return False
31         self.front = (self.front + 1) % self.capacity
32         return True
33 
34     def deleteLast(self) -> bool:
35         if self.is_empty():
36             return False
37         self.rear = (self.rear - 1 + self.capacity) % self.capacity
38         return True
39 
40     def getFront(self) -> int:
41         if self.is_empty():
42             return -1
43         return self.circularDeque[self.front]
44 
45     def getRear(self) -> int:
46         if self.is_empty():
47             return -1
48         return self.circularDeque[self.rear - 1]