Stack Implementation Using Array in DSA Java - Execution Trace

Concept Flow - Stack Implementation Using Array

Start

↓

Push Operation

↓

Check if stack is full?

Yes→Error: Stack Overflow

No↓

Add element at top index

↓

Increment top pointer

↓

Done Push

↓

Pop Operation

↓

Check if stack is empty?

Yes→Error: Stack Underflow

No↓

Decrement top pointer

↓

Return element at top index

↓

Done Pop

The stack uses an array and a top pointer. Push adds element at top if not full. Pop removes element from top if not empty.

Execution Sample

DSA Java

int[] stack = new int[3];
int top = 0;
// Push 10
stack[top++] = 10;
// Push 20
stack[top++] = 20;
// Pop
int val = stack[--top];

This code pushes 10 and 20 onto the stack, then pops the top element (20).

Execution Table

Step	Operation	Top Pointer	Stack Array State	Action Description
1	Initialize stack	0	[null, null, null]	Stack created with size 3, top at 0
2	Push 10	0 -> 1	[10, null, null]	10 added at index 0, top incremented to 1
3	Push 20	1 -> 2	[10, 20, null]	20 added at index 1, top incremented to 2
4	Pop	2 -> 1	[10, 20, null]	Top decremented to 1, element 20 popped from index 1
5	Push 30	1 -> 2	[10, 30, null]	30 added at index 1, top incremented to 2
6	Push 40	2 -> 3	[10, 30, 40]	40 added at index 2, top incremented to 3
7	Push 50	3	[10, 30, 40]	Stack full, cannot push 50 (Overflow)
8	Pop	3 -> 2	[10, 30, 40]	Top decremented to 2, element 40 popped from index 2
9	Pop	2 -> 1	[10, 30, 40]	Top decremented to 1, element 30 popped from index 1
10	Pop	1 -> 0	[10, 30, 40]	Top decremented to 0, element 10 popped from index 0
11	Pop	0	[10, 30, 40]	Stack empty, cannot pop (Underflow)

💡 Execution stops after stack overflow or underflow conditions prevent further push or pop.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11
top	0	1	2	1	2	3	3	2	1	0	0
stack	[null, null, null]	[10, null, null]	[10, 20, null]	[10, 20, null]	[10, 30, null]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]

Key Moments - 3 Insights

Why does the top pointer increment after pushing an element?

Because the top points to the next free position, after placing the element at top index, top increments to point to the next empty slot (see Step 2 and 3 in execution_table).

Why do we decrement top before popping an element?

Because top points to the next free slot, the actual top element is at top-1. So we decrement top first to get the correct index to pop (see Step 4 in execution_table).

What happens when we try to push but the stack is full?

The push operation is blocked and an overflow error occurs because top equals the array size, no space to add new element (see Step 7 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value of top after popping?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Top Pointer' column at Step 4 in execution_table.

At which step does the stack become full?

A Step 5

B Step 6

C Step 7

D Step 3

💡 Hint

Look for when top reaches the array size in execution_table's 'Top Pointer' column.

If we try to pop at Step 11, what happens to the stack array?

A Top decreases and element is removed

B Top stays same and underflow error occurs

C Top increases and element is added

D Stack array resets to empty

💡 Hint

See Step 11 in execution_table where pop is attempted on empty stack.

Concept Snapshot

Stack using array:
- Use array and top pointer
- Push: add element at top, then top++
- Pop: top--, then return element
- Overflow if top == size
- Underflow if top == 0

Full Transcript

This visualization shows how a stack is implemented using an array and a top pointer. The top pointer indicates the next free position in the array. When pushing, the element is placed at the current top index, then top is incremented. When popping, top is decremented first, then the element at top is returned. The stack can overflow if we try to push when top equals the array size, and underflow if we try to pop when top is zero. The execution table traces each step showing the top pointer and stack array state, helping learners see how the stack changes with each operation.

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