题目描述
题目
双向链表实现
由于双端队列的操作都在队头和队尾进行，因此可以使用双向链表，对头结点和尾结点进行操作。
双向链表实现双端队列
class MyCircularDeque1 {
public Deque<Integer> deque = new LinkedList<>();
public int size;
public int limit;
public MyCircularDeque1(int k) {
size = 0;
limit = k;
}
//头部添加元素
public boolean insertFront(int value) {
if (isFull()) {
return false;
} else {
deque.offerFirst(value);
size++;
return true;
}
}
//尾部添加元素
public boolean insertLast(int value) {
if (isFull()) {
return false;
} else {
deque.offerLast(value);
size++;
return true;
}
}
//头部删除元素
public boolean deleteFront() {
if (isEmpty()) {
return false;
} else {
size--;
deque.pollFirst();
return true;
}
}
//尾部删除元素
public boolean deleteLast() {
if (isEmpty()) {
return false;
} else {
size--;
deque.pollLast();
return true;
}
}
//获取头部元素
public int getFront() {
if (isEmpty()) {
return -1;
} else {
return deque.peekFirst();
}
}
//获取尾部元素
public int getRear() {
if (isEmpty()) {
return -1;
} else {
return deque.peekLast();
}
}
//判空
public boolean isEmpty() {
return size == 0;
}
//判满
public boolean isFull() {
return size == limit;
}
}
数组实现
也可通过数组来实现，定义一个size变量来限制队列中同时可存在的最多元素，定义一个头指针和一个尾指针，添加和删除元素都在头指针和尾指针处进行。
数组实现双端队列
头尾指针移动情况
class MyCircularDeque2 {
public int[] deque;
public int l, r, size, limit;
public MyCircularDeque2(int k) {
deque = new int[k];
l = r = size = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
} else {
if (isEmpty()) {
l = r = 0;
deque[0] = value;
} else {
l = l == 0 ? (limit - 1) : (l - 1);
deque[l] = value;
}
size++;
return true;
}
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
} else {
if (isEmpty()) {
l = r = 0;
deque[0] = value;
} else {
r = r == limit - 1 ? 0 : (r + 1);
deque[r] = value;
}
size++;
return true;
}
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
} else {
l = (l == limit - 1) ? 0 : (l + 1);
size--;
return true;
}
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
} else {
r = r == 0 ? (limit - 1) : (r - 1);
size--;
return true;
}
}
public int getFront() {
if (isEmpty()) {
return -1;
} else {
return deque[l];
}
}
public int getRear() {
if (isEmpty()) {
return -1;
} else {
return deque[r];
}
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
思考
看到评论区有同学问了个问题，我也思考了一下
问题
