Deque & Stack

ArrayDeque

ArrayDeque is a resizable array implementation of the Deque interface. It is more efficient than LinkedList for stack and queue operations due to better cache locality.

Key characteristics:

Resizable circular array
O(1) for add/remove at both ends
Not synchronized
No capacity restrictions (grows as needed)
Faster than LinkedList for stack/queue

import java.util.*;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        // Creating ArrayDeque
        Deque<String> deque = new ArrayDeque<>();

        // Adding elements
        deque.addFirst("B");  // [B]
        deque.addLast("C");   // [B, C]
        deque.addFirst("A");  // [A, B, C]
        deque.addLast("D");   // [A, B, C, D]
        System.out.println("Deque: " + deque);

        // Accessing elements
        System.out.println("First: " + deque.getFirst()); // A
        System.out.println("Last: " + deque.getLast()); // D
        System.out.println("peekFirst: " + deque.peekFirst()); // A
        System.out.println("peekLast: " + deque.peekLast()); // D

        // Removing elements
        System.out.println("removeFirst: " + deque.removeFirst()); // A
        System.out.println("removeLast: " + deque.removeLast()); // D
        System.out.println("After removes: " + deque); // [B, C]

        // Adding with offer (queue-style)
        deque.offer("E");   // addLast
        deque.offerFirst("F"); // addFirst
        System.out.println("After offers: " + deque); // [F, B, C, E]

        // Removing with poll (queue-style)
        System.out.println("poll: " + deque.poll()); // F (removeFirst)
        System.out.println("pollLast: " + deque.pollLast()); // E
        System.out.println("After polls: " + deque); // [B, C]

        // Size and emptiness
        System.out.println("Size: " + deque.size());
        System.out.println("isEmpty: " + deque.isEmpty());
        System.out.println("Contains B: " + deque.contains("B"));

        // Iterating
        System.out.println("\nForward:");
        for (String s : deque) {
            System.out.print(s + " ");
        }
        System.out.println("\nBackward:");
        Iterator<String> rit = deque.descendingIterator();
        while (rit.hasNext()) {
            System.out.print(rit.next() + " ");
        }
        System.out.println();
    }
}

Internal implementation: ArrayDeque uses a circular array with two pointers (head and tail). When elements are added/removed, the pointers wrap around the array using modular arithmetic. The array doubles in size when full.

Stack Operations

Stack Operations with ArrayDeque

ArrayDeque implements LIFO (Last-In-First-Out) stack operations using push, pop, and peek.

import java.util.*;

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

        // push - add to top (front)
        stack.push(10);  // [10]
        stack.push(20);  // [20, 10]
        stack.push(30);  // [30, 20, 10]
        System.out.println("Stack: " + stack);

        // peek - view top without removing
        System.out.println("Peek: " + stack.peek()); // 30
        System.out.println("Size after peek: " + stack.size()); // 3

        // pop - remove from top
        System.out.println("Pop: " + stack.pop()); // 30
        System.out.println("Pop: " + stack.pop()); // 20
        System.out.println("After pops: " + stack); // [10]

        // isEmpty - check if empty
        System.out.println("isEmpty: " + stack.isEmpty()); // false

        // Practical: Balanced parentheses
        System.out.println("\nBalanced: " + isBalanced("((()))")); // true
        System.out.println("Balanced: " + isBalanced("(()")); // false
        System.out.println("Balanced: " + isBalanced("{[()]}") ); // true
        System.out.println("Balanced: " + isBalanced("([)]")); // false

        // Practical: Reverse a string using stack
        System.out.println("Reversed: " + reverseString("Hello")); // olleH

        // Practical: Evaluate postfix expression
        System.out.println("Postfix: " + evaluatePostfix("3 4 + 2 *")); // 14
    }

    public static boolean isBalanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static String reverseString(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            stack.push(c);
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    public static int evaluatePostfix(String expr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : expr.split(" ")) {
            switch (token) {
                case "+": stack.push(stack.pop() + stack.pop()); break;
                case "-": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a - b); break;
                }
                case "*": stack.push(stack.pop() * stack.pop()); break;
                default: stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

Key difference from Stack class: ArrayDeque's push/pop operate on the front (head) of the deque, which is O(1). The old java.util.Stack class is synchronized and slower.

Queue Operations

Queue Operations with ArrayDeque

ArrayDeque implements FIFO (First-In-First-Out) queue operations.

import java.util.*;

public class QueueOperationsDemo {
    public static void main(String[] args) {
        // ArrayDeque as Queue
        Queue<String> queue = new ArrayDeque<>();

        // offer - add to back (tail)
        queue.offer("Job1");
        queue.offer("Job2");
        queue.offer("Job3");
        System.out.println("Queue: " + queue); // [Job1, Job2, Job3]

        // peek - view front without removing
        System.out.println("Peek: " + queue.peek()); // Job1
        System.out.println("Size after peek: " + queue.size()); // 3

        // poll - remove from front
        System.out.println("Poll: " + queue.poll()); // Job1
        System.out.println("Poll: " + queue.poll()); // Job2
        System.out.println("After polls: " + queue); // [Job3]

        // offerFirst, offerLast - explicit ends
        Deque<String> deque = new ArrayDeque<>();
        deque.offerFirst("Front");
        deque.offerLast("Back");
        System.out.println("Deque: " + deque); // [Front, Back]

        // pollFirst, pollLast - remove from specific end
        System.out.println("pollFirst: " + deque.pollFirst()); // Front
        System.out.println("pollLast: " + deque.pollLast()); // Back

        // Practical: BFS using queue
        System.out.println("\nBFS traversal:");
        bfs(new int[][]{{1,2},{3,4},{5,6}}, 0);

        // Practical: Sliding window maximum
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println("\nSliding window max (k=3): " + 
            Arrays.toString(slidingWindowMax(arr, 3)));
    }

    // BFS traversal
    public static void bfs(int[][] graph, int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[graph.length];
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

    // Sliding window maximum
    public static int[] slidingWindowMax(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

Queue method summary:

offer(e) / add(e) — insert at tail
poll() / remove() — remove from head
peek() / element() — view head
All have O(1) time complexity in ArrayDeque

vs Stack

ArrayDeque vs Stack Class

Java has a legacy Stack class, but ArrayDeque is the recommended replacement.

Aspect	ArrayDeque	Stack
Synchronization	No (faster)	Yes (slower)
Implements	Deque interface	Vector + Stack
Performance	O(1) for all ops	O(1) but synchronized
Thread safety	No	Yes
Flexibility	Stack + Queue	Stack only

import java.util.*;

public class ArrayDequeVsStackDemo {
    public static void main(String[] args) {
        // Legacy Stack class (avoid)
        Stack<Integer> legacyStack = new Stack<>();
        legacyStack.push(1);
        legacyStack.push(2);
        legacyStack.push(3);
        System.out.println("Stack peek: " + legacyStack.peek()); // 3
        System.out.println("Stack pop: " + legacyStack.pop()); // 3
        System.out.println("Stack: " + legacyStack); // [1, 2]

        // Recommended: ArrayDeque
        Deque<Integer> modernStack = new ArrayDeque<>();
        modernStack.push(1);
        modernStack.push(2);
        modernStack.push(3);
        System.out.println("Deque peek: " + modernStack.peek()); // 3
        System.out.println("Deque pop: " + modernStack.pop()); // 3
        System.out.println("Deque: " + modernStack); // [1, 2]

        // ArrayDeque also works as Queue
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println("\nQueue poll: " + queue.poll()); // 1

        // Why ArrayDeque is better:
        System.out.println("\n--- Why ArrayDeque is better ---");
        System.out.println("1. Not synchronized - better performance");
        System.out.println("2. Implements Deque - can be stack AND queue");
        System.out.println("3. Better cache locality than LinkedList");
        System.out.println("4. No capacity limit (grows dynamically)");
        System.out.println("5. Part of modern Collections Framework");

        // Performance comparison
        long start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            legacyStack.push(i);
            legacyStack.pop();
        }
        long stackTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            modernStack.push(i);
            modernStack.pop();
        }
        long dequeTime = System.nanoTime() - start;

        System.out.println("\n1M push/pop - Stack: " + stackTime / 1_000_000 + "ms");
        System.out.println("1M push/pop - ArrayDeque: " + dequeTime / 1_000_000 + "ms");
    }
}

Rule: Never use java.util.Stack. Always use ArrayDeque for stack operations. It is faster, more flexible, and follows modern Java conventions.

Practice Problems

0/3solved

intermediateValid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid using ArrayDeque as a stack.

Solution

import java.util.*;

public class ValidParentheses {
    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

intermediateImplement Queue Using Two Stacks

Implement a queue using two ArrayDeque instances as stacks.

Solution

import java.util.*;

public class QueueUsingStacks {
    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    public QueueUsingStacks() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }

    public void enqueue(int x) {
        stack1.push(x);
    }

    public int dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

intermediateReverse a Queue

Write a method to reverse a queue using ArrayDeque as a stack.

Solution

import java.util.*;

public class QueueReverser {
    public static <T> Queue<T> reverse(Queue<T> queue) {
        Deque<T> stack = new ArrayDeque<>();
        while (!queue.isEmpty()) {
            stack.push(queue.poll());
        }
        Queue<T> reversed = new ArrayDeque<>();
        while (!stack.isEmpty()) {
            reversed.offer(stack.pop());
        }
        return reversed;
    }
}

Flashcards

Question

Why is ArrayDeque preferred over Stack class?

Click to reveal answer

Answer

ArrayDeque is not synchronized (faster), implements Deque interface (stack + queue), has better cache locality, and is the modern replacement for Stack. Never use java.util.Stack.

Question

What methods does ArrayDeque provide for stack operations?

Click to reveal answer

Answer

push(e) adds to front, pop() removes from front, peek() views front. All are O(1). The front of the deque is the top of the stack.

Question

What is a circular array and how does ArrayDeque use it?

Click to reveal answer

Answer

A circular array wraps around when it reaches the end. ArrayDeque uses head and tail pointers with modular arithmetic to efficiently add/remove at both ends without shifting elements.

Question

What is ArrayDeque as Stack and Queue?

Click to reveal answer

Answer

ArrayDeque as Stack and Queue is a key concept in Java programming.

Question

When to use ArrayDeque as Stack and Queue?

Click to reveal answer

Answer

Use ArrayDeque as Stack and Queue when building production systems that require reliability, scalability, and maintainability.

Revision Notes

Key Takeaways

1.ArrayDeque is the recommended replacement for Stack class
2.It provides O(1) operations at both ends
3.Works as both stack (LIFO) and queue (FIFO)
4.Better cache locality than LinkedList for stack/queue operations

Interview Tips

•Always use ArrayDeque instead of Stack in interviews
•Explain the circular array internal implementation
•Know the difference between push/pop (stack) and offer/poll (queue)
•Be ready to implement a queue using two stacks

Cheat Sheet

ArrayDeque Cheat Sheet

Structure

Resizable circular array
O(1) add/remove at both ends
Not synchronized

Stack Operations

push(e) → addFirst
pop() → removeFirst
peek() → peekFirst

Queue Operations

offer(e) → addLast
poll() → removeFirst
peek() → peekFirst

Deque Operations

addFirst/addLast → O(1)
removeFirst/removeLast → O(1)
peekFirst/peekLast → O(1)

vs Stack

ArrayDeque: not synchronized, faster
Stack: synchronized, slower, legacy

ArrayDeque

ArrayDeque

Stack Operations

Stack Operations with ArrayDeque

Queue Operations

Queue Operations with ArrayDeque

vs Stack

ArrayDeque vs Stack Class

Practice Problems

Quiz

Flashcards

Revision Notes

Key Takeaways

Interview Tips

Cheat Sheet

ArrayDeque Cheat Sheet

Structure

Stack Operations

Queue Operations

Deque Operations

vs Stack