641. Design Circular Deque
Problem Description
The given problem asks us to design a particular data structure known as a circular double-ended queue, often abbreviated as deque. A deque is a dynamic data structure that allows insertion and deletion of elements from both ends (front and back). The circular aspect of the queue implies that it is designed in such a way that the positions in the queue "wrap around" such that the last position is followed by the first, making the data structure continuous and circular.
Specifically, we need to implement a class MyCircularDeque
with the following operations and their respective constraints:
MyCircularDeque(int k)
- Constructor which initializes the deque with a fixed maximum sizek
.boolean insertFront(int value)
- Inserts an item at the front of the deque and returnstrue
if successful orfalse
if the deque is full.boolean insertLast(int value)
- Inserts an item at the rear of the deque and also returnstrue
if successful orfalse
if the deque is full.boolean deleteFront()
- Deletes an item from the front of the deque and returnstrue
if the operation is successful orfalse
if the deque is empty.boolean deleteLast()
- Deletes an item from the rear of the deque with the same return semantics asdeleteFront
.int getFront()
- Provides the front item from the deque, returning-1
if the deque is empty.int getRear()
- Provides the rear item from the deque, again returning-1
if the deque is empty.boolean isEmpty()
- Checks whether the deque is empty and returnstrue
if it is, orfalse
otherwise.boolean isFull()
- Checks if the deque is full, returningtrue
in such a case, orfalse
otherwise.
The challenge is to implement a deque that uses fixed-size storage but operates as if it were dynamic thanks to its circular nature.
Intuition
To implement the MyCircularDeque
, the solution should handle the "circular" part efficiently. Consequently, we use an array of size k
to represent the deque and two pointers, one for the front
of the deque and the other to keep track of the number of elements in the deque, referred to as size
. Since the deque is circular, we need a strategy to navigate circularly within the fixed-size list, which is accomplished by using modulo arithmetic when updating the front
pointer or calculating the index for insertions and deletions.
The intuition behind using modulo arithmetic is that when we reach the end of the array and need to wrap around to the beginning (or vice versa when going backwards), the modulo operation index % capacity
will give us the correct index within the bounds of our fixed-size array.
During insertion at the front, we adjust the front
index by subtracting one (to move to the front) and then use modulo to wrap around if necessary. Similarly, when inserting at the rear, we calculate the index based on front
and size
values. Deletion operations adjust the front
index or reduce the size
while avoiding underflow or overflow conditions.
For checking if the deque is full, we compare the size
with the capacity
. The deque is empty when size
is zero. Peek operations at the front or rear involve calculating the index based on the front
and size
and then accessing the array element at that index, taking care to return -1
when the deque is empty.
Learn more about Queue and Linked List patterns.
Solution Approach
The solution approach involves creating a fixed-size array and using two pointers ('front' and 'size') to efficiently manage the operations of the circular deque. Below is a detailed explanation of each operation implemented in MyCircularDeque
class:
-
Constructor (
__init__
): Initializes the deque with an array (self.q
) of sizek
,self.front
pointing to 0 (the initial position) andself.size
to track the current number of elements. Also,self.capacity
is set tok
to enforce the fixed size of the deque. -
Insert Front (
insertFront
): When a new element is to be inserted at the front, first check if the deque is full usingself.isFull()
. If not full:- Adjust the
front
pointer one step backward using modulo operation:self.front = (self.front - 1 + self.capacity) % self.capacity
. - Insert the new element at the
front
. - Increment
size
to reflect the addition.
- Adjust the
-
Insert Last (
insertLast
): To insert a new element at the rear, check if the deque is full. If there is space:- Calculate the new index for inserting the element at the rear using:
idx = (self.front + self.size) % self.capacity
. - Place the new element at the calculated
idx
. - Increase
size
accordingly.
- Calculate the new index for inserting the element at the rear using:
-
Delete Front (
deleteFront
): To delete the front element, first ensure that the deque is not empty by checkingself.isEmpty()
. If it contains elements:- Move the
front
pointer to the next element using the modulo operation:self.front = (self.front + 1) % self.capacity
. - Decrease
size
.
- Move the
-
Delete Last (
deleteLast
): To remove the element at the rear, first check if the deque is empty. If it has elements:- No need to move any pointers because the next insertLast will overwrite the last element.
- Simply decrement
size
.
-
Get Front (
getFront
): Returns the value at the front of the deque. If empty, return-1
. If not, returnself.q[self.front]
. -
Get Rear (
getRear
): Returns the last element of the deque. If empty, return-1
. If not, calculate the index of the rear element using:idx = (self.front + self.size - 1) % self.capacity
, and return the element at this index. -
Is Empty (
isEmpty
): A simple check comparingself.size
to 0 to determine if the deque is empty. -
Is Full (
isFull
): Check if the deque has reached its capacity by comparingself.size
withself.capacity
.
This implementation takes advantage of the modular arithmetic to wrap around the fixed-size array, thereby emulating a circular behavior. The array serves as the primary data structure, while the front and size pointers control access to the circular deque's elements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate how the MyCircularDeque
operates using the solution approach.
Suppose we initialize our circular deque with a maximum size of 3
.
-
Initialization:
MyCircularDeque circularDeque = new MyCircularDeque(3);
// set the size to be 3.- This creates an array
q
of size3
, setsfront
to0
,size
to0
, andcapacity
to3
.
-
Insert Last:
circularDeque.insertLast(1);
// returns true.- The rear index is calculated as
(front + size) % capacity
which translates to(0 + 0) % 3 = 0
. - The number 1 is inserted at index
0
. Thesize
is incremented to 1.
-
Insert Last:
circularDeque.insertLast(2);
// returns true.- The rear index is now
(0 + 1) % 3 = 1
. - The number 2 is inserted at index
1
. Thesize
is incremented to 2.
-
Insert Front:
circularDeque.insertFront(3);
// returns true.front
is adjusted backwards:(front - 1 + capacity) % capacity
which translates to(0 - 1 + 3) % 3 = 2
.- The number 3 is inserted at the new
front
which is index2
. Thesize
is incremented to 3.
-
Insert Front:
circularDeque.insertFront(4);
// returns false, the deque is full.- Since
size
equalscapacity
(3), no insertion is possible and operation returns false.
-
Get Rear:
circularDeque.getRear();
// returns 2.- The rear index is
(front + size - 1) % capacity
which is(2 + 3 - 1) % 3 = 1
. - Index
1
has the value2
, which is returned.
-
Is Full:
circularDeque.isFull();
// returns true.- This checks if
size
equalscapacity
which is3 == 3
, hence the deque is full.
-
Delete Last:
circularDeque.deleteLast();
// returns true.- Removes the last element which is
2
.size
is decremented to 2.
-
Insert Front:
circularDeque.insertFront(4);
// returns true.- Adjust
front
backward to index1
(newfront
after decrement is(2 - 1) % 3 = 1
). - Insert number
4
at index1
. Thesize
is incremented to 3.
-
Get Front:
circularDeque.getFront();
// returns 4.- Since our
front
is currently at1
, and that's where we inserted the value4
last,4
is what gets returned.
The above step-by-step operations show how each method manipulates the front
, size
, and sometimes the capacity
to perform their respective actions, while maintaining the integrity of a circular double-ended queue with fixed size. These examples also demonstrate how the operations are interdependent affecting the overall state of the queue.
Solution Implementation
1class MyCircularDeque:
2 def __init__(self, k: int):
3 """
4 Initialize the deque with a fixed size of 'k'.
5 """
6 self.queue = [0] * k
7 self.head = 0
8 self.size = 0
9 self.capacity = k
10
11 def insertFront(self, value: int) -> bool:
12 """
13 Add an item at the front of the deque.
14 Returns True if the operation is successful, otherwise False.
15 """
16 if self.isFull():
17 return False
18 if not self.isEmpty():
19 self.head = (self.head - 1 + self.capacity) % self.capacity
20 self.queue[self.head] = value
21 self.size += 1
22 return True
23
24 def insertLast(self, value: int) -> bool:
25 """
26 Add an item at the rear of the deque.
27 Returns True if the operation is successful, otherwise False.
28 """
29 if self.isFull():
30 return False
31 tail_index = (self.head + self.size) % self.capacity
32 self.queue[tail_index] = value
33 self.size += 1
34 return True
35
36 def deleteFront(self) -> bool:
37 """
38 Delete an item from the front of the deque.
39 Returns True if the operation is successful, otherwise False.
40 """
41 if self.isEmpty():
42 return False
43 self.head = (self.head + 1) % self.capacity
44 self.size -= 1
45 return True
46
47 def deleteLast(self) -> bool:
48 """
49 Delete an item from the rear of the deque.
50 Returns True if the operation is successful, otherwise False.
51 """
52 if self.isEmpty():
53 return False
54 self.size -= 1
55 return True
56
57 def getFront(self) -> int:
58 """
59 Get the front item from the deque.
60 Returns the front item, or -1 if the deque is empty.
61 """
62 if self.isEmpty():
63 return -1
64 return self.queue[self.head]
65
66 def getRear(self) -> int:
67 """
68 Get the last item from the deque.
69 Returns the last item, or -1 if the deque is empty.
70 """
71 if self.isEmpty():
72 return -1
73 tail_index = (self.head + self.size - 1) % self.capacity
74 return self.queue[tail_index]
75
76 def isEmpty(self) -> bool:
77 """
78 Check whether the deque is empty.
79 Returns True if the deque is empty, otherwise False.
80 """
81 return self.size == 0
82
83 def isFull(self) -> bool:
84 """
85 Check whether the deque is full.
86 Returns True if the deque is at full capacity, otherwise False.
87 """
88 return self.size == self.capacity
89
90# Example of how to use the MyCircularDeque class
91# circular_deque = MyCircularDeque(3)
92# print(circular_deque.insertLast(1)) # returns True
93# print(circular_deque.insertLast(2)) # returns True
94# print(circular_deque.insertFront(3)) # returns True
95# print(circular_deque.insertFront(4)) # returns False, the queue is full
96# print(circular_deque.getRear()) # returns 2
97# print(circular_deque.isFull()) # returns True
98# print(circular_deque.deleteLast()) # returns True
99# print(circular_deque.insertFront(4)) # returns True
100# print(circular_deque.getFront()) # returns 4
101
1class MyCircularDeque {
2 private int[] queue;
3 private int front;
4 private int size;
5 private int capacity;
6
7 /**
8 * Constructor to initialize the circular deque.
9 * @param k The capacity of the deque.
10 */
11 public MyCircularDeque(int k) {
12 queue = new int[k];
13 capacity = k;
14 front = 0;
15 size = 0;
16 }
17
18 /**
19 * Inserts an item at the front of the deque.
20 * @param value The value to insert.
21 * @return true if the operation is successful, false otherwise.
22 */
23 public boolean insertFront(int value) {
24 if (isFull()) {
25 return false;
26 }
27 front = (front - 1 + capacity) % capacity;
28 queue[front] = value;
29 size++;
30 return true;
31 }
32
33 /**
34 * Inserts an item at the rear of the deque.
35 * @param value The value to insert.
36 * @return true if the operation is successful, false otherwise.
37 */
38 public boolean insertLast(int value) {
39 if (isFull()) {
40 return false;
41 }
42 int rear = (front + size) % capacity;
43 queue[rear] = value;
44 size++;
45 return true;
46 }
47
48 /**
49 * Deletes an item from the front of the deque.
50 * @return true if the operation is successful, false otherwise.
51 */
52 public boolean deleteFront() {
53 if (isEmpty()) {
54 return false;
55 }
56 front = (front + 1) % capacity;
57 size--;
58 return true;
59 }
60
61 /**
62 * Deletes an item from the rear of the deque.
63 * @return true if the operation is successful, false otherwise.
64 */
65 public boolean deleteLast() {
66 if (isEmpty()) {
67 return false;
68 }
69 size--;
70 return true;
71 }
72
73 /**
74 * Gets the item from the front of the deque.
75 * @return The front item, or -1 if the deque is empty.
76 */
77 public int getFront() {
78 if (isEmpty()) {
79 return -1;
80 }
81 return queue[front];
82 }
83
84 /**
85 * Gets the item from the rear of the deque.
86 * @return The rear item, or -1 if the deque is empty.
87 */
88 public int getRear() {
89 if (isEmpty()) {
90 return -1;
91 }
92 int rear = (front + size - 1) % capacity;
93 return queue[rear];
94 }
95
96 /**
97 * Checks whether the circular deque is empty.
98 * @return true if the deque is empty, false otherwise.
99 */
100 public boolean isEmpty() {
101 return size == 0;
102 }
103
104 /**
105 * Checks whether the circular deque is full.
106 * @return true if the deque is full, false otherwise.
107 */
108 public boolean isFull() {
109 return size == capacity;
110 }
111}
112
1#include <vector>
2
3class MyCircularDeque {
4private:
5 std::vector<int> deque; // Underlying container for the deque elements
6 int frontIndex; // Index of the front element
7 int currentSize; // Current number of elements in the deque
8 int maxCapacity; // Maximum capacity of the deque
9
10public:
11 // Constructor to initialize the deque with a fixed capacity.
12 MyCircularDeque(int k) : frontIndex(0), currentSize(0), maxCapacity(k) {
13 deque.assign(k, 0); // Initialize deque with zeros, using the specified capacity.
14 }
15
16 // Inserts an element at the front of the deque. Returns true if the operation is successful.
17 bool insertFront(int value) {
18 if (isFull()) {
19 return false; // Cannot insert when the deque is full.
20 }
21 // When not empty, decrement frontIndex circularly.
22 if (!isEmpty()) {
23 frontIndex = (frontIndex - 1 + maxCapacity) % maxCapacity;
24 }
25 deque[frontIndex] = value; // Assign value to new front position.
26 ++currentSize; // Increment the size of the deque.
27 return true;
28 }
29
30 // Inserts an element at the rear of the deque. Returns true if the operation is successful.
31 bool insertLast(int value) {
32 if (isFull()) {
33 return false; // Cannot insert when the deque is full.
34 }
35 int rearIndex = (frontIndex + currentSize) % maxCapacity; // Calculate rear index.
36 deque[rearIndex] = value; // Assign value to the rear position.
37 ++currentSize; // Increment the size of the deque.
38 return true;
39 }
40
41 // Deletes an element from the front of the deque. Returns true if the operation is successful.
42 bool deleteFront() {
43 if (isEmpty()) {
44 return false; // Cannot delete when the deque is empty.
45 }
46 frontIndex = (frontIndex + 1) % maxCapacity; // Move front index forward circularly.
47 --currentSize; // Decrement the size of the deque.
48 return true;
49 }
50
51 // Deletes an element from the rear of the deque. Returns true if the operation is successful.
52 bool deleteLast() {
53 if (isEmpty()) {
54 return false; // Cannot delete when the deque is empty.
55 }
56 --currentSize; // Decrement the size of the deque. The rear element gets 'removed'.
57 return true;
58 }
59
60 // Gets the front item from the deque. Returns -1 if the deque is empty.
61 int getFront() {
62 return isEmpty() ? -1 : deque[frontIndex];
63 }
64
65 // Gets the last item from the deque. Returns -1 if the deque is empty.
66 int getRear() {
67 if (isEmpty()) {
68 return -1; // Return -1 when the deque is empty.
69 }
70 // Calculate the index of the last element and return the value.
71 int rearIndex = (frontIndex + currentSize - 1) % maxCapacity;
72 return deque[rearIndex];
73 }
74
75 // Checks whether the deque is empty.
76 bool isEmpty() {
77 return currentSize == 0;
78 }
79
80 // Checks whether the deque is full.
81 bool isFull() {
82 return currentSize == maxCapacity;
83 }
84};
85
86/**
87 * Usage of MyCircularDeque:
88 * MyCircularDeque* obj = new MyCircularDeque(k);
89 * bool param_1 = obj->insertFront(value);
90 * bool param_2 = obj->insertLast(value);
91 * bool param_3 = obj->deleteFront();
92 * bool param_4 = obj->deleteLast();
93 * int param_5 = obj->getFront();
94 * int param_6 = obj->getRear();
95 * bool param_7 = obj->isEmpty();
96 * bool param_8 = obj->isFull();
97 */
98
1const DEQUE_SIZE: number = 0;
2let deque_vals: number[] = [];
3let deque_start: number = 0;
4let deque_end: number = 0;
5let deque_length: number = 0;
6
7// Initializes the data structure with a maximum size 'k'.
8function initialize(k: number): void {
9 deque_vals = new Array(k).fill(0);
10 DEQUE_SIZE = k;
11 deque_start = 0;
12 deque_end = 0;
13 deque_length = 0;
14}
15
16// Inserts an element at the front of the deque. Returns true if the operation is successful.
17function insertFront(value: number): boolean {
18 if (isFull()) {
19 return false;
20 }
21 deque_start = deque_start === 0 ? DEQUE_SIZE - 1 : deque_start - 1;
22 deque_vals[deque_start] = value;
23 deque_length++;
24 return true;
25}
26
27// Inserts an element at the rear of the deque. Returns true if the operation is successful.
28function insertLast(value: number): boolean {
29 if (isFull()) {
30 return false;
31 }
32 deque_vals[deque_end] = value;
33 deque_end = (deque_end + 1) % DEQUE_SIZE;
34 deque_length++;
35 return true;
36}
37
38// Deletes an element from the front of the deque. Returns true if the operation is successful.
39function deleteFront(): boolean {
40 if (isEmpty()) {
41 return false;
42 }
43 deque_start = (deque_start + 1) % DEQUE_SIZE;
44 deque_length--;
45 return true;
46}
47
48// Deletes an element from the rear of the deque. Returns true if the operation is successful.
49function deleteLast(): boolean {
50 if (isEmpty()) {
51 return false;
52 }
53 deque_end = deque_end === 0 ? DEQUE_SIZE - 1 : deque_end - 1;
54 deque_length--;
55 return true;
56}
57
58// Gets the front item from the deque. Returns -1 if the deque is empty.
59function getFront(): number {
60 if (isEmpty()) {
61 return -1;
62 }
63 return deque_vals[deque_start];
64}
65
66// Gets the last item from the deque. Returns -1 if the deque is empty.
67function getRear(): number {
68 if (isEmpty()) {
69 return -1;
70 }
71 let last_index = deque_end === 0 ? DEQUE_SIZE - 1 : deque_end - 1;
72 return deque_vals[last_index];
73}
74
75// Checks whether the deque is empty or not.
76function isEmpty(): boolean {
77 return deque_length === 0;
78}
79
80// Checks whether the deque is full or not.
81function isFull(): boolean {
82 return deque_length === DEQUE_SIZE;
83}
84
Time and Space Complexity
Time Complexity
__init__(k: int)
: The initialization of the deque takesO(k)
time since it initializes a list of sizek
with zeros.insertFront(value: int) -> bool
: Inserting an item at the front takesO(1)
time as it is done by updating an index and inserting the value.insertLast(value: int) -> bool
: Inserting an item at the rear is also done inO(1)
time, which involves calculating the index and inserting the value.deleteFront() -> bool
: Deleting an item from the front takesO(1)
time due to the update of thefront
index and decreasing the size.deleteLast() -> bool
: Deleting an item from the rear takesO(1)
time since it only involves decrementing the size.getFront() -> int
: Retrieving the front item isO(1)
because it simply accesses the element at thefront
index.getRear() -> int
: Retrieving the rear item isO(1)
by calculating the index of the last item based onfront
andsize
and then accessing it.isEmpty() -> bool
: Checking if the deque is empty takesO(1)
time as it checks if the size is0
.isFull() -> bool
: Checking if the deque is full also takesO(1)
time by comparingsize
andcapacity
.
All operations of the deque are implemented in a way that ensures a constant time complexity.
Space Complexity
- The overall space complexity for the deque is
O(k)
, which is required for storing the elements of the deque. The variablesfront
,size
, andcapacity
use constant additional space, hence they do not affect the overall space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.