Implement Queue

Implement a queue using arrays or linked lists with O(1) time complexity for all operations.

Language Selection

Choose your preferred programming language

Showing: Python

Implement Queue

Problem Statement

Implement a first in first out (FIFO) queue using arrays or linked lists. The implemented queue should support all the functions of a normal queue (enqueue, dequeue, front, rear, isEmpty, and isFull).

Implement the MyQueue class:

void enqueue(int x) Pushes element x to the back of the queue
int dequeue() Removes the element from the front of the queue and returns it
int front() Returns the element at the front of the queue
int rear() Returns the element at the back of the queue
boolean isEmpty() Returns true if the queue is empty, false otherwise
boolean isFull() Returns true if the queue is full, false otherwise

Examples

Example 1:

Input:
["MyQueue", "enqueue", "enqueue", "enqueue", "dequeue", "dequeue", "front", "rear", "isEmpty"]
[[3], [1], [2], [3], [], [], [], [], []]

Output:
[null, null, null, null, 1, 2, 3, 3, false]

Explanation:
MyQueue myQueue = new MyQueue(3);
myQueue.enqueue(1); // queue is: [1]
myQueue.enqueue(2); // queue is: [1, 2]
myQueue.enqueue(3); // queue is: [1, 2, 3]
myQueue.dequeue();  // return 1, queue is [2, 3]
myQueue.dequeue();  // return 2, queue is [3]
myQueue.front();    // return 3
myQueue.rear();     // return 3
myQueue.isEmpty();  // return false

Constraints

1 <= capacity <= 1000
0 <= x <= 1000
At most 3000 calls will be made to enqueue, dequeue, front, rear, isEmpty, and isFull

Approach 1: Array-Based Implementation (Optimal)

Algorithm

Use a fixed-size array with head and tail pointers to implement a queue.

Steps:

Use a fixed-size array to store elements
Use head pointer to track the front of the queue
Use tail pointer to track the next available position
Use count to track the number of elements
Implement circular behavior using modulo arithmetic

Implementation

Python:

class MyQueue:
    """
    Queue implementation using array
    Time: O(1) for all operations
    Space: O(n)
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = [0] * capacity
        self.head = 0
        self.tail = 0
        self.count = 0
    
    def enqueue(self, x: int) -> bool:
        """Add element x to the back of queue"""
        if self.isFull():
            return False
        
        self.queue[self.tail] = x
        self.tail = (self.tail + 1) % self.capacity
        self.count += 1
        return True
    
    def dequeue(self) -> int:
        """Remove element from front of queue and return it"""
        if self.isEmpty():
            return -1
        
        result = self.queue[self.head]
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return result
    
    def front(self) -> int:
        """Return element at front of queue"""
        if self.isEmpty():
            return -1
        return self.queue[self.head]
    
    def rear(self) -> int:
        """Return element at back of queue"""
        if self.isEmpty():
            return -1
        return self.queue[(self.tail - 1 + self.capacity) % self.capacity]
    
    def isEmpty(self) -> bool:
        """Return true if queue is empty"""
        return self.count == 0
    
    def isFull(self) -> bool:
        """Return true if queue is full"""
        return self.count == self.capacity

Java:

class MyQueue {
    /**
     * Queue implementation using array
     * Time: O(1) for all operations
     * Space: O(n)
     */
    
    private int[] queue;
    private int head;
    private int tail;
    private int count;
    private int capacity;
    
    public MyQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }
    
    public boolean enqueue(int x) {
        if (isFull()) {
            return false;
        }
        
        queue[tail] = x;
        tail = (tail + 1) % capacity;
        count++;
        return true;
    }
    
    public int dequeue() {
        if (isEmpty()) {
            return -1;
        }
        
        int result = queue[head];
        head = (head + 1) % capacity;
        count--;
        return result;
    }
    
    public int front() {
        if (isEmpty()) {
            return -1;
        }
        return queue[head];
    }
    
    public int rear() {
        if (isEmpty()) {
            return -1;
        }
        return queue[(tail - 1 + capacity) % capacity];
    }
    
    public boolean isEmpty() {
        return count == 0;
    }
    
    public boolean isFull() {
        return count == capacity;
    }
}

Go:

type MyQueue struct {
    queue    []int
    head     int
    tail     int
    count    int
    capacity int
}

// Constructor - Initialize queue
func Constructor(capacity int) MyQueue {
    return MyQueue{
        queue:    make([]int, capacity),
        head:     0,
        tail:     0,
        count:    0,
        capacity: capacity,
    }
}

// Enqueue - Add element x to the back of queue
func (this *MyQueue) Enqueue(x int) bool {
    if this.IsFull() {
        return false
    }
    
    this.queue[this.tail] = x
    this.tail = (this.tail + 1) % this.capacity
    this.count++
    return true
}

// Dequeue - Remove element from front of queue and return it
func (this *MyQueue) Dequeue() int {
    if this.IsEmpty() {
        return -1
    }
    
    result := this.queue[this.head]
    this.head = (this.head + 1) % this.capacity
    this.count--
    return result
}

// Front - Return element at front of queue
func (this *MyQueue) Front() int {
    if this.IsEmpty() {
        return -1
    }
    return this.queue[this.head]
}

// Rear - Return element at back of queue
func (this *MyQueue) Rear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.queue[(this.tail-1+this.capacity)%this.capacity]
}

// IsEmpty - Return true if queue is empty
func (this *MyQueue) IsEmpty() bool {
    return this.count == 0
}

// IsFull - Return true if queue is full
func (this *MyQueue) IsFull() bool {
    return this.count == this.capacity
}

JavaScript:

/**
 * Queue implementation using array
 * Time: O(1) for all operations
 * Space: O(n)
 */
class MyQueue {
    constructor(capacity) {
        this.capacity = capacity;
        this.queue = new Array(capacity);
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }
    
    enqueue(x) {
        if (this.isFull()) {
            return false;
        }
        
        this.queue[this.tail] = x;
        this.tail = (this.tail + 1) % this.capacity;
        this.count++;
        return true;
    }
    
    dequeue() {
        if (this.isEmpty()) {
            return -1;
        }
        
        const result = this.queue[this.head];
        this.head = (this.head + 1) % this.capacity;
        this.count--;
        return result;
    }
    
    front() {
        if (this.isEmpty()) {
            return -1;
        }
        return this.queue[this.head];
    }
    
    rear() {
        if (this.isEmpty()) {
            return -1;
        }
        return this.queue[(this.tail - 1 + this.capacity) % this.capacity];
    }
    
    isEmpty() {
        return this.count === 0;
    }
    
    isFull() {
        return this.count === this.capacity;
    }
}

C#:

public class MyQueue {
    /// <summary>
    /// Queue implementation using array
    /// Time: O(1) for all operations
    /// Space: O(n)
    /// </summary>
    
    private int[] queue;
    private int head;
    private int tail;
    private int count;
    private int capacity;
    
    public MyQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }
    
    public bool Enqueue(int x) {
        if (IsFull()) {
            return false;
        }
        
        queue[tail] = x;
        tail = (tail + 1) % capacity;
        count++;
        return true;
    }
    
    public int Dequeue() {
        if (IsEmpty()) {
            return -1;
        }
        
        int result = queue[head];
        head = (head + 1) % capacity;
        count--;
        return result;
    }
    
    public int Front() {
        if (IsEmpty()) {
            return -1;
        }
        return queue[head];
    }
    
    public int Rear() {
        if (IsEmpty()) {
            return -1;
        }
        return queue[(tail - 1 + capacity) % capacity];
    }
    
    public bool IsEmpty() {
        return count == 0;
    }
    
    public bool IsFull() {
        return count == capacity;
    }
}

Complexity Analysis

Time Complexity: O(1) for all operations
Space Complexity: O(n) where n is the capacity

Key Insights

Array Implementation: Use circular array with head and tail pointers
Circular Buffer: Use modulo arithmetic for wrap-around behavior
FIFO Behavior: Maintain first-in-first-out order
Space Efficiency: Pre-allocate array for predictable memory usage
Count Tracking: Use count variable for efficient size checking

Edge Cases

Empty Queue: All operations on empty queue
Full Queue: Enqueue operations on full queue
Single Element: Queue with one element
Capacity 1: Queue with capacity 1
Wrap Around: Head and tail pointers wrap around

Follow-up Questions

Dynamic Size: What if the queue size can grow dynamically?
Thread Safety: How would you make it thread-safe?
Memory Management: How would you handle memory allocation?
Performance: How would you optimize for high-frequency operations?

Common Mistakes

Modulo Arithmetic: Incorrect calculation of head/tail positions
Empty/Full Check: Wrong logic for determining queue state
Index Bounds: Not handling array bounds properly
Pointer Management: Incorrect head/tail pointer updates

Interview Tips

Clarify Requirements: Ask about capacity limits and operation requirements
Discuss Approaches: Mention both array and linked list approaches
Handle Edge Cases: Discuss empty, full, and single-element scenarios
Explain Algorithm: Walk through the circular buffer concept
Optimize Space: Consider space-time tradeoffs