Implement Stack Using Arrays in C++ | Complete Guide with Code, Dry Run & Complexity (Interview Ready)

A Stack is one of the most fundamental linear data structures in computer science. Think of it exactly like a real-world stack of everyday objects—like a stack of dinner plates, a stack of books, or a deck of cards.

If you want to add a plate to the pile, you place it on the very top. If you want to take a plate out, you must take it from the very top. You cannot pull a plate from the middle or bottom without crashing the whole thing.

The Core Principle: LIFO

A stack operates on the LIFO principle, which stands for Last In, First Out.

This means the element that was added last (most recently) is the first one to be removed.

Example: If you push a blue book onto a stack, then a red book, and finally a green book, the green book is on top. If you decide to pick up a book, you must pick up the green one first (the last one you put down).

Key Stack Operations

A stack restricts data access so that you can only interact with the element at the top. It primarily supports three basic operations:

Push: Adds an element to the top of the stack.
Pop: Removes and returns the top element from the stack.
Top (or Peek): Looks at the top element without removing it.

Auxiliary Operations

isEmpty: Checks if the stack has zero elements.
isFull: Checks if the stack has reached its maximum capacity (relevant for fixed-size stacks).

Real-World Examples in Software

You actually use stacks every single day when navigating the digital world:

The Undo/Redo Button: When you type in a text editor like Microsoft Word or Google Docs, your actions are "pushed" onto a history stack. When you hit Ctrl + Z (Undo), the editor "pops" your most recent action off the stack to reverse it.
Browser History: When you browse the web, every new page you visit gets pushed onto your history stack. When you click the Back button, the browser pops the current page off and takes you to the previously visited page.
Function Calls (The Call Stack): When a programming language executes code and a Function A calls Function B, the system pushes Function B onto a "Call Stack." Once Function B completes its task, it is popped off, and control returns to Function A.

1. Problem Statement

At its core, the problem asks us to design a data structure that mimics a real-world stack (like a stack of plates) using a standard array.

What is a Stack?

A stack is a linear data structure that follows the LIFO principle.

What does LIFO mean?

LIFO stands for Last In, First Out. The last element you put into the stack is the very first one you take out. Imagine a stack of dinner plates: you add plates to the top, and when you need a plate, you take it from the top. You never pull from the bottom.

Input

A series of operations:

push(x): Insert an element x into the stack.
pop(): Remove the top element from the stack.
top() (or peek()): Look at the top element without removing it.

Output

push(x) returns nothing.
pop() returns the removed element (or an error/flag if empty).
top() returns the top element (or an error/flag if empty).

Constraints & Conditions

Maximum capacity: The stack will have a predefined fixed capacity (e.g., $N$ ).
Duplicates & Negatives: Allowed. The stack does not care about the value of the elements, only their order.
Stack Overflow: Occurs when you try to push an element but the array is already at its maximum capacity.
Stack Underflow: Occurs when you try to pop or get the top element, but the stack is completely empty.
Time Complexity: The interviewer expects every single operation to run in $O(1)$ (constant) time.

Small Example

Assume Capacity = 5.

push(10)
push(20)
push(30)
top()
pop()
top()

Output:

30

20

Why is this output correct?

We push 10, then 20, then 30. The stack from bottom to top is [10, 20, 30].
top() looks at the last inserted element. It correctly outputs 30.
pop() removes and returns the last inserted element. It outputs 30. The stack is now [10, 20].
The next top() looks at the new top element, outputting 20.

2. Intuition

To build this from first principles, imagine a standard array arr with indices from 0 to 4 (capacity of 5).

Index:    0    1    2    3    4
Array:  [   ][   ][   ][   ][   ]

To make this array act like a stack, we need a way to keep track of where the "top" is. We do this by maintaining a single integer variable called top.

Why top starts at -1

We initialize top = -1. Array indices start at 0. If top was initialized to 0, it would imply there is already an element at index 0. By starting at -1, we clearly signal that the stack currently has absolutely no elements.

Why the stack is empty when top == -1

Because -1 is not a valid array index. It mathematically represents an empty state before the 0th index.

Why pushing increments top

When we add an element, we first move our top pointer up by one (from -1 to 0), and then place the element at arr[top].

Why popping decrements top

When we remove an element, we read the value at arr[top], and then simply decrease top by one.

Why no shifting of elements is required

We do not actually need to delete or erase the old value in the array. By moving the top pointer down, we effectively "forget" the popped element. The next time we push, we will simply overwrite that old memory space.

3. Key Observations

The array stores stack elements: The raw data lives in the contiguous blocks of the array.
top always points to the current top element: It represents the boundary of our active stack within the larger array capacity.
Push inserts at top + 1: We move the boundary up, then write.
Pop removes the latest inserted element: We read the boundary value, then move the boundary down.
Top simply returns arr[top]: It is a direct array access.
All operations happen at one end: We strictly operate at the top index. We never touch the middle or bottom (index 0).
Every operation takes constant time: Because array index access is instantaneous, all these pointer shifts and reads are $O(1)$ .

These observations naturally lead to the array implementation because arrays provide instant $O(1)$ access to any index, making it the perfect underlying structure for moving a single top pointer back and forth.

4. Algorithm

Here is the exact algorithmic flow for each function:

Push(x)

Check for overflow: If top is equal to Capacity - 1, the stack is full. Throw an error or return.
Increment top: Move the pointer to the next available empty slot (top = top + 1).
Store the value: Assign arr[top] = x.

Pop()

Check for underflow: If top == -1, the stack is empty. Throw an error or return a sentinel value (like -1).
Retrieve the value: Store arr[top] in a temporary variable.
Decrement top: Move the pointer down (top = top - 1).
Return the temporary variable.

Top()

Check for underflow: If top == -1, return an error.
Return the current top element: arr[top].

isEmpty()

Return whether top == -1. (Returns true if empty, false otherwise).

size()

Return top + 1. (Since indices are 0-based, a top of 2 means there are 3 elements).

Every step is necessary to maintain boundaries (preventing segmentation faults) and to keep the logical LIFO structure intact.

5. Complete Dry Run

Let's simulate the stack with Capacity = 6.

Initial State:

Array: [_, _, _, _, _, _]
Top: -1

Operation 1: push(5)

Step: Increment top to 0. Set arr[0] = 5.
Array: [5, _, _, _, _, _]
Top: 0
Stack Contents (bottom to top): 5

Operation 2: push(7)

Step: Increment top to 1. Set arr[1] = 7.
Array: [5, 7, _, _, _, _]
Top: 1
Stack Contents: 5, 7

Operation 3: push(2)

Step: Increment top to 2. Set arr[2] = 2.
Array: [5, 7, 2, _, _, _]
Top: 2
Stack Contents: 5, 7, 2

Operation 4: push(9)

Step: Increment top to 3. Set arr[3] = 9.
Array: [5, 7, 2, 9, _, _]
Top: 3
Stack Contents: 5, 7, 2, 9

Operation 5: pop()

Step: Read arr[3] (which is 9). Decrement top to 2.
Returned Value: 9
Array: [5, 7, 2, 9, _, _] (Note: the 9 is still in memory, but logically deleted)
Top: 2
Stack Contents: 5, 7, 2

Operation 6: push(1)

Step: Increment top to 3. Set arr[3] = 1. (The old 9 is overwritten)
Array: [5, 7, 2, 1, _, _]
Top: 3
Stack Contents: 5, 7, 2, 1

Operation 7: top()

Step: Read arr[3].
Returned Value: 1
Array: [5, 7, 2, 1, _, _]
Top: 3
Stack Contents: 5, 7, 2, 1

c++ implementation:

class Stack {
private:
    // Dynamic array to store stack elements
    int* arr;

    // Maximum capacity of the stack
    int capacity = 1000;

    // Index of the current top element
    // Initially -1 because the stack is empty
    int topIndex;

public:
    // Constructor
    Stack() {

        // Allocate memory for the stack
        arr = new int[capacity];

        // Initially, no elements are present
        topIndex = -1;
    }

    // Destructor to free allocated memory
    ~Stack() {
        delete[] arr;
    }

    // Push an element onto the stack
    void push(int x) {

        // Check if the stack is already full
        if (topIndex == capacity - 1)
            return;

        // Move to the next position
        topIndex++;

        // Store the new element
        arr[topIndex] = x;
    }

    // Remove and return the top element
    int pop() {

        // If the stack is empty
        if (topIndex == -1)
            return -1;

        // Store the top element
        int value = arr[topIndex];

        // Remove it by moving the top pointer down
        topIndex--;

        return value;
    }

    // Return the current top element
    int top() {

        // If the stack is empty
        if (topIndex == -1)
            return -1;

        return arr[topIndex];
    }

    // Check whether the stack is empty
    bool isEmpty() {

        return topIndex == -1;
    }

    // Return the current number of elements
    int size() {

        return topIndex + 1;
    }
};

6. Correctness Proof

Why does this array logic perfectly emulate a stack?

top points to the most recent: By definition, every time we add a new item, we update top to point directly to it.
Push is safe: Push only adds after the current top, meaning older items are never overwritten prematurely.
Pop removes the latest: When we ask to remove an item, pop() looks exactly at top. It decreases top, cutting the latest item out of the logical active window.
Older elements are unchanged: Because we only ever manipulate the boundary (top), elements at indices 0 to top - 1 are left completely alone.
Conclusion: Because the only item ever accessed or removed is the very last one added, this data structure strictly obeys the Last In, First Out (LIFO) principle.

7. Complexity Analysis

Time Complexity

Push: $O(1)$ . We check a condition, do one addition, and assign one array index.
Pop: $O(1)$ . We check a condition, do one subtraction, and return a value.
Top: $O(1)$ . We check a condition and return an array index.
isEmpty: $O(1)$ . One comparison operation.
size: $O(1)$ . One addition operation.

Space Complexity

Overall Space: $O(N)$ where $N$ is the maximum capacity, because we must pre-allocate the array.
Auxiliary Space: $O(1)$ per operation. We do not create any new data structures during pushes or pops.

8. Edge Cases

Empty stack: Checked via top == -1. Handled gracefully by returning errors or sentinel values during pop and top.
Stack with one element: top is 0. Popping makes top -1, cleanly returning the stack to empty status.
Stack Overflow: Handled by checking top == capacity - 1 before pushing. Prevents crashing from out-of-bounds array access.
Stack Underflow: Handled by checking top == -1 before popping.
Duplicate values: Array naturally allows duplicates; top moves forward regardless of the value.
Negative numbers: Array stores raw integers; negative values are stored and retrieved safely.
Capacity = 1: Works perfectly. top moves from -1 to 0 and back. Pushing a second item correctly triggers overflow.
Large capacity: Memory allocation might fail if the capacity is larger than available RAM, but algorithmically it remains sound.
Continuous push and pop: top will safely oscillate up and down, continually overwriting old "garbage" data without memory leaks.

9. Common Interview Mistakes

Forgetting to initialize top = -1: If initialized to 0, the first inserted element goes to index 1, wasting space, or implies index 0 is full.
Incorrect overflow condition: Using top == capacity instead of top == capacity - 1. Arrays are 0-indexed; an array of size 5 maxes out at index 4.
Incorrect underflow condition: Using top == 0 for empty. This would mean a stack with 1 element (at index 0) is treated as empty.
Incrementing/decrementing top in the wrong order: For push, if you write arr[top] = x then top++, you write to index -1 (crash). For pop, if you decrement then read, you return the wrong element.
Accessing invalid indices: Failing to check overflow/underflow leads to segmentation faults.
Returning the wrong value in top(): Returning the top index variable instead of arr[top].
Forgetting boundary checks: Assuming the user will always call push and pop correctly.
Confusing top with stack size: top is an index. Size is top + 1.

video reference:

practice link:

The Core Principle: LIFO

Key Stack Operations

Auxiliary Operations

Real-World Examples in Software

1. Problem Statement

2. Intuition

3. Key Observations

4. Algorithm

5. Complete Dry Run

c++ implementation:

6. Correctness Proof

7. Complexity Analysis

8. Edge Cases

9. Common Interview Mistakes

chakradhar

The Core Principle: LIFO

Key Stack Operations

Auxiliary Operations

Real-World Examples in Software

1. Problem Statement

2. Intuition

3. Key Observations

4. Algorithm

5. Complete Dry Run

c++ implementation:

6. Correctness Proof

7. Complexity Analysis

8. Edge Cases

9. Common Interview Mistakes