Design Circular Queue II

LeetCode Q 641 - Design Circular Queue II

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

Your implementation should support following operations:

• MyCircularDeque(k): Constructor, set the size of the deque to be k.
• insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
• insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
• deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
• deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
• getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
• getRear(): Gets the last item from Deque. If the deque is empty, return -1.
• isEmpty(): Checks whether Deque is empty or not.
• isFull(): Checks whether Deque is full or not.

Example:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1); // return true
circularDeque.insertLast(2); // return true
circularDeque.insertFront(3); // return true
circularDeque.insertFront(4); // return false, the queue is full
circularDeque.getRear(); // return 2
circularDeque.isFull(); // return true
circularDeque.deleteLast(); // return true
circularDeque.insertFront(4); // return true
circularDeque.getFront(); // return 4

Note:

• All values will be in the range of [0, 1000].
• The number of operations will be in the range of [1, 1000].
• Please do not use the built-in Deque library.

Solution: Doubly-Linked List

Code:

class MyCircularDeque {

	class Node {
		int val;
		Node prev, next;
		public Node (int val) { this.val = val; }
	}

	private Node head, tail;
	private int len, size;

	/ ** Initialize your data structure here. Set the size of the deque to be k. * /
	public MyCircularDeque(int k) {
		size = k; len = 0;
		head = new Node(-1); tail = new Node(-1);
		head.next = tail; head.prev = null;
		tail.prev = head; tail.next = null;
	}

	/ ** Adds an item at the front of Deque. Return true if the operation is successful. * /
	public boolean insertFront(int value) {
		if (isFull()) return false;
		
		len++;
		
		Node node = new Node(value);
		node.next = head.next; node.prev = head;
		head.next.prev = node; head.next = node;
		
		return true;
	}

	/ ** Adds an item at the rear of Deque. Return true if the operation is successful. * /
	public boolean insertLast(int value) {
		if (isFull()) return false;
		
		len++;
		
		Node node = new Node(value);
		node.next = tail; node.prev = tail.prev;
		tail.prev.next = node; tail.prev = node;
		
		return true;
	}

	/ ** Deletes an item from the front of Deque. Return true if the operation is successful. * /
	public boolean deleteFront() {
		if (isEmpty()) return false;
		
		len--;
		
		head.next.next.prev = head;
		head.next = head.next.next;
		
		return true;
	}

	/ ** Deletes an item from the rear of Deque. Return true if the operation is successful. * /
	public boolean deleteLast() {
		if (isEmpty()) return false;
		
		len--;
		
		tail.prev.prev.next = tail;
		tail.prev = tail.prev.prev;
		
		return true;
	}

	/ ** Get the front item from the deque. * /
	public int getFront() {
		return isEmpty() ? -1 : head.next.val;
	}

	/ ** Get the last item from the deque. * /
	public int getRear() {
		return isEmpty() ? -1 : tail.prev.val;
	}

	/ ** Checks whether the circular deque is empty or not. * /
	public boolean isEmpty() {
		return len == 0;
	}

	/ ** Checks whether the circular deque is full or not. * /
	public boolean isFull() {
		return len == size;
	}
}