链表还是好写一点, 不用考虑边界问题
为了写着舒服, 在双向链表的首尾可以都设一个不存放数据的哑结点(dummy node)
class MyCircularDeque {
private static class node {
int val;
node next, last;
public node(int val) {
this.val = val;
next = last = null;
}
}
private final node head, tail;
private int size;
private final int capacity;
public MyCircularDeque(int k) {
size = 0;
capacity = k;
head = new node(-1);
tail = new node(-1);
head.next = tail;
tail.last = head;
}
public boolean insertFront(int value) {
if(isFull()) {
return false;
}
size++;
node t = new node(value);
head.next.last = t;
t.next = head.next;
t.last = head;
head.next = t;
return true;
}
public boolean insertLast(int value) {
if(isFull()) {
return false;
}
size++;
node t = new node(value);
tail.last.next = t;
t.last = tail.last;
t.next = tail;
tail.last = t;
return true;
}
public boolean deleteFront() {
if(isEmpty()) {
return false;
}
size--;
head.next = head.next.next;
head.next.last = head;
return true;
}
public boolean deleteLast() {
if(isEmpty()) {
return false;
}
size--;
tail.last = tail.last.last;
tail.last.next = tail;
return true;
}
public int getFront() {
return size == 0 ? -1 : head.next.val;
}
public int getRear() {
return size == 0 ? -1 : tail.last.val;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}