设计循环双端队列
设计循环双端队列
设计实现双端队列。实现 MyCircularDeque 类:
- MyCircularDeque(int k) :构造函数,双端队列最大为 k 。
- boolean insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true ,否则返回 false 。
- boolean insertLast() :将一个元素添加到双端队列尾部。如果操作成功返回 true ,否则返回 false 。
- boolean deleteFront() :从双端队列头部删除一个元素。 如果操作成功返回 true ,否则返回 false 。
- boolean deleteLast() :从双端队列尾部删除一个元素。如果操作成功返回 true ,否则返回 false 。
- int getFront() ):从双端队列头部获得一个元素。如果双端队列为空,返回 -1 。
- int getRear() :获得双端队列的最后一个元素。 如果双端队列为空,返回 -1 。
- boolean isEmpty() :若双端队列为空,则返回 true ,否则返回 false 。
- boolean isFull() :若双端队列满了,则返回 true ,否则返回 false 。
public class MyCircularDeque {
private int[] arr = null;
int size = 0;
int l = 0;
int r = 0;
/**
* 构造函数,双端队列最大为 k
*/
public MyCircularDeque(int k) {
arr = new int[k];
}
/**
* 将一个元素添加到双端队列头部。 如果操作成功返回 true ,否则返回 false
*/
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
if (l == 0) {
l = arr.length - 1;
} else {
l = l - 1;
}
arr[l] = value;
size++;
return true;
}
/**
* 将一个元素添加到双端队列尾部。如果操作成功返回 true ,否则返回 false 。
*/
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
arr[r] = value;
size++;
if (r == (arr.length - 1)) {
r = 0;
} else {
r = r + 1;
}
return true;
}
/**
* 从双端队列头部删除一个元素。 如果操作成功返回 true ,否则返回 false 。
*/
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
if (l == (arr.length - 1)) {
l = 0;
} else {
l = l + 1;
}
size--;
return true;
}
/**
* 从双端队列尾部删除一个元素。如果操作成功返回 true ,否则返回 false 。
*/
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
if (r == 0) {
r = arr.length - 1;
} else {
r = r - 1;
}
size--;
return true;
}
/**
* 从双端队列头部获得一个元素。如果双端队列为空,返回 -1 。
*/
public int getFront() {
if (isEmpty()) {
return -1;
}
return arr[l];
}
/**
* 获得双端队列的最后一个元素。 如果双端队列为空,返回 -1 。
*/
public int getRear() {
if (isEmpty()) {
return -1;
}
if (r == 0) {
return arr[arr.length - 1];
}
return arr[r - 1];
}
/**
* 若双端队列为空,则返回 true ,否则返回 false
*/
public boolean isEmpty() {
return size == 0 ? true : false;
}
/**
* 若双端队列满了,则返回 true ,否则返回 false 。
*/
public boolean isFull() {
return size == arr.length ? true : false;
}
}