Katkat
Back

Design a circular queue data structure

OptiverSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement a fixed-capacity circular queue using a static array, focusing on efficient pointer arithmetic and state management.

Circular Queue Design

Design a circular queue data structure that follows the First-In-First-Out (FIFO) principle. The queue has a fixed capacity k defined at initialization. Your implementation must support the following operations in O(1) time complexity.

Requirements

Implement the CircularQueue class with the following methods:

  • __init__(self, k: int): Initializes the queue with a capacity of k.
  • enqueue(self, value: int) -> bool: Inserts an element into the circular queue. Returns True if the operation is successful, otherwise False.
  • dequeue(self) -> bool: Deletes an element from the circular queue. Returns True if the operation is successful, otherwise False.
  • front(self) -> int: Gets the front item from the queue. Returns -1 if the queue is empty.
  • rear(self) -> int: Gets the last item from the queue. Returns -1 if the queue is empty.
  • is_empty(self) -> bool: Checks whether the circular queue is empty.
  • is_full(self) -> bool: Checks whether the circular queue is full.

Examples

q = CircularQueue(3)
q.enqueue(1) # returns True
q.enqueue(2) # returns True
q.enqueue(3) # returns True
q.enqueue(4) # returns False (Queue is full)
q.rear()     # returns 3
q.is_full()  # returns True
q.dequeue()  # returns True
q.enqueue(4) # returns True
q.rear()     # returns 4

Constraints

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • All operations will be performed within integer limits.

Hints

Hint 1

Use a fixed-size array and two pointers to track the front and rear indices.

Hint 2

The modulo operator `%` is the key to wrapping indices back to the start of the array when they reach the end.

Hint 3

Consider maintaining a separate variable for the current size, or use a specific pointer configuration to distinguish between an empty and a full state.

Follow-up questions

  • How would you modify this implementation to be thread-safe in a multi-threaded environment?
  • What would change if the queue capacity needed to grow dynamically when full?
  • How would you implement this queue using two stacks instead of a static array?