Build a circular deque (a double-ended queue). You can add and remove numbers at both the front and the back. It has a fixed size, and the last place is joined to the first place to make a circle.
Write a class MyCircularDeque with these methods:
MyCircularDeque(k): create a deque that holds at most k numbers.insertFront(value): add value at the front. Return true if it was added, or false if the deque is full.insertLast(value): add value at the back. Return true if it was added, or false if the deque is full.deleteFront(): remove the number at the front. Return true if one was removed, or false if the deque is empty.deleteLast(): remove the number at the back. Return true if one was removed, or false if the deque is empty.getFront(): return the number at the front, or -1 if the deque is empty.getRear(): return the number at the back, or -1 if the deque is empty.isEmpty(): return true if the deque has no numbers.isFull(): return true if the deque already holds k numbers.
Examples
Example 1:
Input
["MyCircularDeque", "insertLast", "insertFront", "insertFront", "isFull", "getFront", "getRear", "deleteFront", "deleteLast", "isEmpty", "getFront"]
[[2], [5], [8], [9], [], [], [], [], [], [], []]
Output
[null, true, true, false, true, 8, 5, true, true, true, -1]
Explanation
The deque holds at most 2 numbers.
insertLast(5) gives [5]. insertFront(8) gives [8, 5].
insertFront(9) returns false because the deque is full.
getFront() returns 8 and getRear() returns 5.
deleteFront() and deleteLast() remove both numbers, so isEmpty() is true.
getFront() now returns -1.
Example 2:
Input
["MyCircularDeque", "insertLast", "insertLast", "deleteFront", "insertFront", "getFront", "getRear"]
[[3], [1], [2], [], [7], [], []]
Output
[null, true, true, true, true, 7, 2]
Explanation
insertLast(1) and insertLast(2) give [1, 2].
deleteFront() removes 1, leaving [2].
insertFront(7) gives [7, 2]. So getFront() is 7 and getRear() is 2.