循环队列
此前,我们提供了一种简单但低效的队列实现。
更有效的方法是使用循环队列。 具体来说,我们可以使用固定大小的数组
和两个指针
来指示起始位置和结束位置。 目的是重用
我们之前提到的被浪费的存储
。
设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。你的实现应该支持如下操作:- MyCircularQueue(k): 构造器,设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空,返回 -1 。
- Rear: 获取队尾元素。如果队列为空,返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为3circularQueue.enQueue(1); // 返回truecircularQueue.enQueue(2); // 返回truecircularQueue.enQueue(3); // 返回truecircularQueue.enQueue(4); // 返回false,队列已满circularQueue.Rear(); // 返回3circularQueue.isFull(); // 返回truecircularQueue.deQueue(); // 返回truecircularQueue.enQueue(4); // 返回truecircularQueue.Rear(); // 返回4
提示:
- 所有的值都在 1 至 1000 的范围内;
- 操作数将在 1 至 1000 的范围内;
- 请不要使用内置的队列库。
循环队列 - 实现
在循环队列中,我们使用一个数组
和两个指针(head
和 tail
)。 head
表示队列的起始位置,tail
表示队列的结束位置。
这里我们提供了代码供你参考:
1 package queue; 2 3 public class Main2 { 4 public static void main(String[] args) { 5 /** 6 * Your MyCircularQueue object will be instantiated and called as such: 7 * MyCircularQueue obj = new MyCircularQueue(k); 8 * boolean param_1 = obj.enQueue(value); 9 * boolean param_2 = obj.deQueue(); 10 * int param_3 = obj.Front(); 11 * int param_4 = obj.Rear(); 12 * boolean param_5 = obj.isEmpty(); 13 * boolean param_6 = obj.isFull(); 14 */ 15 } 16 } 17 18 class MyCircularQueue { 19 20 private int[] data; 21 private int head; 22 private int tail; 23 private int size; 24 25 /** Initialize your data structure here. Set the size of the queue to be k. */ 26 //在这里初始化数据结构。将队列的大小设置为k. 27 public MyCircularQueue(int k) { 28 data = new int[k]; 29 head = -1; 30 tail = -1; 31 size = k; 32 } 33 34 /** Insert an element into the circular queue. Return true if the operation is successful. */ 35 //在循环队列中插入一个元素。如果操作成功,返回true。 36 public boolean enQueue(int value) { 37 if (isFull() == true) { 38 return false; 39 } 40 if (isEmpty() == true) { 41 head = 0; 42 } 43 tail = (tail + 1) % size; 44 data[tail] = value; 45 return true; 46 } 47 48 /** Delete an element from the circular queue. Return true if the operation is successful. */ 49 //从循环队列中删除一个元素。如果操作成功,返回true。 50 public boolean deQueue() { 51 if (isEmpty() == true) { 52 return false; 53 } 54 if (head == tail) { 55 head = -1; 56 tail = -1; 57 return true; 58 } 59 head = (head + 1) % size; 60 return true; 61 } 62 63 /** Get the front item from the queue. */ 64 //从队列中获取前面的项 65 public int Front() { 66 if (isEmpty() == true) { 67 return -1; 68 } 69 return data[head]; 70 } 71 72 /** Get the last item from the queue. */ 73 //从队列中获取最后一个条目。 74 public int Rear() { 75 if (isEmpty() == true) { 76 return -1; 77 } 78 return data[tail]; 79 } 80 81 /** Checks whether the circular queue is empty or not. */ 82 //检查循环队列是否为空。 83 public boolean isEmpty() { 84 return head == -1; 85 } 86 87 /** Checks whether the circular queue is full or not. */ 88 //检查循环队列是否已满。 89 public boolean isFull() { 90 return ((tail + 1) % size) == head; 91 } 92 } 93 94 /** 95 * Your MyCircularQueue object will be instantiated and called as such: 96 * MyCircularQueue obj = new MyCircularQueue(k); 97 * boolean param_1 = obj.enQueue(value); 98 * boolean param_2 = obj.deQueue(); 99 * int param_3 = obj.Front();100 * int param_4 = obj.Rear();101 * boolean param_5 = obj.isEmpty();102 * boolean param_6 = obj.isFull();103 */