Design Circular Deque

Design and implement a circular deque using linked-list pointer manipulation, ensuring efficient insertion and deletion at both ends.

array linked list design queue

Problem Statement

You are tasked with designing a circular deque that supports insertion and deletion from both ends. The deque should be able to hold up to a specified size, k, and provide constant-time operations for these insertions and deletions.

You need to implement the MyCircularDeque class with the following methods: insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull. The goal is to use linked-list pointer manipulation for efficient operations while maintaining a circular structure.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 1000
0 <= value <= 1000
At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

Solution Approach

Efficient Circular Structure

A circular deque can be implemented using a doubly linked list, where each node points to the next and previous nodes. By maintaining pointers to both the front and rear ends, insertions and deletions at both ends of the deque can be performed in constant time, O(1).

Node Manipulation

The linked list approach involves manipulating the prev and next pointers during each operation. For instance, when inserting an element at the front, the new node’s next pointer is updated to the current front, and the current front’s prev pointer is updated to point to the new node.

Handling Overflow and Underflow

In a circular deque, managing overflow (deque is full) and underflow (deque is empty) conditions is crucial. The circular structure helps by wrapping around the ends of the deque when either insertion or deletion happens at the front or rear, ensuring efficient space utilization.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(k)

The time complexity for all operations in the MyCircularDeque class is O(1) because insertions and deletions at both ends only involve pointer manipulation. The space complexity is O(k), where k is the size of the deque, as the deque stores at most k elements at any time.

What Interviewers Usually Probe

The candidate should demonstrate knowledge of linked-list pointer manipulation, especially handling both ends of a deque.
Look for an understanding of circular structures and how they impact space and time complexity.
Candidates who can explain efficient handling of boundary conditions (overflow and underflow) will show solid problem-solving skills.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update both next and prev pointers correctly when inserting or deleting elements.
Not handling the circular nature of the deque properly, especially with the front and rear pointers.
Failing to efficiently manage the size of the deque, leading to overflow or underflow errors.

Follow-up variants

Implementing a deque using arrays or other data structures for comparison of space and time efficiency.
Designing a fixed-size deque with resizing capabilities when full or empty.
Optimizing memory usage by adjusting node structure or implementing a static array-based deque.

FAQ

What is the best approach for solving the Design Circular Deque problem?

Using a doubly linked list is the most efficient approach, allowing constant-time operations for insertion and deletion at both ends while maintaining a circular structure.

How do I handle the circular nature of the deque?

By keeping pointers to both the front and rear, and manipulating the prev and next pointers, you can ensure the circular structure is maintained during all operations.

What are the time and space complexities of the solution?

All operations in the MyCircularDeque class run in O(1) time, and the space complexity is O(k), where k is the size of the deque.

Can I implement the deque with an array instead of a linked list?

Yes, it is possible to implement a deque using an array, but it would require handling resizing when the deque is full, and it may not be as efficient as the linked-list approach for insertion and deletion at both ends.

What should I watch out for when implementing the Design Circular Deque problem?

Make sure you handle boundary conditions such as overflow and underflow properly, and ensure the circular structure is maintained by correctly updating the pointers during each operation.

terminal

Solution

Solution 1: Array

We can use an array to implement the circular deque. We maintain a pointer $\textit{front}$ pointing to the front of the queue, a variable $\textit{size}$ representing the number of elements in the queue, and a variable $\textit{capacity}$ representing the queue's capacity. We use an array $\textit{q}$ to store the elements.

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()

Continue Practicing

#622 design circular queue #705 design hashset #706 design hashmap