Implement Stack using Deque

The problem, simply

A stack is a pile: the last thing you put on is the first thing you take off. You must build one with four moves: push(x) puts x on top, pop() takes the top off and gives it back, top() tells you the top without taking it, and empty() says if the pile is empty.

The only tool you may use inside is a deque. A deque is a tube with a door at each end. You can put things in or take things out at the front door or the back door, and each of those moves is fast.

A story to remember it

Picture it

Examples

Way 1: the simple way

The first idea many people have is a plain list where the top lives at position 0, the front of the list. It feels natural to read the top first.

1. push(x): insert x at position 0. Every other item must slide one step right to make room.
2. pop(): remove the item at position 0. Every other item slides one step left.
3. top(): read position 0.
4. empty(): check if the list size is 0.

import java.util.*;

class MyStack {
    private final List<Integer> list = new ArrayList<>();

    public void push(int x) {
        list.add(0, x);              // everybody slides right to make room
    }

    public int pop() {
        if (list.isEmpty()) throw new RuntimeException("stack is empty");
        return list.remove(0);       // everybody slides left to fill the gap
    }

    public int top() {
        if (list.isEmpty()) throw new RuntimeException("stack is empty");
        return list.get(0);
    }

    public boolean empty() {
        return list.isEmpty();
    }
}

How long it takes: push and pop slide every item, so each one costs O(n) when the stack holds n items. top and empty are O(1). Extra room: the list holds the items, O(n). It works, but it is slow for a big pile.

Way 2: the clever way

Use the deque and pick one door. We pick the back door. The back of the deque is the top of the stack.

1. push(x): addLast(x), put it in at the back.
2. pop(): removeLast(), take it out from the back.
3. top(): peekLast(), look at the back.
4. empty(): isEmpty().

Nothing ever slides, because a deque can open either door in one step.

import java.util.*;

class MyStack {
    private final Deque<Integer> dq = new ArrayDeque<>();

    public void push(int x) {
        dq.addLast(x);               // in through the back door
    }

    public int pop() {
        if (dq.isEmpty()) throw new RuntimeException("stack is empty");
        return dq.removeLast();      // out through the same door
    }

    public int top() {
        if (dq.isEmpty()) throw new RuntimeException("stack is empty");
        return dq.peekLast();        // look, do not take
    }

    public boolean empty() {
        return dq.isEmpty();
    }

    public int size() {
        return dq.size();
    }
}

How long it takes: each move touches one door once, so every operation is O(1). Extra room: the deque holds the n items, O(n). Using the front door for everything (addFirst, removeFirst, peekFirst) works just as well. What matters is that push and pop use the same door.

Watch out for

• Popping or peeking an empty stack. removeLast() throws and peekLast() returns null, which crashes when unboxed to int. Check empty() first or throw a clear error.
• ArrayDeque does not allow null items. If your stack must hold null, use LinkedList as the deque.
• Java's old Stack class works but is slow because every method is locked for threads. Interviewers like to hear that ArrayDeque is the modern choice.

What interviewers ask next

• Can a deque also act as a queue? Yes. Put things in at the back and take them out at the front. One deque can be a stack or a queue depending on which doors you use.
• How would you build the deque itself? Use a circular array with a head index and a tail index that wrap around, and double the array when it is full. Each move stays O(1) on average.
• Add getMin() in O(1). Keep a second deque that stores the smallest value so far next to every push, and pop it together with the main one.
• What is the cost when the array inside the deque grows? A single push can cost O(n) while copying, but doubling makes it rare, so the average stays O(1). This is called amortized time.

Remember this

Grown-up words: the pile is a stack (last in, first out), the tube with two doors is a deque (double ended queue), the back door is addLast and removeLast, and "fast on average even with rare big copies" is amortized O(1).