Description
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 <= 10000 <= value <= 1000- At most
2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.
Solutions
Solution 1: Array
We can use an array to implement the circular deque. We maintain a pointer front pointing to the front of the queue, a variable size representing the number of elements in the queue, and a variable capacity representing the queue's capacity. We use an array q to store the elements.
When insertFront is called, we first check if the queue is full; if so, return false. Otherwise, we move front one position forward (using modular arithmetic for circular wrapping), insert the new element at front, and increment size by 1.
When insertLast is called, we first check if the queue is full; if so, return false. Otherwise, we compute the insertion position (using front and size), insert the new element there, and increment size by 1.
When deleteFront is called, we first check if the queue is empty; if so, return false. Otherwise, we move front one position backward (using modular arithmetic for circular wrapping) and decrement size by 1.
When deleteLast is called, we first check if the queue is empty; if so, return false. Otherwise, we decrement size by 1.
When getFront is called, we first check if the queue is empty; if so, return -1. Otherwise, we return q[front].
When getRear is called, we first check if the queue is empty; if so, return -1. Otherwise, we compute the position of the rear element (using front and size) and return the element at that position.
When isEmpty is called, we check whether size equals 0.
When isFull is called, we check whether size equals capacity.
All operations above have a time complexity of O(1) and a space complexity of O(k), where k is the capacity of the deque.
PythonJavaC++GoTypeScript
class MyCircularDeque:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the deque to be k.
"""
self.q = [0] * k
self.front = 0
self.size = 0
self.capacity = k
def insertFront(self, value: int) -> bool:
"""
Adds an item at the front of Deque. Return true if the operation is successful.
"""
if self.isFull():
return False
if not self.isEmpty():
self.front = (self.front - 1 + self.capacity) % self.capacity
self.q[self.front] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
"""
Adds an item at the rear of Deque. Return true if the operation is successful.
"""
if self.isFull():
return False
idx = (self.front + self.size) % self.capacity
self.q[idx] = value
self.size += 1
return True
def deleteFront(self) -> bool:
"""
Deletes an item from the front of Deque. Return true if the operation is successful.
"""
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def deleteLast(self) -> bool:
"""
Deletes an item from the rear of Deque. Return true if the operation is successful.
"""
if self.isEmpty():
return False
self.size -= 1
return True
def getFront(self) -> int:
"""
Get the front item from the deque.
"""
if self.isEmpty():
return -1
return self.q[self.front]
def getRear(self) -> int:
"""
Get the last item from the deque.
"""
if self.isEmpty():
return -1
idx = (self.front + self.size - 1) % self.capacity
return self.q[idx]
def isEmpty(self) -> bool:
"""
Checks whether the circular deque is empty or not.
"""
return self.size == 0
def isFull(self) -> bool:
"""
Checks whether the circular deque is full or not.
"""
return self.size == self.capacity
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()(code-box)
class MyCircularDeque {
private int[] q;
private int front;
private int size;
private int capacity;
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
q = new int[k];
capacity = k;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
if (!isEmpty()) {
front = (front - 1 + capacity) % capacity;
}
q[front] = value;
++size;
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;
}
int idx = (front + size) % capacity;
q[idx] = value;
++size;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
--size;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
--size;
return true;
}
/** Get the front item from the deque. */
public int getFront() {
if (isEmpty()) {
return -1;
}
return q[front];
}
/** Get the last item from the deque. */
public int getRear() {
if (isEmpty()) {
return -1;
}
int idx = (front + size - 1) % capacity;
return q[idx];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
return size == 0;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
return size == capacity;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/(code-box)
class MyCircularDeque {
public:
vector<int> q;
int front = 0;
int size = 0;
int capacity = 0;
MyCircularDeque(int k) {
q.assign(k, 0);
capacity = k;
}
bool insertFront(int value) {
if (isFull()) {
return false;
}
if (!isEmpty()) {
front = (front - 1 + capacity) % capacity;
}
q[front] = value;
++size;
return true;
}
bool insertLast(int value) {
if (isFull()) {
return false;
}
int idx = (front + size) % capacity;
q[idx] = value;
++size;
return true;
}
bool deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
--size;
return true;
}
bool deleteLast() {
if (isEmpty()) {
return false;
}
--size;
return true;
}
int getFront() {
return isEmpty() ? -1 : q[front];
}
int getRear() {
return isEmpty() ? -1 : q[(front + size - 1) % capacity];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/(code-box)
type MyCircularDeque struct {
q []int
size int
front int
capacity int
}
func Constructor(k int) MyCircularDeque {
q := make([]int, k)
return MyCircularDeque{q, 0, 0, k}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.IsFull() {
return false
}
if !this.IsEmpty() {
this.front = (this.front - 1 + this.capacity) % this.capacity
}
this.q[this.front] = value
this.size++
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.IsFull() {
return false
}
idx := (this.front + this.size) % this.capacity
this.q[idx] = value
this.size++
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if this.IsEmpty() {
return false
}
this.front = (this.front + 1) % this.capacity
this.size -= 1
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if this.IsEmpty() {
return false
}
this.size -= 1
return true
}
func (this *MyCircularDeque) GetFront() int {
if this.IsEmpty() {
return -1
}
return this.q[this.front]
}
func (this *MyCircularDeque) GetRear() int {
if this.IsEmpty() {
return -1
}
return this.q[(this.front+this.size-1)%this.capacity]
}
func (this *MyCircularDeque) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularDeque) IsFull() bool {
return this.size == this.capacity
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.InsertFront(value);
* param_2 := obj.InsertLast(value);
* param_3 := obj.DeleteFront();
* param_4 := obj.DeleteLast();
* param_5 := obj.GetFront();
* param_6 := obj.GetRear();
* param_7 := obj.IsEmpty();
* param_8 := obj.IsFull();
*/(code-box)
class MyCircularDeque {
private vals: number[];
private length: number;
private size: number;
private start: number;
private end: number;
constructor(k: number) {
this.vals = new Array(k).fill(0);
this.start = 0;
this.end = 0;
this.length = 0;
this.size = k;
}
insertFront(value: number): boolean {
if (this.isFull()) {
return false;
}
if (this.start === 0) {
this.start = this.size - 1;
} else {
this.start--;
}
this.vals[this.start] = value;
this.length++;
return true;
}
insertLast(value: number): boolean {
if (this.isFull()) {
return false;
}
this.vals[this.end] = value;
this.length++;
if (this.end + 1 === this.size) {
this.end = 0;
} else {
this.end++;
}
return true;
}
deleteFront(): boolean {
if (this.isEmpty()) {
return false;
}
if (this.start + 1 === this.size) {
this.start = 0;
} else {
this.start++;
}
this.length--;
return true;
}
deleteLast(): boolean {
if (this.isEmpty()) {
return false;
}
if (this.end === 0) {
this.end = this.size - 1;
} else {
this.end--;
}
this.length--;
return true;
}
getFront(): number {
if (this.isEmpty()) {
return -1;
}
return this.vals[this.start];
}
getRear(): number {
if (this.isEmpty()) {
return -1;
}
if (this.end === 0) {
return this.vals[this.size - 1];
}
return this.vals[this.end - 1];
}
isEmpty(): boolean {
return this.length === 0;
}
isFull(): boolean {
return this.length === this.size;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* var obj = new MyCircularDeque(k)
* var param_1 = obj.insertFront(value)
* var param_2 = obj.insertLast(value)
* var param_3 = obj.deleteFront()
* var param_4 = obj.deleteLast()
* var param_5 = obj.getFront()
* var param_6 = obj.getRear()
* var param_7 = obj.isEmpty()
* var param_8 = obj.isFull()
*/(code-box)
