A circular deque (double-ended queue) is a deque data structure that supports various operations to insert and delete elements from both ends. Implement the 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 the Deque. If the deque is empty, return -1
.isEmpty()
: Checks whether the circular deque is empty or not.isFull()
: Checks whether the circular deque is full or not.k
(the size of the deque)?front
and last
) to manage the insertion and deletion at both ends.insertFront
, insertLast
, deleteFront
, deleteLast
, getFront
, getRear
, isEmpty
, isFull
) would be O(1) since accessing or modifying elements in the array and updating indexes are constant time operations.Let’s write the code:
class MyCircularDeque:
def __init__(self, k: int):
self.deque = [0] * k
self.size = 0
self.capacity = k
self.front = 0
self.rear = -1
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
self.front = (self.front - 1) % self.capacity
self.deque[self.front] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
self.rear = (self.rear + 1) % self.capacity
self.deque[self.rear] = value
self.size += 1
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.rear = (self.rear - 1) % self.capacity
self.size -= 1
return True
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.deque[self.front]
def getRear(self) -> int:
if self.isEmpty():
return -1
return self.deque[self.rear]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
# Example usage:
# circularDeque = MyCircularDeque(3)
# print(circularDeque.insertLast(1)) # return True
# print(circularDeque.insertLast(2)) # return True
# print(circularDeque.insertFront(3)) # return True
# print(circularDeque.insertFront(4)) # return False, the queue is full
# print(circularDeque.getRear()) # return 2
# print(circularDeque.isFull()) # return True
# print(circularDeque.deleteLast()) # return True
# print(circularDeque.insertFront(4)) # return True
# print(circularDeque.getFront()) # return 4
This implementation maintains efficient operations with O(1) time complexity for insertion, deletion, and access operations in the deque.
Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?