Stack Implementation Using Array in DSA Java

Mental Model

A stack is like a pile where you add and remove items only from the top. Using an array means we keep track of the top position with a number.

Analogy: Imagine a stack of plates. You can only put a new plate on top or take the top plate off. The array is like a shelf with fixed spots, and the top number tells you where the last plate is.

Array: [ _ , _ , _ , _ , _ ]
Top index: -1 (empty stack)

Dry Run Walkthrough

Input: Push 10, Push 20, Pop, Push 30 on an empty stack of size 5

Goal: Show how the stack changes after each push and pop operation using an array

Step 1: Push 10 onto stack

Array: [10, _ , _ , _ , _ ]
Top index: 0 ↑

Why: We add 10 at the first position and update top to 0

Step 2: Push 20 onto stack

Array: [10, 20, _ , _ , _ ]
Top index: 1 ↑

Why: We add 20 at next position and move top to 1

Step 3: Pop top element

Array: [10, 20, _ , _ , _ ]
Top index: 0 ↑ (20 is removed logically)

Why: We remove 20 by moving top back to 0, 20 is ignored

Step 4: Push 30 onto stack

Array: [10, 30, _ , _ , _ ]
Top index: 1 ↑

Why: We add 30 at position 1 and update top to 1

Result:

Array: [10, 30, _ , _ , _ ]
Top index: 1 ↑
Stack content: 10 -> 30 -> null

Annotated Code

DSA Java

public class StackUsingArray {
    private int[] arr;
    private int top;
    private int capacity;

    public StackUsingArray(int size) {
        arr = new int[size];
        capacity = size;
        top = -1; // stack is empty
    }

    public void push(int value) {
        if (top == capacity - 1) {
            System.out.println("Stack Overflow");
            return;
        }
        top++; // move top up
        arr[top] = value; // place value at top
    }

    public int pop() {
        if (top == -1) {
            System.out.println("Stack Underflow");
            return -1; // indicates empty
        }
        int poppedValue = arr[top];
        top--; // move top down
        return poppedValue;
    }

    public void printStack() {
        if (top == -1) {
            System.out.println("Stack is empty");
            return;
        }
        for (int i = 0; i <= top; i++) {
            System.out.print(arr[i]);
            if (i != top) System.out.print(" -> ");
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        StackUsingArray stack = new StackUsingArray(5);
        stack.push(10);
        stack.push(20);
        stack.pop();
        stack.push(30);
        stack.printStack();
    }
}

if (top == capacity - 1) { System.out.println("Stack Overflow"); return; }

check if stack is full before pushing

top++; arr[top] = value;

increment top and add new value at top

if (top == -1) { System.out.println("Stack Underflow"); return -1; }

check if stack is empty before popping

int poppedValue = arr[top]; top--; return poppedValue;

store top value, decrement top to remove it logically

for (int i = 0; i <= top; i++) { print arr[i] with arrows }

print all elements from bottom to top

Output

10 -> 30 -> null

Complexity Analysis

Time: O(1) for push and pop because we only update the top index and array position directly

Space: O(n) where n is the capacity of the array, fixed size allocated at start

vs Alternative: Compared to linked list stack, array stack uses fixed space but faster access; linked list uses dynamic space but more memory per element

Edge Cases

Push when stack is full

Prints 'Stack Overflow' and does not add new element

DSA Java

if (top == capacity - 1) { System.out.println("Stack Overflow"); return; }

Pop when stack is empty

Prints 'Stack Underflow' and returns -1

DSA Java

if (top == -1) { System.out.println("Stack Underflow"); return -1; }

Print empty stack

Prints 'Stack is empty'

DSA Java

if (top == -1) { System.out.println("Stack is empty"); return; }

When to Use This Pattern

When you need last-in-first-out order with fixed size and fast access, use stack with array to track top index for quick push/pop.

Common Mistakes

Mistake: Forgetting to check for stack overflow before pushing
Fix: Add condition to check if top reached capacity - 1 before push

Mistake: Forgetting to check for stack underflow before popping
Fix: Add condition to check if top is -1 before pop

Mistake: Not updating top index correctly after push or pop
Fix: Increment top on push and decrement top on pop to keep track of stack top

Summary

Implements a stack using a fixed-size array and a top index to add/remove elements.

Use when you want a simple last-in-first-out structure with known maximum size.

The key is to track the top position to know where to push or pop elements.

Practice

1. What is the main purpose of using an array in stack implementation?

easy

A. To allow random access to elements anywhere in the stack

B. To store elements in a fixed-size linear structure

C. To automatically resize the stack when full

D. To store elements in a linked manner with pointers

Solution

1. Step 1: Understand stack storage using array

   An array provides a fixed-size linear block of memory to store stack elements sequentially.

2. Step 2: Compare with other storage methods

   Unlike linked lists, arrays do not use pointers and have fixed size, so they store elements linearly.

3. Final Answer:

   To store elements in a fixed-size linear structure -> Option B

4. Quick Check:

   Array = fixed-size linear storage [OK]

Hint: Stack array stores elements linearly with fixed size [OK]

Common Mistakes:

• Thinking array allows automatic resizing
• Confusing array with linked list storage
• Assuming random access is main stack feature

2. Which of the following is the correct way to declare a stack array of size 10 in Java?

easy

A. int[] stack = new int[10];

B. int stack = new int[10];

C. int stack[] = int[10];

D. int stack = int[10];

Solution

1. Step 1: Recall Java array declaration syntax

   In Java, arrays are declared with type[], variable = new type[size];

2. Step 2: Match correct syntax

   int[] stack = new int[10]; matches this syntax: int[] stack = new int[10]; others have syntax errors.

3. Final Answer:

   int[] stack = new int[10]; -> Option A

4. Quick Check:

   Java array declaration = int[] name = new int[size]; [OK]

Hint: Use 'type[] name = new type[size];' for arrays in Java [OK]

Common Mistakes:

• Missing 'new' keyword
• Wrong placement of brackets
• Assigning array without 'new'

3. What will be the output after the following operations on a stack of size 3?

Stack s = new Stack(3);
s.push(10);
s.push(20);
s.pop();
s.push(30);
s.push(40);

Assuming push prints "Pushed: value" and pop prints "Popped: value".

medium

A. "Pushed: 10\nPushed: 20\nPopped: 20\nStack Overflow\nPushed: 40"

B. "Pushed: 10\nPushed: 20\nPopped: 20\nPushed: 30"

C. "Pushed: 10\nPushed: 20\nPopped: 20\nPushed: 30\nStack Overflow"

D. "Pushed: 10\nPushed: 20\nPopped: 20\nPushed: 30\nPushed: 40"

Solution

1. Step 1: Trace push and pop operations on stack size 3

   push(10) prints "Pushed: 10" stack:[10]; push(20) "Pushed: 20" [10,20]; pop() "Popped: 20" [10]; push(30) "Pushed: 30" [10,30]; push(40) "Pushed: 40" [10,30,40] (capacity 3, net 3 elements).

2. Step 2: Identify outputs printed

   All pushes and pop print their messages; no overflow since 3 <= capacity 3.

3. Final Answer:

   "Pushed: 10\nPushed: 20\nPopped: 20\nPushed: 30\nPushed: 40" -> Option D

4. Quick Check:

   Net 3 elements <= size 3 = no overflow [OK]

Hint: Net pushes (4 push - 1 pop = 3) <= size 3: no overflow [OK]

Common Mistakes:

• Thinking stack doesn't reuse space after pop
• Miscalculating net elements (3 <= 3)
• Expecting overflow on 3rd net push

4. Identify the error in the following stack push method and select the correct fix:

public void push(int x) {
  if (top == size) {
    System.out.println("Stack Overflow");
  } else {
    stack[top] = x;
    top++;
  }
}

medium

A. Change condition to if (top >= size) to correctly detect overflow

B. Change condition to if (top == size - 1) to avoid overflow

C. Initialize top to 1 instead of 0 to fix indexing

D. Replace top++ with ++top to fix increment order

Solution

1. Step 1: Analyze overflow condition

   Since array indices go from 0 to size-1, top == size means stack is full; condition should catch top >= size to prevent overflow.

2. Step 2: Check other options

   Changing to size - 1 is incorrect because top points to next free slot; initializing top to 1 or changing increment order is unrelated.

3. Final Answer:

   Change condition to if (top >= size) to correctly detect overflow -> Option A

4. Quick Check:

   Overflow check = top >= size [OK]

Hint: Overflow when top index reaches or exceeds size [OK]

Common Mistakes:

• Using top == size - 1 instead of top >= size
• Incorrect top initialization
• Misunderstanding increment order

5. Given a stack implemented using an array with size 5, which sequence of operations will result in the stack containing elements [5, 10, 15] from bottom to top?

Operations:
1) push(5)
2) push(10)
3) pop()
4) push(15)
5) push(10)

hard

A. Perform operations in order: 1, 2, 3, 4, 5

B. Perform operations in order: 1, 3, 2, 4, 5

C. Perform operations in order: 1, 2, 5, 3, 4

D. Perform operations in order: 1, 2, 4, 3, 5

Solution

1. Step 1: Trace operations in order 1,2,3,4,5

   push(5) -> [5]; push(10) -> [5,10]; pop() removes 10 -> [5]; push(15) -> [5,15]; push(10) -> [5,15,10]

2. Step 2: Check final stack order bottom to top

   Stack is [5,15,10], which is not [5,10,15]. So Perform operations in order: 1, 2, 3, 4, 5 is incorrect. Check other options similarly.

3. Step 3: Trace Perform operations in order: 1, 3, 2, 4, 5 (1,3,2,4,5)

   push(5) -> [5]; pop() removes 5 -> []; push(10) -> [10]; push(15) -> [10,15]; push(10) -> [10,15,10] not correct.

4. Step 4: Trace Perform operations in order: 1, 2, 4, 3, 5 (1,2,4,3,5)

   push(5) -> [5]; push(10) -> [5,10]; push(15) -> [5,10,15]; pop() removes 15 -> [5,10]; push(10) -> [5,10,10] not correct.

5. Step 5: Trace Perform operations in order: 1, 2, 5, 3, 4 (1,2,5,3,4)

   push(5) -> [5]; push(10) -> [5,10]; push(10) -> [5,10,10]; pop() removes 10 -> [5,10]; push(15) -> [5,10,15] correct final stack.

6. Final Answer:

   Perform operations in order: 1, 2, 5, 3, 4 -> Option C

7. Quick Check:

   Final stack = [5,10,15] after Perform operations in order: 1, 2, 5, 3, 4 [OK]

Hint: Simulate stack step-by-step to verify final order [OK]

Common Mistakes:

• Assuming order of operations does not affect stack
• Not simulating pop effects correctly
• Confusing push order with final stack order