641. Design Circular Deque #

题目 #

设计实现双端队列。

实现 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 。

思路 #

代码 #

class MyCircularDeque {

    private class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        ListNode (int value, ListNode prev, ListNode next) {
            this.val = value;
            this.prev = prev;
            this.next = next;
        }
    }

    private int size;
    private int capacity;
    private ListNode sentinel;

    public MyCircularDeque(int k) {
        this.size = 0;
        this.capacity = k;
        this.sentinel = new ListNode(-1, null, null);
        this.sentinel.prev = this.sentinel.next = this.sentinel;
    }
    
    public boolean insertFront(int value) {
        if (this.isFull()) return false;
        this.sentinel.next = new ListNode(value, this.sentinel, this.sentinel.next);
        this.sentinel.next.next.prev = this.sentinel.next;
        this.size += 1;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (this.isFull()) return false;
        this.sentinel.prev = new ListNode(value, this.sentinel.prev, this.sentinel);
        this.sentinel.prev.prev.next = this.sentinel.prev;
        this.size += 1;
        return true;
    }
    
    public boolean deleteFront() {
        if (this.isEmpty()) return false;
        this.sentinel.next = this.sentinel.next.next;
        this.sentinel.next.prev = this.sentinel;
        this.size -= 1;
        return true;
    }
    
    public boolean deleteLast() {
        if (this.isEmpty()) return false;
        this.sentinel.prev = this.sentinel.prev.prev;
        this.sentinel.prev.next = this.sentinel;
        this.size -= 1;
        return true;
    }
    
    public int getFront() {
        if (this.isEmpty()) return -1;
        return this.sentinel.next.val;
    }
    
    public int getRear() {
        if (this.isEmpty()) return -1;
        return this.sentinel.prev.val;
    }
    
    public boolean isEmpty() {
        return this.size == 0;
    }
    
    public boolean isFull() {
        return this.size == this.capacity;
    }
}