Design a Circular Deque

December 29, 2023

Problem #

Design a circular deque (double-ended queue) with ‘addFront’, ‘addRear’, ‘deleteFront’, and ‘deleteRear’ operations. The circular deque should support these methods in O(1) time complexity.

Solution #

Here’s the Python code for the CircularDeque class:

class CircularDeque:
    def __init__(self, size):
        self.size = size
        self.count = 0
        self.front = -1
        self.rear = 0
        self.deque = [None] * size

    def isFull(self):
        return self.count == self.size

    def isEmpty(self):
        return self.count == 0

    def addFront(self, value):
        if self.isFull():
            return False
        if self.front == -1:
            self.front = self.rear = 0
        elif self.front == 0:
            self.front = self.size - 1
        else:
            self.front -= 1
        self.deque[self.front] = value
        self.count += 1
        return True

    def addRear(self, value):
        if self.isFull():
            return False
        if self.front == -1:
            self.front = self.rear = 0
        elif self.rear == self.size - 1:
            self.rear = 0
        else:
            self.rear += 1
        self.deque[self.rear] = value
        self.count += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False
        if self.front == self.rear:
            self.front = self.rear = -1
        elif self.front == self.size - 1:
            self.front = 0
        else:
            self.front += 1
        self.count -= 1
        return True

    def deleteRear(self):
        if self.isEmpty():
            return False
        if self.front == self.rear:
            self.front = self.rear = -1
        elif self.rear == 0:
            self.rear = self.size - 1
        else:
            self.rear -= 1
        self.count -= 1
        return True

    def getFront(self):
        if self.isEmpty():
            return -1
        return self.deque[self.front]

    def getRear(self):
        if self.isEmpty():
            return -1
        return self.deque[self.rear]

# Example usage
circularDeque = CircularDeque(5)
circularDeque.addFront(1)
circularDeque.addRear(2)
circularDeque.deleteFront()
circularDeque.deleteRear()
front = circularDeque.getFront()
rear = circularDeque.getRear()

This class initializes a circular deque with a specified size and provides the methods to add and remove elements from both ends efficiently. The getFront and getRear methods return the front and rear elements of the deque, respectively. The example usage demonstrates how to use these methods.

Solution Analysis #

The algorithm used in the provided code for the CircularDeque class is based on a circular buffer or ring buffer approach. This is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. The key characteristics of this algorithm are:

1. Fixed-Size Array: The deque is implemented using a fixed-size array. The size of this array is set during the initialization of the deque and remains constant.

2. Two Pointers (Front and Rear): The circular deque maintains two pointers, front and rear. These pointers are used to track the current positions at the front and rear ends of the deque, respectively.

3. Wrap-Around at Boundaries: When an element is added or removed, the pointers are adjusted. If a pointer reaches the end of the array, it wraps around to the beginning. This behavior is achieved using modulo arithmetic or conditional logic.

4. Constant Time Operations (O(1)): The operations addFront, addRear, deleteFront, and deleteRear are all designed to execute in constant time, regardless of the number of elements in the deque. This efficiency is due to the direct access nature of array indexing and the avoidance of any need to shift elements.

5. Check for Full and Empty States: Before adding or removing elements, the code checks whether the deque is full or empty, respectively. This is important for preventing overwriting of elements or attempting to remove elements from an empty deque.

This circular buffer approach is particularly efficient for implementing a deque where elements are frequently added and removed from both ends, as it ensures constant time operations without the need for dynamically resizing or shifting elements as in other data structures like linked lists.