Circular Queue Implementation

Question

Implement a circular queue using a fixed-size array. A circular queue is a data structure that uses a single array and two pointers to indicate the start and end positions. It appears as though the array is connected end-to-end. Click on the Hint button if you need more information about Circular Queues and find out why it's relevant in the trading industry.
class CircularQueue:
    def __init__(self, size: int):
        pass

    def enqueue(self, item: Any) -> bool:
        pass

    def dequeue(self) -> Optional[Any]:
        pass

    def peek(self) -> Optional[Any]:
        pass

    def is_empty(self) -> bool:
        pass

    def is_full(self) -> bool:
        pass

Methods

 	enqueue(item: Any) -> bool: Adds an item to the rear of the queue.
 	dequeue() -> Optional[Any]: Removes and returns an item from the front of the queue.
 	peek() -> Optional[Any]: Returns the item at the front of the queue without removing it.
 	is_empty() -> bool: Checks if the queue is empty.
 	is_full() -> bool: Checks if the queue is full.

Inputs and Outputs

 	enqueue(item): Takes any type as input and returns a boolean. Returns True if the item was successfully added to the queue, and False otherwise.
 	dequeue(): Returns the dequeued item if successful and None if the queue is empty.
 	peek(): Returns the item at the front of the queue without removing it. Returns None if the queue is empty.
 	is_empty(): Returns True if the queue is empty and False otherwise.
 	is_full(): Returns True if the queue is full and False otherwise.

Example
cq = CircularQueue(3)
print(cq.enqueue(1))  # Should return True
print(cq.enqueue(2))  # Should return True
print(cq.enqueue(3))  # Should return True
print(cq.enqueue(4))  # Should return False (Queue is full)

print(cq.dequeue())  # Should return 1
print(cq.dequeue())  # Should return 2
print(cq.dequeue())  # Should return 3
print(cq.dequeue())  # Should return None (Queue is empty)

print(cq.is_empty())  # Should return True
print(cq.is_full())   # Should return False

cq.enqueue(5)
print(cq.peek())  # Should return 5
print(cq.is_empty())  # Should return False

Accepted Answer

from typing import Any, Optional

class CircularQueue:
    def __init__(self, size: int):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def enqueue(self, item: Any) -> bool:
        if (self.rear + 1) % self.size == self.front:  # Check if queue is full
            return False

        if self.front == -1:
            self.front = 0

        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = item
        return True

    def dequeue(self) -> Optional[Any]:
        if self.front == -1:  # Check if queue is empty
            return None

        removed_item = self.queue[self.front]

        if self.front == self.rear:
            self.front = self.rear = -1  # Reset pointers if queue becomes empty
        else:
            self.front = (self.front + 1) % self.size

        return removed_item

    def peek(self) -> Optional[Any]:
        if self.front == -1:  # Check if queue is empty
            return None
        return self.queue[self.front]

    def is_empty(self) -> bool:
        return self.front == -1

    def is_full(self) -> bool:
        return (self.rear + 1) % self.size == self.front

def test_circular_queue():
    cq = CircularQueue(3)

    # Test enqueue
    assert cq.enqueue(1) == True
    assert cq.enqueue(2) == True
    assert cq.enqueue(3) == True
    assert cq.enqueue(4) == False  # Queue is full

    # Test dequeue
    assert cq.dequeue() == 1
    assert cq.dequeue() == 2
    assert cq.dequeue() == 3
    assert cq.dequeue() == None  # Queue is empty

    # Test is_empty and is_full
    assert cq.is_empty() == True
    assert cq.is_full() == False

    # Test peek
    assert cq.enqueue(5) == True
    assert cq.peek() == 5
    assert cq.is_empty() == False

    print("All test cases pass")

test_circular_queue()

Title	Category	Subcategory	Difficulty	Status
Balanced Brackets	Programming	Other	Easy	Unlock
Evaluate RPN	Programming	Other	Medium	Unlock
Last Node of Singly Linked List	Programming	Other	Medium	Unlock
Linked List Cycle	Programming	Other	Medium	Unlock
Priority Queue Using Heaps	Programming	Other	Hard	Example
Reverse a Linked List	Programming	Other	Easy	Unlock
Streaming Median	Programming	Other	Hard	Unlock
Validate a BST	Programming	Other	Medium	Unlock
Weather API Data Analyzer	Programming	Other	Hard	Unlock

The Interview Guide for Quants and Traders

Circular Queue Implementation

What do you think of this page?