Queue Basics | FIFO Data Structure | Queue

Overview

A queue is a fundamental FIFO (First-In, First-Out) data structure where elements are added at the rear (enqueue) and removed from the front (dequeue). This ordering principle makes queues perfect for scenarios where you need to process elements in the exact order they arrived, such as task scheduling, BFS traversal, and level-order processing.

Unlike stacks (LIFO), queues maintain chronological order, ensuring the first element added is the first one removed. This makes queues essential for breadth-first search (BFS), level-order tree traversal, and many real-world applications like print queues, message queues, and request handling.

Key characteristics:

FIFO order - First element added is first removed
Two ends - Front (dequeue) and rear (enqueue)
O(1) operations - Enqueue and dequeue in constant time (amortized)
Dynamic size - Can grow/shrink as needed
Level-order processing - Process elements level by level

Basic Operations

Core Queue Operations

A queue supports these fundamental operations:

enqueue(item) - Add element to the rear (back) of the queue
dequeue() - Remove and return element from the front
peek() / front() - View front element without removing
isEmpty() - Check if queue is empty
size() - Get number of elements

Time complexity:

enqueue: O(1) amortized
dequeue: O(1) amortized
peek: O(1)
isEmpty: O(1)
size: O(1)

Space complexity: O(n) where n is number of elements

Implementation Approaches

Approach 1: Array-Based Queue

Using an array with front and rear pointers. Simple but may waste space.

class Queue<T> {
  private items: T[] = [];
  private front = 0;
  private rear = -1;
  
  enqueue(item: T): void {
    this.rear++;
    this.items[this.rear] = item;
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.front];
    this.front++;
    return item;
  }
  
  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.front > this.rear;
  }
  
  size(): number {
    return this.rear - this.front + 1;
  }
}

Limitation: Space grows but never shrinks (front pointer moves forward but array doesn't shrink).

Approach 2: Linked List-Based Queue

Using a linked list with head (front) and tail (rear) pointers. More space-efficient.

class ListNode<T> {
  val: T;
  next: ListNode<T> | null = null;
  constructor(val: T) {
    this.val = val;
  }
}

class Queue<T> {
  private head: ListNode<T> | null = null;
  private tail: ListNode<T> | null = null;
  private length = 0;
  
  enqueue(item: T): void {
    const newNode = new ListNode(item);
    
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      this.tail = newNode;
    }
    
    this.length++;
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const item = this.head!.val;
    this.head = this.head!.next;
    
    if (this.head === null) {
      this.tail = null;
    }
    
    this.length--;
    return item;
  }
  
  peek(): T | undefined {
    return this.head?.val;
  }
  
  isEmpty(): boolean {
    return this.head === null;
  }
  
  size(): number {
    return this.length;
  }
}

Advantages:

No wasted space
Dynamic size
O(1) operations

Approach 3: Using Built-in Array (JavaScript/TypeScript)

Using array shift() and push() operations. Simple but shift() is O(n).

class Queue<T> {
  private items: T[] = [];
  
  enqueue(item: T): void {
    this.items.push(item); // O(1)
  }
  
  dequeue(): T | undefined {
    return this.items.shift(); // O(n) - inefficient!
  }
  
  peek(): T | undefined {
    return this.items[0];
  }
  
  isEmpty(): boolean {
    return this.items.length === 0;
  }
  
  size(): number {
    return this.items.length;
  }
}

Note: shift() is O(n) because it needs to shift all elements. For better performance, use linked list or circular queue.

Common Patterns

Pattern 1: Basic Queue Usage

Simple FIFO processing:

function processQueue<T>(items: T[]): T[] {
  const queue = new Queue<T>();
  const result: T[] = [];
  
  // Enqueue all items
  for (const item of items) {
    queue.enqueue(item);
  }
  
  // Process in FIFO order
  while (!queue.isEmpty()) {
    result.push(queue.dequeue()!);
  }
  
  return result;
}

Pattern 2: Level-by-Level Processing

Process elements level by level (foundation for BFS):

function processLevelByLevel<T>(items: T[]): void {
  const queue = new Queue<T>();
  
  // Add initial items
  for (const item of items) {
    queue.enqueue(item);
  }
  
  while (!queue.isEmpty()) {
    const levelSize = queue.size();
    
    // Process all items at current level
    for (let i = 0; i < levelSize; i++) {
      const item = queue.dequeue()!;
      // Process item
      console.log(item);
      
      // Add next level items if needed
      // queue.enqueue(nextItem);
    }
  }
}

Pattern 3: Task Queue

Process tasks in order:

interface Task {
  id: number;
  name: string;
  priority: number;
}

class TaskQueue {
  private queue = new Queue<Task>();
  
  addTask(task: Task): void {
    this.queue.enqueue(task);
  }
  
  processNext(): Task | undefined {
    return this.queue.dequeue();
  }
  
  hasTasks(): boolean {
    return !this.queue.isEmpty();
  }
}

When to Use Queue

Use a queue when you see these signals:

"Level-order" or "level by level" processing
"Breadth-first" traversal
"FIFO" or "first come first served" requirement
"Process in order" - maintain arrival order
"Task scheduling" - process tasks sequentially
"BFS" - graph/tree traversal
"Shortest path" - unweighted graphs

Key distinction:

Queue (FIFO) - Process in arrival order, level by level
Stack (LIFO) - Process in reverse order, depth-first
Priority Queue - Process by priority, not arrival order

Queue vs Stack

| Aspect | Queue (FIFO) | Stack (LIFO) |

|--------|-------------|--------------|

| Order | First in, first out | Last in, first out |

| Operations | enqueue (rear), dequeue (front) | push (top), pop (top) |

| Use case | BFS, level-order, scheduling | DFS, backtracking, parsing |

| Processing | Level by level | Depth first |

| Typical problems | BFS, level-order traversal | DFS, valid parentheses |

Remember:

Queue for breadth-first, level-order, chronological processing
Stack for depth-first, reverse order, backtracking

Template (Basic Queue Usage)

function queueTemplate<T>(items: T[]): T[] {
  const queue = new Queue<T>();
  const result: T[] = [];
  
  // Initialize queue
  for (const item of items) {
    queue.enqueue(item);
  }
  
  // Process queue
  while (!queue.isEmpty()) {
    const item = queue.dequeue()!;
    
    // Process item
    result.push(item);
    
    // Add related items if needed
    // queue.enqueue(relatedItem);
  }
  
  return result;
}

Template (Level-by-Level Processing)

function levelByLevelTemplate<T>(root: T): T[][] {
  const queue = new Queue<T>();
  const result: T[][] = [];
  
  queue.enqueue(root);
  
  while (!queue.isEmpty()) {
    const levelSize = queue.size();
    const level: T[] = [];
    
    // Process all nodes at current level
    for (let i = 0; i < levelSize; i++) {
      const node = queue.dequeue()!;
      level.push(node);
      
      // Add children to queue
      // for (const child of node.children) {
      //   queue.enqueue(child);
      // }
    }
    
    result.push(level);
  }
  
  return result;
}

Time and Space Complexity

Array-Based Queue

enqueue: O(1) amortized
dequeue: O(1) amortized (if using circular buffer)
peek: O(1)
isEmpty: O(1)
Space: O(n)

Linked List-Based Queue

enqueue: O(1)
dequeue: O(1)
peek: O(1)
isEmpty: O(1)
Space: O(n)

JavaScript Array (push/shift)

enqueue (push): O(1)
dequeue (shift): O(n) ⚠️ Inefficient!
peek: O(1)
Space: O(n)

Recommendation: Use linked list or circular queue for O(1) dequeue.

Practice Tips

Understand FIFO order - First added is first removed
Track front and rear - Know which end to add/remove from
Handle empty queue - Always check isEmpty before dequeue
Level-by-level pattern - Process all items at current level before next
Use for BFS - Queue is essential for breadth-first search
Choose implementation - Linked list for dynamic, array for fixed size
Avoid shift() - Use linked list or circular queue instead

Common Mistakes

Using shift() - O(n) operation, use linked list instead
Wrong order - Adding to front instead of rear (confusing with stack)
Not checking empty - Dequeue from empty queue causes errors
Mixing queue and stack - Using wrong data structure for problem
Not tracking level size - Forgetting to process level by level
Memory leaks - Not clearing references in linked list implementation
Index errors - Off-by-one errors in array-based implementation

Real-World Applications

Queues are used extensively in:

Operating Systems - Process scheduling, task queues
Networking - Packet routing, message queues
Web Servers - Request handling, rate limiting
Printers - Print job queues
Game Development - BFS for pathfinding, AI decision queues
Distributed Systems - Job queues, message brokers (RabbitMQ, Kafka)
Social Networks - Feed algorithms, friend suggestions
Search Engines - Web crawling queues

Related Concepts

Breadth-First Search (BFS) - Uses queue for graph/tree traversal
Level-Order Traversal - Queue-based tree traversal
Circular Queue - Fixed-size queue with wraparound
Priority Queue - Queue with priority ordering
Deque - Double-ended queue (both ends)
Stack - LIFO data structure (opposite of queue)

Summary

Queue is a fundamental FIFO data structure essential for:

BFS traversal - Graph and tree algorithms
Level-order processing - Process elements level by level
Task scheduling - Maintain order of tasks
Chronological processing - First come, first served

Key takeaways:

Master basic operations (enqueue, dequeue, peek)
Understand FIFO vs LIFO (queue vs stack)
Use for level-by-level processing
Choose right implementation (linked list recommended)
Essential foundation for BFS algorithms

Mastering queue basics will prepare you for BFS, level-order traversal, and many graph/tree problems in coding interviews.

Queue Basics (FIFO, Operations)