Queues Data Structure — Complete Guide

What is a Queue?

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Think of a real-world line of people waiting to buy tickets: the person who gets in line first is served first, and new people join at the end of the line.

Enqueue (Add to Rear) ──→ [ 40 | 30 | 20 | 10 ] ──→ Dequeue (Remove from Front)
                          Rear            Front

In software engineering, queues form the core of:

• Task Scheduling: CPU task queues, printer spooling.
• Asynchronous Message Buffers: RabbitMQ, Kafka, AWS SQS.
• Breadth-First Search (BFS): Graph and tree traversal algorithms.
• Rate Limiting: Managing web server request spikes.

Core Operations & Complexity

Types of Queues

1. Simple Linear Queue

Elements are inserted at the rear and removed from the front. A basic array implementation suffers from false overflow: after multiple dequeues, empty space at the front of the array cannot be reused without costly O(N) shifting.

2. Circular Queue

A Circular Queue overcomes memory wastage by connecting the last position back to the first position, forming a ring.

       [0]  ← Front
     /     \
   [3]     [1]
     \     /
       [2]  ← Rear

javascript
class CircularQueue {
    constructor(capacity) {
        this.capacity = capacity;
        this.queue = new Array(capacity);
        this.front = -1;
        this.rear = -1;
        this.size = 0;
    }

    enqueue(element) {
        if (this.isFull()) return false;
        if (this.isEmpty()) this.front = 0;
        
        this.rear = (this.rear + 1) % this.capacity;
        this.queue[this.rear] = element;
        this.size++;
        return true;
    }

    dequeue() {
        if (this.isEmpty()) return null;
        const item = this.queue[this.front];
        
        if (this.front === this.rear) {
            this.front = -1;
            this.rear = -1;
        } else {
            this.front = (this.front + 1) % this.capacity;
        }
        
        this.size--;
        return item;
    }

    isEmpty() { return this.size === 0; }
    isFull() { return this.size === this.capacity; }
}

3. Double-Ended Queue (Deque)

A Deque (pronounced "deck") allows insertion and deletion from both the front and the rear in O(1) time. It acts as both a Queue and a Stack simultaneously.

• pushFront(x), pushBack(x)
• popFront(), popBack()

4. Priority Queue

Elements are dequeued based on their priority rather than their insertion order. Typically implemented using a Min-Heap or Max-Heap.

Solved Problem 1: Implement Stack using Queues 🟢 Easy

Problem: Implement a LIFO stack using only standard FIFO queue operations (push, peek, pop, size).

Approach: Use a single queue. When pushing an element, append it, then rotate the previous size - 1 elements to the back of the queue so the newest element ends up at the front!

javascript
class MyStack {
    constructor() {
        this.q = [];
    }

    push(x) {
        this.q.push(x);
        let count = this.q.length;
        // Rotate queue to place newest item at front
        while (count > 1) {
            this.q.push(this.q.shift());
            count--;
        }
    }

    pop() {
        return this.q.shift();
    }

    top() {
        return this.q[0];
    }

    empty() {
        return this.q.length === 0;
    }
}

Time: push: O(N), pop: O(1) | Space: O(N)

Solved Problem 2: Sliding Window Maximum 🔴 Hard

Problem: Given an array nums and a window size k, find the maximum value in each sliding window of size k.

Optimal Solution (Monotonic Deque): Use a Deque to store indices of potential max elements in decreasing order of their values.

javascript
function maxSlidingWindow(nums, k) {
    const deque = []; // Stores indices
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // 1. Remove indices out of current window bounds
        if (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }

        // 2. Maintain decreasing order in deque
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }

        // 3. Add current index
        deque.push(i);

        // 4. Record maximum (at front of deque) for valid windows
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Output: [3, 3, 5, 5, 6, 7]

Time: O(N) — each index is pushed/popped at most once | Space: O(K)

Frequently Asked Questions

Q: Why shouldn't JavaScript Array.shift() be used for high-performance queues?
A: Array.shift() removes the first element and re-indexes all remaining elements, taking O(N) time. For O(1) queue operations in JS, use a pointer-based Linked List or maintain two indices on an array.

Q: What is the main application of Queues in Graph Algorithms?
A: Breadth-First Search (BFS) relies entirely on a FIFO Queue to traverse graph nodes level by level, guaranteeing the shortest path in unweighted graphs.