Module 1: Stacks and Queues

Understanding Stacks

Stacks follow a Last-In-First-Out (LIFO) order, similar to a stack of blocks where you can only add or remove from the top. The most recently added item is always the first one you can remove.

Key operations include:

• push(element) - Adds an element to the top of the stack
• pop() - Removes and returns the top element
• peek() - Returns but does not remove the top element
• isEmpty() - Checks if the stack is empty

Real-world uses of stacks include:

• Undo functionality in applications
• Browser history tracking
• Function call management (call stack)
• Expression evaluation and syntax checking

Stack<String> history = new Stack<>();
history.push("edit document");
history.push("delete paragraph");
history.push("add image");

// Undo last action
String lastAction = history.pop(); // returns "add image"

Understanding Queues

Queues follow a First-In-First-Out (FIFO) order, similar to people waiting in line. The first item added to the queue will be the first one removed.

Key operations include:

• add(element) or offer(element) - Adds an element to the end of the queue
• remove() or poll() - Removes and returns the front element
• element() or peek() - Returns but does not remove the front element
• isEmpty() - Checks if the queue is empty

Real-world uses of queues include:

• Printer job processing
• Task scheduling
• Request handling in web servers
• Breadth-first search in graph algorithms

Queue<PrintJob> printQueue = new LinkedList<>();
printQueue.add(new PrintJob("document1.pdf"));
printQueue.add(new PrintJob("photo.jpg"));
printQueue.add(new PrintJob("report.docx"));

// Process next job
PrintJob nextJob = printQueue.remove(); // returns document1.pdf job

Time and Space Complexity

Understanding the performance characteristics of stacks and queues is essential for efficient application design:

Stack Operations (using Java's Stack)

• push() - O(1) time complexity
• pop() - O(1) time complexity
• peek() - O(1) time complexity
• Space complexity - O(n) where n is the number of elements

Queue Operations (using LinkedList implementation)

• add()/offer() - O(1) time complexity
• remove()/poll() - O(1) time complexity
• peek()/element() - O(1) time complexity
• Space complexity - O(n) where n is the number of elements

These constant-time operations make stacks and queues highly efficient for their specific use cases.

Resources