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 (Java)
        public class Stack {
        private List<Integer> items = new ArrayList<>();

        // Add element to top of stack
        public void push(int element) {
        items.add(element);
        }

        // Remove and return the top element
        public Integer pop() {
        if (isEmpty()) {
        System.out.println("Underflow - Stack is empty");
        return null;
        }
        return items.remove(items.size() - 1);
        }

        // Return the top element without removing it
        public Integer peek() {
        if (isEmpty()) {
        System.out.println("Stack is empty");
        return null;
        }
        return items.get(items.size() - 1);
        }

        // Check if stack is empty
        public boolean isEmpty() {
        return items.isEmpty();
        }

        // Return the size of the stack
        public int size() {
        return items.size();
        }

        // Clear the stack
        public void clear() {
        items.clear();
        }
        }

        // Usage example
        public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek()); // 30
        System.out.println(stack.pop()); // 30
        System.out.println(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 (Java)
      public class Queue {
      private List<Integer> items = new ArrayList<>();

      // Add element to the end of the queue
      public void enqueue(int element) {
      items.add(element);
      }

      // Remove and return the front element
      public Integer dequeue() {
      if (isEmpty()) {
      System.out.println("Underflow - Queue is empty");
      return null;
      }
      return items.remove(0);
      }

      // Return the front element without removing it
      public Integer front() {
      if (isEmpty()) {
      System.out.println("Queue is empty");
      return null;
      }
      return items.get(0);
      }

      // Check if queue is empty
      public boolean isEmpty() {
      return items.isEmpty();
      }

      // Return the size of the queue
      public int size() {
      return items.size();
      }

      // Clear the queue
      public void clear() {
      items.clear();
      }
      }

      // Usage example
      public static void main(String[] args) {
      Queue queue = new Queue();
      queue.enqueue(10);
      queue.enqueue(20);
      queue.enqueue(30);
      System.out.println(queue.front()); // 10
      System.out.println(queue.dequeue()); // 10
      System.out.println(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