We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Circular Deque

Difficulty: Medium

Problem Description

Design your implementation of the circular double-ended queue (deque). Implement the MyCircularDeque class with the following methods:

  • MyCircularDeque(int k): Initializes the deque with a maximum size of k.
  • boolean insertFront(int value): Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean insertLast(int value): 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.

Key Insights

  • A circular deque allows efficient insertion and deletion from both ends.
  • We can use an array to implement the circular behavior by using modulo operations for the indices.
  • Keeping track of the size and the pointers (head and tail) is essential for maintaining the state of the deque.
  • Edge cases include handling full and empty states correctly.

Space and Time Complexity

Time Complexity:

  • O(1) for all operations (insertions, deletions, retrievals, checks).

Space Complexity:

  • O(k) where k is the maximum size of the deque (size of the underlying array).

Solution

To implement the circular deque, we can utilize a fixed-size array combined with two pointers (head and tail) to manage the front and rear of the deque. The pointers will wrap around using modulo operations to ensure the circular functionality. We also maintain a count of the current number of elements in the deque to facilitate the isEmpty and isFull checks.

Code Solutions

class MyCircularDeque:
    def __init__(self, k: int):
        self.size = k
        self.deque = [0] * k  # Initialize the deque with a fixed size
        self.head = 0  # Pointer to the front
        self.tail = 0  # Pointer to the rear
        self.count = 0  # Current number of elements

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.head = (self.head - 1) % self.size  # Move head pointer
        self.deque[self.head] = value  # Insert value at front
        self.count += 1  # Increase the count
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.deque[self.tail] = value  # Insert value at rear
        self.tail = (self.tail + 1) % self.size  # Move tail pointer
        self.count += 1  # Increase the count
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.size  # Move head pointer
        self.count -= 1  # Decrease the count
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.tail = (self.tail - 1 + self.size) % self.size  # Move tail pointer
        self.count -= 1  # Decrease the count
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[self.head]  # Return the front value

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[(self.tail - 1 + self.size) % self.size]  # Return the rear value

    def isEmpty(self) -> bool:
        return self.count == 0  # Check if the deque is empty

    def isFull(self) -> bool:
        return self.count == self.size  # Check if the deque is full
← Back to All Questions