Coding Patterns + Java Collections

When to use Deque vs Stack

In modern Java, Deque with ArrayDeque is usually preferred over the legacy Stack class. Deque can behave like a stack, a queue, or a true double-ended queue.

DequeStackQueueArrayDequeJava

The Short Answer

In modern Java, prefer Deque, usually ArrayDeque, instead of the old Stack class.

Stack = last-in-first-out only.
Deque = double-ended queue that can act like a stack or a queue.

The practical interview answer is: use ArrayDeque for stack-like problems unless you specifically need something else.

What Is a Stack?

A stack is LIFO: last in, first out.

top: 30

pop() removes 30 first because it was added last.

java

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

stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.pop()); // 30
System.out.println(stack.pop()); // 20
System.out.println(stack.pop()); // 10

What Is a Deque?

A deque means double-ended queue. You can add or remove elements from both ends.

addFirst()

addLast()

A deque gives you access to both the front and the back.

java

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

deque.addFirst(20);
deque.addFirst(10);
deque.addLast(30);

System.out.println(deque); // [10, 20, 30]

Deque Can Behave Like a Stack

If you use push, pop, and peek, a Deque behaves like a stack.

java

Deque<String> stack = new ArrayDeque<>();

stack.push("A");
stack.push("B");
stack.push("C");

System.out.println(stack.peek()); // C
System.out.println(stack.pop());  // C
System.out.println(stack.pop());  // B

For coding interviews, this is usually the cleanest Java stack pattern:

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

Deque Can Also Behave Like a Queue

If you use offer and poll, a Deque can behave like a regular FIFO queue.

java

Deque<String> queue = new ArrayDeque<>();

queue.offer("A");
queue.offer("B");
queue.offer("C");

System.out.println(queue.poll()); // A
System.out.println(queue.poll()); // B
System.out.println(queue.poll()); // C

Same data structure, different method style.

Why Not Use Stack?

Java has a class named Stack, but it is considered legacy. In modern Java, Deque is usually preferred.

Stack

Old class. Extends Vector. Usually avoided in modern Java interview code.

ArrayDeque

Modern choice for stack-like and queue-like operations.

java

// Avoid in modern interview code
Stack<Integer> stack = new Stack<>();

// Prefer this
Deque<Integer> stack = new ArrayDeque<>();

Method Cheat Sheet

Use Case	Operation	Deque Method
Stack	Push top	push(e)
Stack	Pop top	pop()
Stack	View top	peek()
Queue	Add back	offer(e)
Queue	Remove front	poll()
Deque	Add front	addFirst(e)
Deque	Add back	addLast(e)

Example: Valid Parentheses

This is a classic stack problem. Every time we see an opening bracket, we push it. Every time we see a closing bracket, we pop and check whether it matches.

java

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

public class ValidParentheses {
    public static void main(String[] args) {
        System.out.println(isValid("()[]{}")); // true
        System.out.println(isValid("(]"));     // false
    }

    static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;

                char open = stack.pop();

                if (ch == ')' && open != '(') return false;
                if (ch == ']' && open != '[') return false;
                if (ch == '}' && open != '{') return false;
            }
        }

        return stack.isEmpty();
    }
}

Example: Sliding Window With Deque

Deque is also useful when you need to remove from both ends, such as in sliding window problems.

java

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

deque.addLast(10);
deque.addLast(20);
deque.addLast(30);

System.out.println(deque.removeFirst()); // 10
System.out.println(deque.removeLast());  // 30

This ability to work from both sides is why Deque appears in monotonic queue and sliding window maximum problems.

When Should You Use Which?

Use Deque as a stack

DFS, backtracking, valid parentheses, monotonic stack, next greater element.

Use Deque as a queue

BFS, level-order traversal, normal FIFO processing.

Use both ends

Sliding window maximum, monotonic queue, palindrome-style processing.

Avoid Stack

In modern Java, prefer ArrayDeque unless you specifically need legacy Stack behavior.

Common LeetCode Problems

These are some problems with the data structure to use:

Valid Parentheses - Stack (Deque)
Min Stack - Stack (Deque)
Daily Temperatures - Monotonic Stack (Decreasing)
Next Greater Element - Monotonic Stack (Decreasing)
Sliding Window Maximum - Monotonic Queue (Deque)
Binary Tree Level Order Traversal - Queue (BFS)
Evaluate Reverse Polish Notation - Stack (Deque)
Remove K Digits - Monotonic Stack (Increasing)

Common Interview Follow-Ups

Is Deque the same as Stack?

No. Deque is more general. It can behave like a stack, a queue, or a double-ended queue.

Why prefer ArrayDeque over Stack?

Stack is a legacy class. ArrayDeque is the modern common choice for stack-like behavior in Java.

Is ArrayDeque thread-safe?

No. ArrayDeque is not thread-safe. If multiple threads access it concurrently, you need external synchronization or a concurrent collection.

Can ArrayDeque store null?

No. ArrayDeque does not allow null elements.

What is the main mental model?

Use one end for stack behavior, use offer/poll for queue behavior, and use both ends when a problem needs flexible front/back removal.

Final Takeaway

In modern Java interview code, reach for Deque with ArrayDeque. Use it like a stack with push/pop, like a queue with offer/poll, and like a true deque when you need both ends.