Formatted question description: https://leetcode.ca/all/641.html

# 641. Design Circular Deque

Medium

## Description

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

queue vs deque. Reference: https://www.quora.com/What-is-the-difference-between-queue-and-deque

Queue is who ever gets in first gets out first i.e First In First Out(FIFO). like a line in front of a super market counter. It is used when there is a single resource(cashier) who has to do the tasks(billing) of all the requests(shoppers in line who want to get the items billed)

Deque(pronounced as deck) is double ended queue i.e the elements can be added or removed at either end of the line. It is used in situations when there are multiple requests(customers who want their items to be billed) but the contract is such that as soon as the cashier from other counter completes all the requests he can take over the left over requests(customers) from the opposite end of the line. This helps to use up the resource efficiently and requests are cleared at a faster rate.

Use an array to act as a deque and store the elements. Besides the array that is a data field of the class MyCircularDeque, the other data fields include capacity which is the capacity of the deque, start and end which are the indices of the first element and the last element, and size which is the number of elements in the deque.

For the constructor, given capacity k, initialize the array to be an array of length k and filled with -1, set capacity = k, and set start, end and size to 0.

For method insertFront, return false if the deque is full (checked by calling isFull). If size == 0, then set both start to end to 0. Otherwise, move front one step backward (note that the deque is circular, so if start was previously 0, then end will become capacity - 1 after moving one step backward). Set the element at index start in the array to be the given value, increase size by 1, and return true.

For method insertLast, return false if the deque is full (checked by calling isFull). If size == 0, then set both start to end to 0. Otherwise, move end one step forward (note that the deque is circular, so if end was previously capacity - 1, then end will become 0 after moving one step forward). Set the element at index end in the array to be the given value, increase size by 1, and return true.

For method deleteFront, return false if the deque is empty (checked by calling isEmpty). Set the element at index start to -1, move start one step forward (note that the deque is circular, so if start was previously capacity - 1, then start will become 0 after moving one step forward), decrease size by 1, and return true.

For method deleteLast, return false if the deque is empty (checked by calling isEmpty). Set the element at index end to -1, move end one step backward (note that the deque is circular, so if end was previously 0, then end will become capacity - 1 after moving one step backward), decrease size by 1, and return true.

For method getFront, return the element at index start.

For method getRear, return the element at index end.

For method isEmpty, return true if and only if size == 0.

For method isFull, return true if and only if size == capacity.