6. Stack, Queue & Deque

Note

Why this matters for DSA Linear structures like Stacks and Queues control the ordering of element processing. Stacks (LIFO) are the backbone of recursion, graph DFS, and parentheses matching. Queues (FIFO) power graph BFS. Deques (Double-ended queues) are essential for sliding windows. PriorityQueues (Heaps) unlock optimal solutions for top-K elements, merging sorted streams, and Dijkstra's algorithm.

6.1 Stack (LIFO - Last In, First Out)

A stack is a linear data structure where elements are added and removed from the same end (the top).

Warning

Do NOT use java.util.Stack Java has a legacy Stack class, but it is deprecated for general use. It extends Vector and uses thread synchronization internally, which introduces unnecessary performance overhead. Instead: Use ArrayDeque as your Stack implementation.

java

import java.util.ArrayDeque;

ArrayDeque<Integer> stack = new ArrayDeque<>();

// 1. Push - add to top
stack.push(10);
stack.push(20);

// 2. Peek - look at top element without removing
int top = stack.peek(); // 20

// 3. Pop - remove and return top element
int removed = stack.pop(); // 20

// 4. Auxiliary check
boolean empty = stack.isEmpty(); // false
int size = stack.size(); // 1

6.2 Queue (FIFO - First In, First Out)

A queue is a linear structure where elements are added at the back (enqueue) and removed from the front (dequeue).

In Java, Queue is an interface. You must instantiate it using a concrete class, typically ArrayDeque (preferred for performance) or LinkedList.

java

import java.util.Queue;
import java.util.ArrayDeque;

Queue<Integer> queue = new ArrayDeque<>();

// 1. Enqueue - add to back
queue.offer(10);
queue.offer(20);

// 2. Peek - view front element without removing
int front = queue.peek(); // 10

// 3. Dequeue - remove and return front element
int removed = queue.poll(); // 10

Queue Method Comparisons

Java queues provide two sets of methods for access. One set throws exceptions on failure (like capacity limits or empty states), while the other returns special values (false or null). Always prefer the special value set for DSA.

Operation	Throws Exception	Returns Special Value (Preferred)
Insert	`add(e)`	`offer(e)` (returns `false` if full)
Remove	`remove()`	`poll()` (returns `null` if empty)
Examine	`element()`	`peek()` (returns `null` if empty)

6.3 Deque (Double-Ended Queue)

A Deque (pronounced "deck") allows you to insert and remove elements from both the front and the back. It serves as a generalized stack and queue.

java

import java.util.ArrayDeque;

ArrayDeque<Integer> deque = new ArrayDeque<>();

// 1. Insert
deque.addFirst(10); // add to front
deque.addLast(20);  // add to back

// 2. Examine
int first = deque.peekFirst(); // 10
int last = deque.peekLast();   // 20

// 3. Remove
int removedFirst = deque.pollFirst(); // 10
int removedLast = deque.pollLast();   // 20

6.4 PriorityQueue (Heaps)

A PriorityQueue retrieves elements based on their priority (sorting order), rather than insertion order.

Min-Heap (default): Smallest element stays at the top.
Max-Heap: Largest element stays at the top.

java

import java.util.PriorityQueue;
import java.util.Collections;

// 1. Min-Heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(10);
minHeap.offer(5);
minHeap.offer(20);
int smallest = minHeap.poll(); // 5

// 2. Max-Heap (using reverse comparator)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(5);
maxHeap.offer(20);
int largest = maxHeap.poll(); // 20

PriorityQueue with Custom Objects

For sorting custom classes, pass a lambda expression comparator during instantiation:

java

class Pair {
    int key, value;
    Pair(int k, int v) { this.key = k; this.value = v; }
}

// Min-heap sorted by value ascending
PriorityQueue<Pair> heap = new PriorityQueue<>((a, b) -> a.value - b.value);

Complexity Summary

Operation	Stack / Queue / Deque	PriorityQueue
Insert / Push	$O(1)$	$O(\log N)$
Remove / Pop	$O(1)$	$O(\log N)$
Peek	$O(1)$	$O(1)$

Practice Drill

java

// Try implementing these:
// 1. Valid Parentheses: Given a string containing brackets '(', ')', '{', '}', '[', ']', check if the input string is valid using a Stack.
// 2. Implement a Queue using two Stacks.
// 3. Find the K largest elements in an unsorted array using a PriorityQueue (Min-Heap approach).
// 4. Implement a simple monotonic decreasing queue check: print elements of an array that are greater than all elements to their right.

💡 Click for Solutions

java

import java.util.*;

public class StackQueueDrill {
    public static void main(String[] args) {
        // 1. Valid Parentheses
        System.out.println("Is '()[{}]' valid? " + isValidParentheses("()[{}]")); // true
        System.out.println("Is '([)]' valid? " + isValidParentheses("([)]")); // false

        // 2. Queue using two Stacks
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        System.out.println("Queue Pop: " + queue.pop()); // 1

        // 3. K Largest elements
        int[] arr = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("K Largest elements: " + getKLargest(arr, k)); // [5, 6]
    }

    // 1. Valid Parentheses Solution
    public static boolean isValidParentheses(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (ch == ')' && top != '(') return false;
                if (ch == '}' && top != '{') return false;
                if (ch == ']' && top != '[') return false;
            }
        }
        return stack.isEmpty();
    }

    // 2. Queue using two Stacks Solution
    static class MyQueue {
        private ArrayDeque<Integer> s1 = new ArrayDeque<>();
        private ArrayDeque<Integer> s2 = new ArrayDeque<>();

        public void push(int x) {
            s1.push(x);
        }

        public int pop() {
            peek();
            return s2.pop();
        }

        public int peek() {
            if (s2.isEmpty()) {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }

        public boolean empty() {
            return s1.isEmpty() && s2.isEmpty();
        }
    }

    // 3. K Largest Elements Solution (Min-heap of size K)
    public static List<Integer> getKLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Keep only the K largest elements
            }
        }
        List<Integer> result = new ArrayList<>(minHeap);
        Collections.sort(result); // optional: sort result ascending
        return result;
    }
}

← Arrays & Collections | Next → Sorting & Utilities