Design Circular Deque

class CircularDeque {
private:
    vector<int> deque;
    int head;
    int tail;
    int count;
    int maxCapacity;

public:
    CircularDeque(int k) {
        deque = vector<int>(k);
        count = 0;
        maxCapacity = k;
        head = 0;
        tail = k - 1;
    }

    bool insertFront(int value) {
        if (isFull()) return false;
        head = (head - 1 + maxCapacity) % maxCapacity;
        deque[head] = value;
        count++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        tail = (tail + 1) % maxCapacity;
        deque[tail] = value;
        count++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        head = (head + 1) % maxCapacity;
        count--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        tail = (tail - 1 + maxCapacity) % maxCapacity;
        count--;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return deque[head];
    }

    int getRear() {
        if (isEmpty()) return -1;
        return deque[tail];
    }

    bool isEmpty() { return count == 0; }

    bool isFull() { return count == maxCapacity; }
};

The provided C++ code implements a data structure known as a Circular Deque (Double Ended Queue). This implementation allows for efficient addition and removal of items from both the front and the rear ends. Here's an overview of the functionality provided by the CircularDeque class:

• Initialization: The constructor CircularDeque(int k) initializes the deque with a capacity k. It sets up an internal vector to store the elements and maintains four properties: head, tail, count, and maxCapacity to manage the queue's state.

• Insert Operations:

  • insertFront(int value): Inserts an item at the front of the deque. It checks if the deque is full using isFull(). If not full, it adjusts the head pointer and inserts the value.
  • insertLast(int value): Appends an item to the rear of the deque. Similar to insertFront, it checks for available space and inserts the item if possible, updating the tail pointer.

• Delete Operations:

  • deleteFront(): Removes an item from the front of the deque. It checks if the deque is empty using isEmpty() before removing the item and adjusting the head pointer.
  • deleteLast(): Eliminates an item from the rear. It similarly verifies non-emptiness and adjusts the tail pointer.

• Access Operations:

  • getFront(): Retrieves the front item of the deque. If the deque is empty, it returns -1.
  • getRear(): Fetches the rear item. Again, if empty, it returns -1.

• Utility Functions:

  • isEmpty(): Checks if the deque is currently empty.
  • isFull(): Determines if the deque has reached its capacity.

This implementation leverages modular arithmetic to efficiently wrap around the internal vector indices, ensuring constant-time operations for insertions and deletions. This structure is particularly useful in situations where frequent additions and removals from both ends of a queue are necessary, providing flexibility and efficiency over traditional queues or stacks.

class CircularDeque {

    int[] elements;
    int head;
    int tail;
    int count;
    int maxCapacity;

    public CircularDeque(int k) {
        elements = new int[k];
        count = 0;
        maxCapacity = k;
        head = 0;
        tail = k - 1;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        head = (head - 1 + maxCapacity) % maxCapacity;
        elements[head] = value;
        count++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        tail = (tail + 1) % maxCapacity;
        elements[tail] = value;
        count++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        head = (head + 1) % maxCapacity;
        count--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        tail = (tail - 1 + maxCapacity) % maxCapacity;
        count--;
        return true;
    }

    public int getFront() {
        if (isEmpty()) return -1;
        return elements[head];
    }

    public int getRear() {
        if (isEmpty()) return -1;
        return elements[tail];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == maxCapacity;
    }
}

This Java solution implements a Circular Deque (double-ended queue) using an array. Here's a detailed explanation of how this implementation works:

• Create a fixed-size array elements to store deque elements and integer variables head, tail, count, and maxCapacity to track the state of the deque.
• Initialize the CircularDeque with a constructor specifying its maximum capacity, set head to 0, and tail to maximum capacity minus one. Initially, count, which tracks the number of elements in the deque, is set to 0.
• Implement insertFront(int value) to add an element at the front. If the deque is full (determined by isFull()), the operation returns false. Otherwise, adjust head and insert the value, then increment the count.
• Implement insertLast(int value) to add an element at the end. This method also checks if the deque is full, adjusts the tail, inserts the value, and increments the count.
• deleteFront() removes an element from the front. If the deque is empty (checked by isEmpty()), it returns false. If not, it adjusts head and decrements count.
• deleteLast() removes an element from the end, similarly working with checks for emptiness, adjusting the tail, and modifying count.
• getFront() retrieves the element at the front. If empty, it returns -1; otherwise, it returns the element at the head index.
• getRear() retrieves the element at the end, operating similarly by checking emptiness and then accessing the element at the tail index.
• isEmpty() and isFull() provide utility checks to see if the deque is empty or full, respectively, used in various other methods to determine operation feasibility.

This circular deque efficiently utilizes the circular nature of the underlying array, allowing both front and rear operations to wrap around the end of the array using modular arithmetic.

class CircularDeque:

    def __init__(self, capacity):
        self.data = [0] * capacity
        self.head = 0
        self.tail = capacity - 1
        self.count = 0
        self.max_size = capacity

    def insertFront(self, value):
        if self.isFull():
            return False
        self.head = (self.head - 1 + self.max_size) % self.max_size
        self.data[self.head] = value
        self.count += 1
        return True

    def insertLast(self, value):
        if self.isFull():
            return False
        self.tail = (self.tail + 1) % self.max_size
        self.data[self.tail] = value
        self.count += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.max_size
        self.count -= 1
        return True

    def deleteLast(self):
        if self.isEmpty():
            return False
        self.tail = (self.tail - 1 + self.max_size) % self.max_size
        self.count -= 1
        return True

    def getFront(self):
        if self.isEmpty():
            return -1
        return self.data[self.head]

    def getRear(self):
        if self.isEmpty():
            return -1
        return self.data[self.tail]

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

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

The solution involves implementing a data structure called CircularDeque using Python. This structure allows operations to be performed from both ends of the deque, which are optimized by circular indexing to handle wrap-around at the ends.

• Initialize the deque with a specified capacity:

  • An array data is allocated with the size equal to capacity to store the elements of the deque.
  • Pointers head and tail are initiated to point respectively to the beginning and the end of the deque.
  • count keeps track of the number of elements currently stored, and max_size holds the maximum number of items that can be accommodated.

• Insert elements at both ends:

  • insertFront: Adds an element at the front. If the deque is full, it returns False; otherwise, it adjusts the head pointer to make space and inserts the new item.
  • insertLast: Appends an element at the back. If there is no space, it returns False; otherwise, it moves the tail pointer and adds the element.

• Delete elements from both ends:

  • deleteFront: Removes the front element. Returns False if the deque is empty; otherwise, it forwards the head pointer and reduces the count.
  • deleteLast: Removes the back element. Returns False if empty; otherwise, it moves the tail pointer backward.

• Access elements:

  • getFront: Returns the front element or -1 if empty.
  • getRear: Provides the rear element or -1 if there is no element.

• Check states:

  • isEmpty: Returns True if there are no elements in the deque, else False.
  • isFull: Indicates if the deque has reached its capacity.

By executing these methods, the CircularDeque structure efficiently manages its operations without needing to shift elements, utilizing the mod operation to maintain the circular references. This design ensures optimal performance for operations at both ends of the deque.