Why Stack Exists and What Problems It Solves in DSA Java - Why This Pattern

Mental Model

A stack is a simple way to keep track of things in order, where the last thing you put in is the first thing you take out.

Analogy: Imagine a stack of plates in your kitchen: you always add a new plate on top and take the top plate off first when you need one.

Top -> [Plate3] -> [Plate2] -> [Plate1] -> Bottom
          ↑

Dry Run Walkthrough

Input: Operations: push 1, push 2, push 3, pop, push 4

Goal: Show how stack adds and removes items in last-in-first-out order

Step 1: push 1 onto stack

Top -> [1] -> Bottom
          ↑

Why: Start with one item on the stack

Step 2: push 2 onto stack

Top -> [2] -> [1] -> Bottom
          ↑

Why: New item goes on top, above previous items

Step 3: push 3 onto stack

Top -> [3] -> [2] -> [1] -> Bottom
          ↑

Why: Keep adding items on top, last added is on top

Step 4: pop top item (3) from stack

Top -> [2] -> [1] -> Bottom
          ↑

Why: Remove the last added item first (LIFO)

Step 5: push 4 onto stack

Top -> [4] -> [2] -> [1] -> Bottom
          ↑

Why: Add new item on top again

Result:

Top -> [4] -> [2] -> [1] -> Bottom
          ↑

Annotated Code

DSA Java

import java.util.Stack;

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

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

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

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

        // Step 4: pop top (3)
        int popped = stack.pop(); // remove top item

        // Step 5: push 4
        stack.push(4); // add 4 on top

        // Print stack from top to bottom
        System.out.print("Top -> ");
        for (int i = stack.size() - 1; i >= 0; i--) {
            System.out.print("[" + stack.get(i) + "] -> ");
        }
        System.out.println("Bottom");
    }
}

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

push adds item on top of stack

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

push adds item on top of stack

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

push adds item on top of stack

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

pop removes the last added item (top)

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

push adds item on top of stack

Output

Top -> [4] -> [2] -> [1] -> Bottom

Complexity Analysis

Time: O(1) for push and pop because these operations only add or remove the top item without scanning the whole stack

Space: O(n) because the stack stores all pushed items until they are popped

vs Alternative: Compared to using an array where removing the last item might require shifting elements, stack operations are faster and simpler because they only work at one end

Edge Cases

pop from empty stack

throws EmptyStackException to signal no items to remove

DSA Java

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

When to Use This Pattern

When you see a problem needing last-in-first-out order like undo actions or matching brackets, reach for the stack pattern because it naturally handles these with simple push/pop operations.

Common Mistakes

Mistake: Trying to remove items from the bottom of the stack instead of the top
Fix: Always use pop to remove the top item, never try to access or remove items deeper in the stack

Summary

A stack stores items so the last one added is the first one removed.

Use a stack when you need to reverse order or track things in last-in-first-out style.

The key insight is that stacks only add or remove from one end, making these operations very fast and simple.

Practice

1. Why do we use a stack data structure in programming?

easy

A. To store large amounts of data permanently

B. To store data in random order

C. To sort numbers automatically

D. To keep track of function calls and return addresses

Solution

1. Step 1: Understand the role of stack in function calls

   Stacks help keep track of where each function should return after finishing execution, storing return addresses in order.

2. Step 2: Compare other options

   Stacks do not sort data automatically, nor store data randomly or permanently; their main use is managing function calls.

3. Final Answer:

   To keep track of function calls and return addresses -> Option D

4. Quick Check:

   Stack manages function calls = A [OK]

Hint: Stack remembers last task first, like a pile of plates [OK]

Common Mistakes:

• Thinking stack sorts data automatically
• Confusing stack with permanent storage
• Assuming stack stores data randomly

2. Which of the following is the correct way to push an element onto a stack in Java?

easy

A. stack.push(element);

B. stack.put(element);

C. stack.insert(element);

D. stack.add(element);

Solution

1. Step 1: Recall Java Stack method names

   The Java Stack class uses the method push() to add elements on top of the stack.

2. Step 2: Check other method names

   Methods like add(), insert(), or put() are not standard for Stack push operation in Java.

3. Final Answer:

   stack.push(element); -> Option A

4. Quick Check:

   Push method adds element = D [OK]

Hint: Use push() to add on top of stack in Java [OK]

Common Mistakes:

• Using add() instead of push()
• Confusing insert() with push()
• Using put() which is not a Stack method

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

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. 20
30

B. 10
20

C. 30
20

D. 30
10

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 element 30; peek() returns new top element 20 without removing it.

3. Final Answer:

   30 20 -> 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 pop() returns bottom element
• Mixing order of pushed elements

4. Identify the error in the following Java code using Stack:

Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());

medium

A. Stack underflow error at third pop()

B. No error, code runs fine

C. Syntax error in stack declaration

D. push() method is incorrect

Solution

1. Step 1: Count push and pop operations

   Two elements pushed: "A", "B"; three pop() calls made.

2. Step 2: Analyze pop() calls

   First two pop() calls remove "B" and "A"; third pop() tries to remove from empty stack causing underflow error.

3. Final Answer:

   Stack underflow error at third pop() -> Option A

4. Quick Check:

   More pops than pushes = underflow error [OK]

Hint: Pop more times than push causes error [OK]

Common Mistakes:

• Ignoring stack underflow on extra pop()
• Thinking push() syntax is wrong
• Assuming no error occurs

5. You want to reverse a string using a stack in Java. Which sequence of operations correctly achieves this?

hard

A. Push all characters, then push again to reverse

B. Push each character, then pop all to build reversed string

C. Pop each character, then push all to build reversed string

D. Peek each character, then pop all to build reversed string

Solution

1. Step 1: Understand stack reversal logic

   Pushing characters stores them in order; popping them reverses order because stack is last-in-first-out.

2. Step 2: Evaluate options

   Only pushing then popping all characters correctly reverses the string; popping before pushing or peeking does not reverse.

3. Final Answer:

   Push each character, then pop all to build reversed string -> Option B

4. Quick Check:

   Push then pop reverses string = C [OK]

Hint: Push all, then pop all to reverse order [OK]

Common Mistakes:

• Trying to pop before pushing
• Using peek instead of pop to build reversed string
• Pushing twice without popping