Design Circular Deque - Leetcode Solution

Problem Statement:

Design your implementation of the circular double-ended queue (deque).

Your implementation should support 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 Deque. If the deque is empty, return -1.
• isEmpty(): Checks whether Deque is empty or not.
• isFull(): Checks whether Deque is full or not.

Solution:

We can implement the circular deque using an array and two pointers, front and rear. front will point to the first element of the deque and rear will point to the last element of the deque. The array will be of size k+1, where k is the size of the deque. We need to add an extra space in the array to accommodate the circular behavior of deque.

Initially, we will set front and rear to 0. front will point to the first index of the array and rear will point to the last index of the array. We will also maintain the count of elements in the deque as size.

We can implement the insert and delete operations as below:

1. insertFront(): If deque is not full, insert the element at front of the array and increment front by 1. If deque is already full, return False.

2. insertLast(): If deque is not full, insert the element at rear of the array and decrement rear by 1. If deque is already full, return False.

3. deleteFront(): If deque is not empty, delete the element at front of the array and increment front by 1. If deque is already empty, return False.

4. deleteLast(): If deque is not empty, delete the element at rear of the array and decrement rear by 1. If deque is already empty, return False.

5. getFront(): If deque is not empty, return the element at front of the array. If deque is empty, return -1.

6. getRear(): If deque is not empty, return the element at rear of the array. If deque is empty, return -1.

7. isEmpty(): Check if front and rear are equal. If yes, deque is empty, return True. Otherwise, return False.

8. isFull(): Check if front and rear are adjacent indices (i.e. front + 1 = rear or front - 1 = rear depending on the direction of traversal). If yes, deque is full, return True. Otherwise, return False.

Below is the python implementation of the circular deque using the above approach:

class MyCircularDeque(object):

    def __init__(self, k):
        self.size = 0
        self.k = k
        self.front = 0
        self.rear = k - 1
        self.arr = [None] * (self.k + 1)

    def insertFront(self, value):
        if not self.isFull():
            self.front = (self.front - 1) % (self.k + 1)
            self.arr[self.front] = value
            self.size += 1
            return True
        else:
            return False

    def insertLast(self, value):
        if not self.isFull():
            self.rear = (self.rear + 1) % (self.k + 1)
            self.arr[self.rear] = value
            self.size += 1
            return True
        else:
            return False

    def deleteFront(self):
        if not self.isEmpty():
            self.front = (self.front + 1) % (self.k + 1)
            self.size -= 1
            return True
        else:
            return False

    def deleteLast(self):
        if not self.isEmpty():
            self.rear = (self.rear - 1) % (self.k + 1)
            self.size -= 1
            return True
        else:
            return False

    def getFront(self):
        if not self.isEmpty():
            return self.arr[self.front]
        else:
            return -1

    def getRear(self):
        if not self.isEmpty():
            return self.arr[self.rear]
        else:
            return -1

    def isEmpty(self):
        return self.front == (self.rear + 1) % (self.k + 1)

    def isFull(self):
        return self.front == (self.rear + 2) % (self.k + 1)

Time Complexity:

• Insertion, deletion and retrieval operations take O(1) time complexity since they access the array by constant indices.

Space Complexity:

• Space complexity is O(k) where k is the size of dequeue.

1