Stack Implementation Using Array in DSA C++

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 and add or remove items there.

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 numbered spots, and the top tells you where the last plate is.

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

Visual:
[0] [1] [2] [3] [4]
 _    _   _   _   _ 
Top -> -1 (no plates)

Dry Run Walkthrough

Input: Create stack of size 5, push 10, push 20, pop, push 30

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

Step 1: Push 10 onto stack

Array: [10, _ , _ , _ , _ ]
Top index: 0
Stack: 10 (top)

Why: We add 10 at the next free spot and update top to 0

Step 2: Push 20 onto stack

Array: [10, 20, _ , _ , _ ]
Top index: 1
Stack: 10 -> 20 (top)

Why: Add 20 at index 1 and move top to 1

Step 3: Pop top element (20)

Array: [10, 20, _ , _ , _ ]
Top index: 0
Stack: 10 (top)

Why: Remove top by moving top index down to 0; 20 is no longer considered in stack

Step 4: Push 30 onto stack

Array: [10, 30, _ , _ , _ ]
Top index: 1
Stack: 10 -> 30 (top)

Why: Add 30 at index 1 and update top to 1

Result:

Array: [10, 30, _ , _ , _ ]
Top index: 1
Stack: 10 -> 30 (top)

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Stack {
private:
    int *arr;
    int capacity;
    int top;

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

    ~Stack() {
        delete[] arr;
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == capacity - 1;
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack Overflow\n";
            return;
        }
        top++; // move top up
        arr[top] = value; // place value at new top
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow\n";
            return -1; // error value
        }
        int poppedValue = arr[top];
        top--; // move top down
        return poppedValue;
    }

    void printStack() {
        if (isEmpty()) {
            cout << "Stack is empty\n";
            return;
        }
        for (int i = 0; i <= top; i++) {
            cout << arr[i];
            if (i != top) cout << " -> ";
        }
        cout << " (top)\n";
    }
};

int main() {
    Stack s(5);
    s.push(10);
    s.push(20);
    s.printStack();
    s.pop();
    s.printStack();
    s.push(30);
    s.printStack();
    return 0;
}

top++; // move top up

advance top index to next free position for push

arr[top] = value; // place value at new top

store new value at top position

int poppedValue = arr[top];

save current top value before removing

top--; // move top down

decrease top index to remove top element

for (int i = 0; i <= top; i++) {

iterate from bottom to current top to print stack

Output

10 -> 20 (top)

10 (top)

10 -> 30 (top)

Complexity Analysis

Time: O(1) for push and pop because we only update the top index and access one array element

Space: O(n) because we use an array of fixed size n to store stack elements

vs Alternative: Compared to linked list stack, array stack uses fixed memory but is faster due to direct indexing; linked list uses dynamic memory but has overhead for pointers

Edge Cases

Push when stack is full

Prints 'Stack Overflow' and does not add element

DSA C++

if (isFull()) { cout << "Stack Overflow\n"; return; }

Pop when stack is empty

Prints 'Stack Underflow' and returns -1

DSA C++

if (isEmpty()) { cout << "Stack Underflow\n"; return -1; }

Print empty stack

Prints 'Stack is empty'

DSA C++

if (isEmpty()) { cout << "Stack is empty\n"; return; }

When to Use This Pattern

When you need last-in-first-out order with fast access and fixed size, use stack with array to quickly push and pop from the top.

Common Mistakes

Mistake: Incrementing top after assigning value in push, causing off-by-one error
Fix: Increment top first, then assign value at arr[top]

Mistake: Not checking for stack overflow before push
Fix: Add isFull() check before pushing to avoid writing outside array

Mistake: Not checking for stack underflow before pop
Fix: Add isEmpty() check before popping to avoid invalid access

Summary

Implements a stack using an array with a top index to add/remove elements at the end.

Use when you want a simple fixed-size stack with fast push/pop operations.

Remember the top index points to the last added element and moves up/down as you push/pop.

Practice

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

easy

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

B. To allow random access to elements anywhere

C. To sort elements automatically

D. To store elements in a tree-like structure

Solution

1. Step 1: Understand stack storage

   A stack stores elements in a linear order, last-in first-out (LIFO).

2. Step 2: Role of array in stack

   An array provides a fixed-size linear structure to hold stack elements efficiently.

3. Final Answer:

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

4. Quick Check:

   Stack uses array for fixed linear storage [OK]

Hint: Stack uses array for fixed linear storage [OK]

Common Mistakes:

• Confusing stack with queue or tree
• Thinking array sorts elements automatically
• Assuming stack allows random access

2. Which of the following is the correct syntax to declare a stack array of size 10 in C++?

easy

A. stack int[10];

B. int stack[10];

C. int stack();

D. array stack[10];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, arrays are declared as: type name[size];

2. Step 2: Match with options

   int stack[10]; matches correct syntax: int stack[10];

3. Final Answer:

   int stack[10]; -> Option B

4. Quick Check:

   C++ array declaration = int stack[10]; [OK]

Hint: Array declaration: type name[size]; [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Wrong order of type and name
• Using non-existent 'array' keyword

3. What will be the output after executing the following code?

int stack[5];
int top = -1;
// Push 10
stack[++top] = 10;
// Push 20
stack[++top] = 20;
// Pop
int x = stack[top--];
// Push 30
stack[++top] = 30;
// Print top element
std::cout << stack[top];

medium

A. Runtime error

B. 20

C. 10

D. 30

Solution

1. Step 1: Trace stack operations step-by-step

   Initially top = -1.
   Push 10: top=0, stack[0]=10
   Push 20: top=1, stack[1]=20
   Pop: x=stack[1]=20, top=0
   Push 30: top=1, stack[1]=30

2. Step 2: Identify top element after operations

   Top is 1, stack[1] = 30, so output is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Last pushed after pop is 30 [OK]

Hint: Track top index changes carefully [OK]

Common Mistakes:

• Confusing push and pop order
• Not updating top correctly
• Assuming pop removes element permanently

4. Identify the error in the following stack push function using array:

void push(int stack[], int &top, int size, int value) {
  if (top == size) {
    std::cout << "Stack Overflow";
    return;
  }
  stack[++top] = value;
}

medium

A. No error, function is correct

B. The increment of top should be after assignment

C. The condition should be 'top == size - 1' to check overflow

D. The function should return a value

Solution

1. Step 1: Understand overflow condition

   Array indices go from 0 to size-1, so top can be max size-1.

2. Step 2: Check condition in code

   Condition 'top == size' is wrong; it should be 'top == size - 1' to prevent overflow.

3. Final Answer:

   The condition should be 'top == size - 1' to check overflow -> Option C

4. Quick Check:

   Overflow check uses top == size - 1 [OK]

Hint: Array max index = size - 1 for overflow check [OK]

Common Mistakes:

• Checking top == size instead of size - 1
• Incrementing top incorrectly
• Ignoring overflow condition

5. Given a stack implemented using an array of size 4, what will be the state of the stack after these operations?

push(5); push(10); pop(); push(15); push(20); push(25); pop();

Assume stack is initially empty and top = -1. Choose the correct stack content from bottom to top.

hard

A. 5 -> 15 -> 20 -> null

B. 5 -> 10 -> 15 -> 20 -> null

C. 5 -> 15 -> 20 -> 25 -> null

D. 10 -> 15 -> 20 -> null

Solution

1. Step 1: Execute operations step-by-step

   Start: top = -1, stack empty.
   push(5): top=0, stack[0]=5
   push(10): top=1, stack[1]=10
   pop(): removes 10, top=0
   push(15): top=1, stack[1]=15
   push(20): top=2, stack[2]=20
   push(25): top=3, stack[3]=25 (stack full)
   pop(): removes 25, top=2

2. Step 2: Final stack content

   Stack from bottom to top: 5 (index 0), 15 (index 1), 20 (index 2). So output is 5 -> 15 -> 20 -> null.

3. Final Answer:

   5 -> 15 -> 20 -> null -> Option A

4. Quick Check:

   Track push/pop changes carefully [OK]

Hint: Write each push/pop step to track stack state [OK]

Common Mistakes:

• Ignoring pop effects on top
• Assuming stack grows beyond size
• Confusing order of elements