Problem

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implementation the MyCircularQueue class:

  • MyCircularQueue(k) Initializes the object with the size of the queue to be k.
  • int Front() Gets the front item from the queue. If the queue is empty, return -1.
  • int Rear() Gets the last item from the queue. If the queue is empty, return -1.
  • boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
  • boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
  • boolean isEmpty() Checks whether the circular queue is empty or not.
  • boolean isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language. 

Examples

Example 1:

**Input**
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
**Output**
[null, true, true, true, false, 3, true, true, true, 4]

**Explanation**
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Solution

Method 1 - Using Array

A circular queue is a variation of a standard queue where the end of the queue is connected back to the front, forming a circle. This allows efficient use of space and avoids unused spaces in front of the queue after elements are dequeued. It maintains operations based on the FIFO (First In First Out) principle.

Approach

  1. Initialization: Use an array arr to represent the queue. Maintain front and rear pointers and a size counter.
  2. Operations:
    • enQueue: Add an element at the position indicated by rear and update the rear pointer and size.
    • deQueue: Remove the element from the position indicated by front and update the front pointer and size.
    • Front: Return the element at the front pointer.
    • Rear: Return the element at the rear pointer.
    • isEmpty: Check if the queue size is zero.
    • isFull: Check if the queue size is equal to the capacity.

Insert from rear and pop from front.

Code

Java
class MyCircularQueue {
    private int[] arr;
    private int front, rear, size, capacity;

    public MyCircularQueue(int k) {
        capacity = k;
        arr = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = value;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return arr[front];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[rear];
    }

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

    public boolean isFull() {
        return size == capacity;
    }
}
Python
class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.arr = [0] * k
        self.front = 0
        self.rear = -1
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.arr[self.rear] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.arr[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.arr[self.rear]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

Complexity

  • ⏰ Time complexity: O(1) for all operations (enQueue, deQueue, Front, Rear, isEmpty, isFull)
  • 🧺 Space complexity: O(n), where n is the size of the array used to store the queue elements.

Method 2 - Using Double Linked List

Using a doubly linked list provides flexibility in managing the elements of the circular queue. In a doubly linked list, each node maintains references to both the next and previous nodes, making it easier to insert and delete elements from both ends of the queue. The head and tail nodes help in managing the front and rear of the circular queue efficiently, while maintaining the size of the queue to check its fullness and emptiness.

Approach

  1. ListNode Class: Define a ListNode class with val, prev, and next attributes to store the value and the references to the previous and next nodes.
  2. MyCircularQueue Class:
    • Initialization: Initialize the queue with a given size k. Create dummy head and tail nodes and link them.
    • enQueue(int value): Add a new node before the tail node and update the links.
    • deQueue(): Remove the node after the head node and update the links.
    • Front(): Return the value of the node after the head.
    • Rear(): Return the value of the node before the tail.
    • isEmpty(): Check if the current size currSize is zero.
    • isFull(): Check if the current size currSize is equal to the maximum size queueSize.

Code

Java
class ListNode {
    int val;
    ListNode prev, next;
    
    public ListNode(int x) {
        val = x;
        prev = null;
        next = null;
    }
}

class MyCircularQueue {
	int queueSize, currSize;
	ListNode head, tail;

	public MyCircularQueue(int k) {
		queueSize = k;
		currSize = 0;
		head = new ListNode(-1);
		tail = new ListNode(-1);
		head.next = tail;
		tail.prev = head;
	}

	public boolean enQueue(int value) {
		if (isFull()) {
			return false;
		}
		ListNode newNode = new ListNode(value);
		newNode.next = tail;
		newNode.prev = tail.prev;
		tail.prev.next = newNode;
		tail.prev = newNode;
		currSize++;
		return true;
	}

	public boolean deQueue() {
		if (isEmpty()) {
			return false;
		}
		ListNode toBeDeleted = head.next;
		head.next = toBeDeleted.next;
		toBeDeleted.next.prev = head;
		toBeDeleted.next = null;
		toBeDeleted.prev = null;
		currSize--;
		return true;
	}

	public int Front() {
		if (isEmpty()) {
			return -1;
		}
		return head.next.val;
	}

	public int Rear() {
		if (isEmpty()) {
			return -1;
		}
		return tail.prev.val;
	}

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

	public boolean isFull() {
		return currSize == queueSize;
	}
}
Python
class ListNode:
    def __init__(self, x: int):
        self.val = x
        self.prev = None
        self.next = None

class MyCircularQueue:
    def __init__(self, k: int):
        self.queueSize = k
        self.currSize = 0
        self.head = Solution.ListNode(-1)
        self.tail = Solution.ListNode(-1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        new_node = Solution.ListNode(value)
        new_node.next = self.tail
        new_node.prev = self.tail.prev
        self.tail.prev.next = new_node
        self.tail.prev = new_node
        self.currSize += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        to_be_deleted = self.head.next
        self.head.next = to_be_deleted.next
        to_be_deleted.next.prev = self.head
        to_be_deleted.next = None
        to_be_deleted.prev = None
        self.currSize -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.head.next.val

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.tail.prev.val

    def isEmpty(self) -> bool:
        return self.currSize == 0

    def isFull(self) -> bool:
        return self.currSize == self.queueSize

Complexity

  • ⏰ Time complexity: O(1) for all operations (enQueue, deQueue, Front, Rear, isEmpty, isFull)
  • 🧺 Space complexity: O(n), where n is the maximum size of the queue.