Introduction

Arrays and Linked Lists are highly flexible — you can insert, read, or delete elements from anywhere. But sometimes, too much flexibility leads to chaos. We often want to strictly control how data enters and leaves our system to ensure predictability.

This is where Stacks and Queues come in. They are essentially restricted wrappers around arrays or linked lists that enforce specific rules on insertion and deletion.

Stacks — LIFO (Last In, First Out)

How It Works

Think of a stack of plates in a cafeteria. You can only put a new plate on the top of the stack. When you need a plate, you take the one from the top. The last plate added is the very first one removed. This behaviour is called LIFO (Last In, First Out).

Core Operations

Real-World Applications

• Undo functionality in text editors (Ctrl+Z goes back to the most recent action).
• Browser history (the “Back” button takes you to the last page visited).
• Function call stack in programming languages (this is why recursion works!).
• Validating parentheses in code editors (matching {,[,().

Java Implementation

Historically, Java provided a java.util.Stack class, but it extends Vector and is synchronised (meaning it is slow and outdated). The modern, recommended way to use a stack in Java is using the Deque (Double Ended Queue) interface, specifically the ArrayDeque implementation.

import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        // Use Deque as a Stack
        Deque<String> stack = new ArrayDeque<>();

        // Push: add to the top
        stack.push("Page 1 (Home)");
        stack.push("Page 2 (About)");
        stack.push("Page 3 (Contact)");

        // Peek: look at the top item
        System.out.println("Top of stack: " + stack.peek()); // Page 3 (Contact)

        // Pop: remove from the top
        System.out.println("Popped: " + stack.pop()); // Page 3 (Contact)
        System.out.println("Popped: " + stack.pop()); // Page 2 (About)

        System.out.println("Is stack empty? " + stack.isEmpty()); // false
        System.out.println("Top of stack: " + stack.peek()); // Page 1 (Home)
    }
}

Queues — FIFO (First In, First Out)

How It Works

Think of a line of people waiting at a supermarket checkout. The first person to join the line is the first person to be served. New people join at the back. This behaviour is called FIFO (First In, First Out).

Core Operations

Note: In Java, add() and remove() throw exceptions if the queue is full/empty, while offer() and poll() return false or null. We generally prefer the safer offer and poll.

Real-World Applications

• Print queues (documents print in the order they were submitted).
• Customer support systems (first caller is routed to the first available agent).
• Thread pools and Task scheduling in operating systems.
• Breadth-First Search (BFS) on Graph Algorithms.

Java Implementation

Java provides the Queue interface. Like the stack, we typically use ArrayDeque or LinkedList as the implementation.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // Use LinkedList as a Queue
        Queue<String> queue = new LinkedList<>();

        // Offer (Enqueue): add to the back of the line
        queue.offer("Customer 1 (Alice)");
        queue.offer("Customer 2 (Bob)");
        queue.offer("Customer 3 (Charlie)");

        // Peek: look at the front of the line
        System.out.println("Next to be served: " + queue.peek()); // Customer 1 (Alice)

        // Poll (Dequeue): remove from the front of the line
        System.out.println("Served: " + queue.poll()); // Customer 1 (Alice)
        System.out.println("Served: " + queue.poll()); // Customer 2 (Bob)

        System.out.println("Is queue empty? " + queue.isEmpty()); // false
        System.out.println("Next to be served: " + queue.peek()); // Customer 3 (Charlie)
    }
}

Summary Comparison

Practice Problems

1. Valid Parentheses – LeetCode #20 — The ultimate classic Stack problem. Use a stack to match opening and closing brackets perfectly.
2. Implement Queue using Stacks – LeetCode #232 — A great thought exercise. Can you simulate FIFO behaviour using only two LIFO stacks?
3. Number of Recent Calls – LeetCode #933 — A perfect use case for a Queue holding timestamps.

What’s Next?

We just saw how to manage sequential data perfectly. But what if we want to store key-value pairs and look them up instantly without searching sequentially? For that, we turn to one of the most powerful data structures ever created: Hash Tables & Hashing.