Algo — Algorithm Learning Tools

What is a Queue?

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Think of it like a line at a coffee shop — the first person in line gets served first!

Unlike arrays where you can access any element, queues are designed for sequential access. The two fundamental operations are enqueue (add to back) and dequeue (remove from front).

1. Core Terminology

EnqueueAdd an element to the back of the queue. O(1) operation.

DequeueRemove and return the element at the front. O(1) operation.

FrontThe first element that will be dequeued. Also called 'head'.

RearThe last element that was enqueued. Also called 'tail'.

Peek/FrontView the front element without removing it. O(1) operation.

isEmptyCheck if the queue has no elements. Returns boolean.

SizeNumber of elements currently in the queue.

OverflowAttempting to add to a full queue (in bounded implementations).

2. Types of Queues

Simple Queue (FIFO)

Basic queue where elements are processed in order of arrival. First element in is first element out.

Enqueue: A → [A]
Enqueue: B → [A, B]
Enqueue: C → [A, B, C]
Dequeue  → returns A, queue = [B, C]

Circular Queue

Back connects to front, creating a circle. Efficiently reuses empty spaces. Used in buffer implementations.

Front → points to index 0
Rear  → points to last element
After dequeue, front increments
After enqueue at end, rear wraps to start

Priority Queue

Elements have priority levels. Higher priority elements are dequeued first, regardless of arrival order.

Enqueue: (A, low), (B, high), (C, med)
Dequeue  → returns B (high priority)
Dequeue  → returns C (medium)
Dequeue  → returns A (low)

Deque (Double-Ended Queue)

Add and remove from both ends. Can function as both queue and stack. Used in task scheduling.

addFront(A)  → [A]
addBack(B)   → [A, B]
addFront(C)  → [C, A, B]
removeBack() → returns B, [C, A]

3. How Queues are Stored in Memory

Array-Based (Circular Buffer)

Fixed-size array with front and rear pointers. Space efficient but bounded. Must handle overflow.

queue = [_, _, _, _, _]  // size = 5
front = 0, rear = -1

enqueue(A): rear = (rear + 1) % 5
enqueue(B): rear = (rear + 1) % 5
dequeue(): front = (front + 1) % 5

Linked List

Dynamic size with head (front) and tail (rear) pointers. No overflow, but uses extra memory for pointers.

head → [A] → [B] → [C] → null
tail
enqueue(D): tail.next = new Node(D)
           tail = new Node(D)
dequeue(): head = head.next

Two Stack Implementation

Simulate queue using two stacks. Amortized O(1) operations. Used in interview questions.

enqueue(x): push onto stack1
dequeue():
  if stack2 empty:
    transfer stack1 → stack2
  return pop from stack2
// Queue order maintained!

Which to use?

Array for fixed-size, predictable memory.Linked List for dynamic size without overflow.Two Stacks for interviews or when only push/pop stacks are available.

4. Real-World Applications

BFS TraversalQueue

Level-by-level graph exploration

Print Job QueueFIFO Queue

Printers process jobs in order

Task SchedulingPriority Queue

CPU schedules high-priority tasks first

Breadth-First SearchQueue

Find shortest path in unweighted graphs

Web Server RequestsFIFO Queue

Handle HTTP requests in order

Buffer/Memory QueueCircular Queue

Streaming data with fixed buffer

Level Order TraversalQueue

Tree traversal level by level

Rotting OrangesBFS Multi-source

Simultaneous spreading process

5. Algorithms Using Queues

Breadth-First Search (BFS)Graph Traversal

Explore all vertices at distance d before distance d+1. Uses queue to track frontier.Complexity: O(V + E)

Level Order TraversalTree Traversal

Visit all nodes at depth d before depth d+1. Perfect for finding shortest tree paths.Complexity: O(n)

LRU CacheCaching

Use queue + hash map to track usage. Recently used items move to front.Complexity: O(1) per operation

Rotting OrangesGrid BFS

Multi-source BFS where all rotting oranges spread simultaneously.Complexity: O(m × n)

Key Insight

Queues are for ordered processing. Any situation where tasks must be handled "first come, first served" is a queue problem. The key is that queues preserve arrival order.

Remember

BFS: Queue = level-by-level exploration, shortest path.
LRU Cache: Queue tracks recency, hash map gives O(1) access.
Rotting Oranges: Multi-source BFS — all rotting oranges spread at once.