LC#622 Design Circular Queue

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.

Implement 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.

package main

import "fmt"

// MyCircularQueue implements a fixed-size circular queue.
// It supports constant-time enqueue, dequeue, and access operations.
type MyCircularQueue struct {
	data       []int
	head       int // Index of the front element
	tail       int // Index where the next element will be inserted
	size       int // Current number of elements
	capacity   int // Maximum number of elements
}

// Constructor622 initializes a new circular queue with capacity k.
func Constructor622(k int) MyCircularQueue {
	if k <= 0 {
		panic("Queue capacity must be greater than zero")
	}
	return MyCircularQueue{
		data:     make([]int, k),
		capacity: k,
	}
}

// IsEmpty returns true if the queue is empty.
func (q *MyCircularQueue) IsEmpty() bool {
	return q.size == 0
}

// IsFull returns true if the queue has reached its capacity.
func (q *MyCircularQueue) IsFull() bool {
	return q.size == q.capacity
}

// EnQueue inserts an element at the rear of the queue.
// Returns false if the queue is full.
func (q *MyCircularQueue) EnQueue(value int) bool {
	if q.IsFull() {
		return false
	}
	q.data[q.tail] = value
	q.tail = (q.tail + 1) % q.capacity
	q.size++
	return true
}

// DeQueue removes the element at the front of the queue.
// Returns false if the queue is empty.
func (q *MyCircularQueue) DeQueue() bool {
	if q.IsEmpty() {
		return false
	}
	q.head = (q.head + 1) % q.capacity
	q.size--
	return true
}

// Front returns the front element of the queue.
// Returns -1 if the queue is empty.
func (q *MyCircularQueue) Front() int {
	if q.IsEmpty() {
		return -1
	}
	return q.data[q.head]
}

// Rear returns the last inserted element in the queue.
// Returns -1 if the queue is empty.
func (q *MyCircularQueue) Rear() int {
	if q.IsEmpty() {
		return -1
	}
	lastIndex := (q.tail - 1 + q.capacity) % q.capacity
	return q.data[lastIndex]
}

// For demonstration
func main() {
	q := Constructor622(3)
	fmt.Println(q.EnQueue(1)) // true
	fmt.Println(q.EnQueue(2)) // true
	fmt.Println(q.EnQueue(3)) // true
	fmt.Println(q.EnQueue(4)) // false, full
	fmt.Println(q.Rear())     // 3
	fmt.Println(q.IsFull())   // true
	fmt.Println(q.DeQueue())  // true
	fmt.Println(q.EnQueue(4)) // true
	fmt.Println(q.Rear())     // 4
}

Below is the enhanced MyCircularQueue implementation with concurrency safety using sync.Mutex, and a simple performance benchmark using Go’s testing framework.

• Clean method structure with Lock/Unlock
• Added sync.Mutex to protect shared state (head, tail, size)
• *MyCircularQueue used instead of value receiver for performance and thread safety
• Includes a benchmark simulating high-concurrency operations

package main

import (
	"fmt"
	"sync"
)

// MyCircularQueue implements a fixed-size circular queue with concurrency safety.
type MyCircularQueue struct {
	data     []int
	head     int
	tail     int
	size     int
	capacity int
	mu       sync.Mutex
}

// Constructor622 initializes a new circular queue with capacity k.
func Constructor622(k int) *MyCircularQueue {
	if k <= 0 {
		panic("Queue capacity must be greater than zero")
	}
	return &MyCircularQueue{
		data:     make([]int, k),
		capacity: k,
	}
}

// IsEmpty returns true if the queue is empty.
func (q *MyCircularQueue) IsEmpty() bool {
	q.mu.Lock()
	defer q.mu.Unlock()
	return q.size == 0
}

// IsFull returns true if the queue is full.
func (q *MyCircularQueue) IsFull() bool {
	q.mu.Lock()
	defer q.mu.Unlock()
	return q.size == q.capacity
}

// EnQueue inserts an element at the rear of the queue.
func (q *MyCircularQueue) EnQueue(value int) bool {
	q.mu.Lock()
	defer q.mu.Unlock()
	if q.size == q.capacity {
		return false
	}
	q.data[q.tail] = value
	q.tail = (q.tail + 1) % q.capacity
	q.size++
	return true
}

// DeQueue removes the element from the front of the queue.
func (q *MyCircularQueue) DeQueue() bool {
	q.mu.Lock()
	defer q.mu.Unlock()
	if q.size == 0 {
		return false
	}
	q.head = (q.head + 1) % q.capacity
	q.size--
	return true
}

// Front returns the front item from the queue.
func (q *MyCircularQueue) Front() int {
	q.mu.Lock()
	defer q.mu.Unlock()
	if q.size == 0 {
		return -1
	}
	return q.data[q.head]
}

// Rear returns the last inserted item from the queue.
func (q *MyCircularQueue) Rear() int {
	q.mu.Lock()
	defer q.mu.Unlock()
	if q.size == 0 {
		return -1
	}
	lastIndex := (q.tail - 1 + q.capacity) % q.capacity
	return q.data[lastIndex]
}