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 list
        class Stack:
        def __init__(self):
        self.items = []
        # Add element to top of stack
        def push(self, element):
        self.items.append(element)

        # Remove and return the top element
        def pop(self):
        if self.is_empty():
        return "Underflow - Stack is empty"
        return self.items.pop()

        # Return the top element without removing it
        def peek(self):
        if self.is_empty():
        return "Stack is empty"
        return self.items[-1]

        # Check if stack is empty
        def is_empty(self):
        return len(self.items) == 0

        # Return the size of the stack
        def size(self):
        return len(self.items)

        # Clear the stack
        def clear(self):
        self.items = []

        # Usage example
        stack = Stack()
        stack.push(10)
        stack.push(20)
        stack.push(30)
        print(stack.peek()) # 30
        print(stack.pop()) # 30
        print(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 list
      class Queue:
      def __init__(self):
      self.items = []

      # Add element to the end of the queue
      def enqueue(self, element):
      self.items.append(element)

      # Remove and return the front element
      def dequeue(self):
      if self.is_empty():
      return "Underflow - Queue is empty"
      return self.items.pop(0)

      # Return the front element without removing it
      def front(self):
      if self.is_empty():
      return "Queue is empty"
      return self.items[0]

      # Check if queue is empty
      def is_empty(self):
      return len(self.items) == 0

      # Return the size of the queue
      def size(self):
      return len(self.items)

      # Clear the queue
      def clear(self):
      self.items = # Usage example
      queue = Queue()
      queue.enqueue(10 queue.enqueue(20 queue.enqueue(30)
      print(queue.front()) # 10
      print(queue.dequeue()) # 10
      print(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:
      def __init__(self):
      self.items = {}
      self.front_index = 0
      self.back_index = 0

      def enqueue(self, element):
      self.items[self.back_index] = element
      self.back_index += 1

      def dequeue(self):
      if self.is_empty():
      return "Underflow - Queue is empty"

      item = self.items[self.front_index]
      del self.items[self.front_index]
      self.front_index += 1
      return item

      def front(self):
      if self.is_empty():
      return "Queue is empty"
      return self.items[self.front_index]

      def is_empty(self):
      return self.back_index - self.front_index == 0

      def size(self):
      return self.back_index - self.front_index
    

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