641. Design Circular Deque

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

• MyCircularDeque(int k) Initializes the deque with a maximum size of k.
• boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
• int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
• int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
• boolean isEmpty() Returns true if the deque is empty, or false otherwise.
• boolean isFull() Returns true if the deque is full, or false otherwise.

Example 1:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

Explanation
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // return True
myCircularDeque.insertLast(2);  // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear();      // return 2
myCircularDeque.isFull();       // return True
myCircularDeque.deleteLast();   // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront();     // return 4

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

Code

class MyCircularDeque {
    class Node {
        Node pre;
        Node next;
        int val;

        public Node(int v) {
            val = v;
        }
    }

    int currSize;
    int maxSize;
    Node head;
    Node tail;

    public MyCircularDeque(int k) {
        head = new Node(-1);
        tail = new Node(-1);
        head.pre = tail;
        tail.next = head;
        maxSize = k;
        currSize = 0;
    }

    public boolean insertFront(int value) {
        if (currSize == maxSize) return false;

        Node node = new Node(value);

        node.next = head;
        node.pre = head.pre;
        head.pre.next = node;
        head.pre = node;

        currSize++;
        return true;
    }

    public boolean insertLast(int value) {
        if (currSize == maxSize) return false;

        Node node = new Node(value);

        node.next = tail.next;
        tail.next.pre = node;
        tail.next = node;
        node.pre = tail;

        currSize++;
        return true;
    }

    public boolean deleteFront() {
        if (currSize == 0) return false;

        head.pre.pre.next = head;
        head.pre = head.pre.pre;
        currSize--;
        return true;
    }

    public boolean deleteLast() {
        if (currSize == 0) return false;

        tail.next.next.pre = tail;
        tail.next = tail.next.next;
        currSize--;
        return true;
    }

    public int getFront() {
        return head.pre.val;
    }

    public int getRear() {
        return tail.next.val;
    }

    public boolean isEmpty() {
        return currSize == 0;
    }

    public boolean isFull() {
        return currSize == maxSize;
    }
}