Stacks and Queues in Java

Introduction

Stacks and Queues are fundamental linear data structures that control the order in which elements are inserted and removed. While both are used to store collections of elements, they differ completely in their access policies:

• Stack: Follows LIFO (Last-In, First-Out).
• Queue: Follows FIFO (First-In, First-Out).

In Java, the Collections Framework provides robust, production-ready implementations for both.

1. Stacks in Java

A Stack represents a collection of elements with push and pop operations. Think of it like a stack of plates in a cafeteria: the last plate put on top is the first one removed.

Legacy java.util.Stack

Historically, Java provided the java.util.Stack class, which extends Vector. Because it is synchronized, it is thread-safe but incurs a performance penalty.

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("First");
        stack.push("Second");
        
        System.out.println(stack.pop()); // Prints "Second"
        System.out.println(stack.peek()); // Prints "First"
    }
}

The Modern Approach: Deque

The official Java documentation recommends using the Deque (Double-Ended Queue) interface instead of the legacy Stack class. The ArrayDeque implementation is faster, not synchronized, and serves as an excellent stack.

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

public class ModernStackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        while (!stack.isEmpty()) {
            System.out.println(stack.pop()); // 30, then 20, then 10
        }
    }
}

2. Queues in Java

A Queue represents a collection designed for holding elements prior to processing. Think of a queue like a line of customers at a checkout counter.

The Queue interface is implemented by several classes, most notably LinkedList and PriorityQueue.

Standard Queue (LinkedList)

LinkedList implements the Queue interface and provides standard FIFO behavior.

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        
        // Enqueue
        queue.offer("Alice");
        queue.offer("Bob");
        queue.offer("Charlie");
        
        // Dequeue
        System.out.println(queue.poll()); // Prints "Alice"
        System.out.println(queue.peek()); // Prints "Bob" (without removing)
    }
}

Priority Queue

A PriorityQueue does not order elements in a FIFO manner. Instead, elements are ordered according to their natural ordering (or by a provided Comparator).

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(50);
        pq.offer(10);
        pq.offer(30);
        
        System.out.println(pq.poll()); // Prints 10 (smallest element first)
    }
}

3. Double-Ended Queues (Deque)

The Deque interface combines the functionality of both Stacks and Queues, allowing insertion and removal at both ends.

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

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        
        deque.addFirst("Front");
        deque.addLast("Back");
        
        System.out.println(deque.removeFirst()); // Prints "Front"
        System.out.println(deque.removeLast());  // Prints "Back"
    }
}

Summary

• Use ArrayDeque when you need a Stack (LIFO) or a simple Queue (FIFO). It is faster than Stack and LinkedList.
• Use LinkedList if you are heavily inserting/removing from the middle of the collection (though for strict queue operations, ArrayDeque is still preferred).
• Use PriorityQueue when you need to process elements based on priority rather than insertion order.
• Avoid the legacy java.util.Stack unless working with old codebases or if thread-safety is strictly required without using Collections.synchronizedCollection.