要点
- 用数组和取模运算来模拟循环队列和循环双端队列
- 数组大小需要设置为数组真实长度+1，这是为了使得队满和队空的条件不同（区分作用）
- front指向的是真实存在的队头元素位置，rear指向的永远为待插入的元素位置（即rear永远指向空，获取队尾元素需要取rear指针前一位的数据）
- 队满的条件为
(rear + 1) % n == front - 队空的条件为
rear == front
循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
- MyCircularQueue(k): 构造器，设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空，返回 -1 。
- Rear: 获取队尾元素。如果队列为空，返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
Java代码
class MyCircularQueue {
int[] q;
int front = 0, rear = 0;
int n;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
q = new int[k+1];
n = k + 1;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if((rear + 1) % n == front) return false;
q[rear] = value;
rear = (rear + 1) % n;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if(front == rear) return false;
front = (front + 1) % n;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if(front == rear) return -1;
return q[front];
}
/** Get the last item from the queue. */
public int Rear() {
if(front == rear) return -1;
return q[(rear - 1 + n) % n];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return front == rear;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return (rear + 1) % n == front;
}
}
循环双端队列
设计实现双端队列。
你的实现需要支持以下操作：
- MyCircularDeque(k)：构造函数,双端队列的大小为k。
- insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
- insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
- deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
- deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
- getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
- getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
- isEmpty()：检查双端队列是否为空。
- isFull()：检查双端队列是否满了。
Java代码
class MyCircularDeque {
int[] q;
int n;
int front = 0, rear = 0;
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
n = k + 1;
q = new int[n];
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
if((rear + 1) % n == front) return false;
front = (front - 1 + n) % n;
q[front] = value;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
if((rear + 1) % n == front) return false;
q[rear] = value;
rear = (rear + 1) % n;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
if(front == rear) return false;
front = (front + 1) % n;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
if(front == rear) return false;
rear = (rear - 1 + n) % n;
return true;
}
/** Get the front item from the deque. */
public int getFront() {
if(front == rear) return -1;
return q[front];
}
/** Get the last item from the deque. */
public int getRear() {
if(front == rear) return -1;
return q[(rear - 1 + n) % n];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
return front == rear;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
return (rear + 1) % n == front;
}
}
