Queue vs Stack When to Use Which in DSA Java - Trade-offs & Analysis

Mental Model

A stack is like a pile where you add and remove from the top only, while a queue is like a line where you add at the back and remove from the front.

Analogy: Think of a stack as a stack of plates: you put a plate on top and take the top plate off first. A queue is like a line at a store: the first person to get in line is the first to be served.

Stack (top at right): bottom -> 1 -> 2 -> 3 [top ↑]
Queue (front at left): [front ↑] 1 -> 2 -> 3 -> back

Dry Run Walkthrough

Input: Use a stack and a queue each with elements 1, 2, 3; then add 4 and remove one element

Goal: Show how adding and removing elements works differently in stack and queue

Step 1: Start with stack: push 1, push 2, push 3

Stack: bottom -> 1 -> 2 -> 3 [top ↑]
Queue: empty

Why: Stack grows by adding elements on top

Step 2: Start with queue: enqueue 1, enqueue 2, enqueue 3

Stack: bottom -> 1 -> 2 -> 3 [top ↑]
Queue: [front ↑] 1 -> 2 -> 3 -> back

Why: Queue grows by adding elements at the back

Step 3: Push 4 onto stack

Stack: bottom -> 1 -> 2 -> 3 -> 4 [top ↑]
Queue: [front ↑] 1 -> 2 -> 3 -> back

Why: Stack adds new element on top

Step 4: Enqueue 4 into queue

Stack: bottom -> 1 -> 2 -> 3 -> 4 [top ↑]
Queue: [front ↑] 1 -> 2 -> 3 -> 4 -> back

Why: Queue adds new element at the back

Step 5: Pop one element from stack

Stack: bottom -> 1 -> 2 -> 3 [top ↑]
Queue: [front ↑] 1 -> 2 -> 3 -> 4 -> back

Why: Stack removes the top element first (last in, first out)

Step 6: Dequeue one element from queue

Stack: bottom -> 1 -> 2 -> 3 [top ↑]
Queue: [front ↑] 2 -> 3 -> 4 -> back

Why: Queue removes the front element first (first in, first out)

Result:

Stack final: bottom -> 1 -> 2 -> 3 [top ↑]
Queue final: [front ↑] 2 -> 3 -> 4 -> back

Annotated Code

DSA Java

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

public class QueueVsStackDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();

        // Push 1, 2, 3 onto stack
        stack.push(1); // add 1 on top
        stack.push(2); // add 2 on top
        stack.push(3); // add 3 on top

        // Enqueue 1, 2, 3 into queue
        queue.offer(1); // add 1 at back
        queue.offer(2); // add 2 at back
        queue.offer(3); // add 3 at back

        // Push 4 onto stack
        stack.push(4); // add 4 on top

        // Enqueue 4 into queue
        queue.offer(4); // add 4 at back

        // Pop one element from stack
        int popped = stack.pop(); // remove top element

        // Dequeue one element from queue
        int dequeued = queue.poll(); // remove front element

        // Print final states
        System.out.println("Stack final: " + stackToString(stack));
        System.out.println("Queue final: " + queueToString(queue));
    }

    // Helper to print stack from bottom to top
    private static String stackToString(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append("bottom -> ");
        for (int i = 0; i < stack.size(); i++) {
            sb.append(stack.get(i));
            if (i != stack.size() - 1) sb.append(" -> ");
        }
        sb.append(" [top ↑]");
        return sb.toString();
    }

    // Helper to print queue from front to back
    private static String queueToString(Queue<Integer> queue) {
        StringBuilder sb = new StringBuilder();
        sb.append("[front ↑] ");
        int count = 0;
        int size = queue.size();
        for (int val : queue) {
            sb.append(val);
            count++;
            if (count != size) sb.append(" -> ");
        }
        sb.append(" -> back");
        return sb.toString();
    }

stack.push(1); // add 1 on top

push element onto stack -- grows top

stack.push(2); // add 2 on top

push element onto stack -- grows top

stack.push(3); // add 3 on top

push element onto stack -- grows top

queue.offer(1); // add 1 at back

enqueue element at queue back

queue.offer(2); // add 2 at back

enqueue element at queue back

queue.offer(3); // add 3 at back

enqueue element at queue back

stack.push(4); // add 4 on top

push element onto stack -- grows top

queue.offer(4); // add 4 at back

enqueue element at queue back

int popped = stack.pop(); // remove top element

pop element from stack -- removes top (LIFO)

int dequeued = queue.poll(); // remove front element

dequeue element from queue -- removes front (FIFO)

Output

Stack final: bottom -> 1 -> 2 -> 3 [top ↑]

Queue final: [front ↑] 2 -> 3 -> 4 -> back

Complexity Analysis

Time: O(1) for push/pop in stack and enqueue/dequeue in queue because these operations happen at one end only without traversal

Space: O(n) because both stack and queue store n elements explicitly

vs Alternative: Compared to arrays where adding/removing at front can be O(n), stacks and queues provide O(1) operations by restricting where changes happen

Edge Cases

Empty stack or queue

Pop or dequeue returns null or error; code uses built-in methods that handle empty gracefully

DSA Java

int popped = stack.pop(); // remove top element

Single element in stack or queue

Pop or dequeue removes the only element leaving structure empty

DSA Java

int dequeued = queue.poll(); // remove front element

When to Use This Pattern

When a problem needs last-in-first-out order, use a stack; when it needs first-in-first-out order, use a queue because their add/remove rules match these needs.

Common Mistakes

Mistake: Using stack when FIFO order is needed
Fix: Use a queue instead because it removes elements in the order they were added

Mistake: Using queue when LIFO order is needed
Fix: Use a stack instead because it removes the most recently added element first

Summary

Stack adds and removes elements from the top (last in, first out).

Use stack when you need to process the most recent item first, like undo actions.

The key insight is that stack and queue differ by where they add and remove elements, changing the order of processing.

Practice

1. Which data structure should you use when you need to process elements in the exact order they arrive, like customers waiting in line?

easy

A. Stack

B. Queue

C. Array

D. HashMap

Solution

1. Step 1: Understand the order requirement

   Processing elements in the exact order they arrive means first-in, first-out (FIFO).

2. Step 2: Match data structure behavior

   Queue follows FIFO, so it processes elements in the order they come.

3. Final Answer:

   Queue -> Option B

4. Quick Check:

   FIFO = Queue [OK]

Hint: Use Queue for first-in, first-out order [OK]

Common Mistakes:

• Confusing Stack (LIFO) with Queue (FIFO)
• Choosing Array without order guarantees
• Using HashMap which has no order

2. Which of the following is the correct way to add an element to a Stack in Java?

easy

A. stack.push(element);

B. stack.enqueue(element);

C. stack.addLast(element);

D. stack.insert(element);

Solution

1. Step 1: Recall Stack method to add elements

   In Java, Stack uses push() to add elements on top.

2. Step 2: Check other options

   enqueue() is for Queue, addLast() is for Deque, insert() is not a Stack method.

3. Final Answer:

   stack.push(element); -> Option A

4. Quick Check:

   Stack add = push() [OK]

Hint: Use push() to add elements to Stack [OK]

Common Mistakes:

• Using enqueue() which is for Queue
• Using addLast() which is for Deque
• Using insert() which does not exist in Stack

3. What will be the output of the following Java code?

import java.util.Stack;
public class Test {
  public static void main(String[] args) {
    Stack<Integer> stack = new Stack<>();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    System.out.println(stack.pop());
    System.out.println(stack.peek());
  }
}

medium

A. 30
10

B. 10
20

C. 30
20

D. 20
30

Solution

1. Step 1: Trace push operations

   Elements pushed in order: 10 (bottom), 20, 30 (top).

2. Step 2: Trace pop and peek

   pop() removes and returns top: 30. peek() returns new top without removing: 20.

3. Final Answer:

   30\n20 -> Option C

4. Quick Check:

   pop = 30, peek = 20 [OK]

Hint: pop() removes top, peek() shows top without removing [OK]

Common Mistakes:

• Confusing pop() and peek() results
• Assuming FIFO order instead of LIFO
• Mixing push order with pop output

4. Identify the error in this Java code snippet using a Queue:

import java.util.Queue;
import java.util.LinkedList;
public class Test {
  public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();
    queue.push(5);
    queue.add(10);
    System.out.println(queue.poll());
  }
}

medium

A. Queue interface has no push() method

B. LinkedList cannot be used as Queue

C. poll() does not remove elements

D. add() method is invalid for Queue

Solution

1. Step 1: Check Queue methods

   Queue interface does not have push() method; push() is for Stack.

2. Step 2: Validate other methods

   LinkedList can be used as Queue, poll() removes and returns head, add() is valid for Queue.

3. Final Answer:

   Queue interface has no push() method -> Option A

4. Quick Check:

   Queue push() invalid [OK]

Hint: Queue uses add(), not push() [OK]

Common Mistakes:

• Using push() on Queue instead of add()
• Thinking poll() does not remove element
• Believing LinkedList can't implement Queue

5. You need to design a system that tracks the most recent 5 user actions to allow undo operations. Which data structure is best and why?

hard

A. Queue, because it processes actions in order

B. HashMap, because it stores actions with keys

C. ArrayList, because it allows random access

D. Stack, because it reverses the order for undo

Solution

1. Step 1: Understand undo operation behavior

   Undo requires reversing the order of actions: last action undone first.

2. Step 2: Match data structure to behavior

   Stack follows last-in, first-out (LIFO), perfect for undo functionality.

3. Final Answer:

   Stack, because it reverses the order for undo -> Option D

4. Quick Check:

   Undo = LIFO = Stack [OK]

Hint: Undo needs LIFO order, so use Stack [OK]

Common Mistakes:

• Choosing Queue which is FIFO, not suitable for undo
• Using HashMap which has no order
• Thinking ArrayList automatically reverses order