Queues — Complete DSA Queue Theory

Learning Progress. Work top to bottom: theory → operations → the interactive visualizer → patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is a Queue?

A Queue is a linear data structure following FIFO (First In, First Out). Elements are added at the rear and removed from the front — like a line at a checkout.

Both ends are touched by different operations, so enqueue and dequeue are O(1) when backed by a linked list or circular buffer.

Core operations

// FIFO — two ends
enqueue(x) // add at rear — O(1)
dequeue()  // remove front — O(1)
front()    // peek front — O(1)
empty()   // is it empty? — O(1)

Why Queues? Whenever order of arrival matters: CPU/task scheduling, BFS traversal, print spoolers, message buffers, rate limiting, and producer-consumer pipelines.

Variants

→

Simple Queue

Plain FIFO. Enqueue at rear, dequeue at front.

Use: BFS, scheduling, buffering.

↺

Circular Queue

Fixed array where rear wraps to the front, reusing freed slots. No shifting.

Use: ring buffers, streaming, bounded queues.

⚡

Priority Queue

Dequeue returns the highest (or lowest) priority element, not the oldest. Backed by a heap.

Use: Dijkstra, scheduling, top-K.

Terminology

Front

The oldest element; the next one to be removed.

Rear / Back

The most recently added element; where new items enter.

Enqueue

Add an element at the rear. O(1).

Dequeue

Remove and return the front element. O(1).

Circular wrap

In a circular queue, rear index wraps to 0 via modulo capacity.

Starvation

In priority queues, low-priority items may never be served.

Complexity Summary

Enqueue

O(1)

Add at rear.

Dequeue

O(1)

Remove at front.

Front / Peek

O(1)

Read the front element.

O(n)

No random access.

Priority Q ops

O(log n)

Heap-backed push/pop.

Space

O(n)

n elements stored.

Advantages & Disadvantages

Advantages

O(1) enqueue and dequeue.
Preserves arrival order — fair processing.
Foundation of BFS and level-order traversal.
Circular variant reuses memory with no shifting.

Disadvantages

No random access to middle elements.
Naive array dequeue is O(n) without a circular buffer.
Fixed-size circular queues can overflow.
Priority queues can starve low-priority items.

C++ STL Implementation

queue_stl.cpp · std::queue & priority_queue

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);      // enqueue rear
    q.push(20);
    q.push(30);      // front=10, rear=30
    cout << q.front() << " " << q.back() << "\n"; // 10 30
    q.pop();           // dequeue front (10)

    priority_queue<int> maxHeap;      // max on top
    priority_queue<int,vector<int>,greater<>> minHeap;
    maxHeap.push(5); maxHeap.push(1); maxHeap.push(9);
    cout << maxHeap.top(); // 9 — O(log n) push/pop
    return 0;
}

circular_queue.cpp · Fixed-size ring buffer

class CircularQueue {
    vector<int> buf; int head=0, sz=0, cap;
public:
    CircularQueue(int k):buf(k),cap(k){}
    bool enqueue(int x){
        if(sz==cap) return false; // full
        buf[(head+sz)%cap]=x; sz++; return true;
    }
    bool dequeue(){
        if(sz==0) return false; // empty
        head=(head+1)%cap; sz--; return true;
    }
    int front(){ return sz? buf[head] : -1; }
};

Interactive Queue Visualization

Element Front Rear Enqueue Dequeue

Idle

Current operation details

Operation

—

Front

—

Rear

—

Steps

taken

Enqueues

added

Dequeues

removed

Size

elements

Step — of —

Select a scenario above, or use the manual controls, then press Play.

Manual controls — build your own operation

Queue (front→rear): Value:

✓ Done

Speed

Step-by-step operation log

Step	Front	Rear	Action	Queue State
Run a scenario to populate the log.

Key Patterns

BFS uses a queue. Enqueue the start node, then repeatedly dequeue a node and enqueue its unvisited neighbours. FIFO order guarantees you explore level by level — shortest path in unweighted graphs.

Monotonic deque = sliding window max. Keep indices in a deque with decreasing values; the front is always the window maximum. O(n) total.

Cheat Sheet

Operation	Time	Space	Notes
Enqueue	O(1)	O(1)	Add at rear
Dequeue	O(1)	O(1)	Remove at front
Front / Peek	O(1)	O(1)	Read front
Search	O(n)	O(1)	Linear scan
Priority push/pop	O(log n)	O(n)	Heap-backed
Circular enqueue	O(1)	O(k)	Fixed capacity k, wraps

Learning Roadmap

Queue Basics

enqueue/dequeue/front, FIFO intuition, array vs linked-list backing.

~2 hours

Circular Queue & Deque

Ring buffers, wrap-around indexing, double-ended queue operations.

~3 hours

BFS & Level Order

Graph/tree BFS, shortest path in unweighted graphs, multi-source BFS.

~4 hours

Priority Queue & Monotonic Deque

Heaps, Dijkstra, top-K, sliding window maximum.

~4 hours

Interview Preparation

Implement Queue using Stacks

Two stacks: push to "in", pour into "out" when dequeuing. Amortized O(1).

Two Stacks

Design Circular Queue

Fixed array with head index and size; rear = (head+size)%cap. O(1) all ops.

Ring Buffer

Sliding Window Maximum

Monotonic decreasing deque of indices; front holds the max, pop stale/smaller. O(n).

Monotonic Deque

Rotting Oranges (multi-source BFS)

Enqueue all rotten cells, BFS outward counting minutes until none fresh remain.

BFS

Practice Problems

EasyImplement Queue using StacksTwo Stacks

EasyNumber of Recent CallsQueue

MediumDesign Circular QueueRing Buffer

MediumRotting OrangesBFS

MediumBinary Tree Level OrderBFS

MediumTask SchedulerPriority Queue

HardSliding Window MaximumMonotonic Deque

HardFind Median from Data StreamTwo Heaps

Key Takeaways

🎟️FIFO: first in, first out. Enqueue at rear, dequeue at front, both O(1).

🌊BFS engine: the queue drives breadth-first search and level-order traversal — shortest paths in unweighted graphs.

↺Circular buffer: wrap the rear index with modulo to reuse freed slots without shifting.

⚡Priority queue: a heap in disguise — serves highest priority first in O(log n), powering Dijkstra and top-K.