Module 2: Stacks and Queues

Master the fundamentals of stacks and queues. Learn how to implement and use these fundamental data structures.

Module Objectives

Upon completion of this module you will be able to:

Understand what a stack is and its behavior (LIFO - Last In, First Out)
Understand what a queue is and its behavior (FIFO - First In, First Out)
Write code to implement a stack and its basic operations: push, pop, peek, isEmpty
Write code to implement a queue and its basic operations: enqueue, dequeue, peek, isEmpty
Apply stacks and queues to solve common programming problems
Analyze the time and space complexity of stack and queue operations

Stack Basics

Understanding Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates - you can only take the top plate, and you always add new plates to the top.

Key Stack Operations:

Push: Add an element to the top of the stack
Pop: Remove and return the top element
Peek/Top: View the top element without removing it
isEmpty: Check if the stack is empty

// Stack implementation using array
class Stack {
  constructor() {
    this.items = [];
  }
  
  // Add element to top of stack
  push(element) {
    this.items.push(element);
  }
  
  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Underflow - Stack is empty";
    }
    return this.items.pop();
  }
  
  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }
  
  // Check if stack is empty
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Return the size of the stack
  size() {
    return this.items.length;
  }
  
  // Clear the stack
  clear() {
    this.items = [];
  }
}

// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek());  // 30
console.log(stack.pop());   // 30
console.log(stack.size());  // 2
            

Common Stack Applications:

Function call management (call stack)
Expression evaluation and syntax parsing
Undo mechanisms in applications
Backtracking algorithms
Browser history

Queue Basics

Understanding Queues

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line of people - the first person to join the line is the first person served.

Key Queue Operations:

Enqueue: Add an element to the end of the queue
Dequeue: Remove and return the front element
Front/Peek: View the front element without removing it
isEmpty: Check if the queue is empty

// Queue implementation using array
class Queue {
  constructor() {
    this.items = [];
  }
  
  // Add element to the end of the queue
  enqueue(element) {
    this.items.push(element);
  }
  
  // Remove and return the front element
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow - Queue is empty";
    }
    return this.items.shift();
  }
  
  // Return the front element without removing it
  front() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }
  
  // Check if queue is empty
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Return the size of the queue
  size() {
    return this.items.length;
  }
  
  // Clear the queue
  clear() {
    this.items = [];
  }
}

// Usage example
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.front());    // 10
console.log(queue.dequeue());  // 10
console.log(queue.size());     // 2
  

More Efficient Queue Implementation

The array implementation above has O(n) time complexity for the dequeue operation due to array shift. A more efficient implementation uses an object with separate tracking for front and rear:

// Queue implementation with O(1) operations
class OptimizedQueue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }
  
  enqueue(element) {
    this.items[this.backIndex] = element;
    this.backIndex++;
  }
  
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow - Queue is empty";
    }
    
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }
  
  front() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[this.frontIndex];
  }
  
  isEmpty() {
    return this.backIndex - this.frontIndex === 0;
  }
  
  size() {
    return this.backIndex - this.frontIndex;
  }
}
  

Common Queue Applications:

Task scheduling
Printer spooling
Request handling in web servers
Breadth-first search algorithms
Message queues in distributed systems

Variations and Special Types

Circular Queue

A circular queue is a special implementation where the front and rear are connected in a circular fashion, optimizing space usage.

Priority Queue

A priority queue assigns a priority to each element, and elements with higher priority are served before elements with lower priority, regardless of their position in the queue.

Deque (Double-Ended Queue)

A deque allows insertion and deletion at both ends, combining features of both stacks and queues.

Practice with LeetCode Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing stack and queue implementations.

Stack Problems:

Valid Parentheses - Use a stack to check valid opening/closing of brackets
Min Stack - Implement a stack with constant time access to minimum element
Evaluate Reverse Polish Notation - Use a stack to evaluate postfix expressions

Queue Problems:

Implement Queue using Stacks - Build a queue using two stacks
Design Circular Queue - Implement a circular queue
Number of Recent Calls - Practical application of queues

Recursion vs. Iteration

It's important to understand when to use recursion versus iterative approaches:

Aspect	Recursion	Iteration
Memory Usage	Uses call stack (higher memory overhead)	Typically uses less memory
Code Clarity	Often more elegant and readable for certain problems	May be more straightforward for simple problems
Performance	Can be slower due to function call overhead	Usually faster
Stack Overflow Risk	Possible with deep recursion	Not an issue
Best For	Tree traversals, divide-and-conquer algorithms	Simple loops, performance-critical code