How to implement a stack using an array in C++?

A stack is a basic data structure that complies with the Last-In-First-Out (LIFO) concept. It permits the effective insertion and removal of items from the upper end of one side. Many applications and algorithms rely on stacks as the primary data structure. Some of these include balancing brackets and depth first search.

We will examine how an array implements a stack in C++. To assist you in comprehending the procedure, we will go over the relevant procedures and offer code samples and illustrations.

Array-based stack implementation

To implement a stack using an array, we need to consider the following essential components and operations:

1. Define the Stack class

Create a class named Stack that will encapsulate all the necessary functionalities of the stack. It should have private members to store the elements and keep track of the top index.

class Stack {
private:
    static const int MAX_SIZE = 100; // Maximum size of the stack
    int stackArray[MAX_SIZE];
    int top; // Index of the top element

public:
    Stack(); // Constructor
    void push(int element); // Pushes an element onto the stack
    int pop(); // Pops the top element from the stack
    bool isEmpty(); // Checks if the stack is empty
};

We define a class named Stack that encapsulates the functionalities of the stack. It has private members MAX_SIZE (maximum size of the stack), stackArray (the array used for stack storage), and top (the index of the top element). The class also declares the constructor and the public member functions push, pop, and isEmpty.

2. Constructor

Initialize the stack by setting the top index to -1 in the constructor.

Stack::Stack() {
    top = -1;
}

This is the constructor definition for the Stack class. It initializes the top index to -1, indicating an empty stack.

3. The push() operation

To insert an element into the stack, we increment the top index and assign the element to the corresponding position in the stackArray.

void Stack::push(int element) {
    if (top == MAX_SIZE - 1) {
        // Stack is full
        cout << "Stack Overflow!" << endl;
        return;
    }
    stackArray[++top] = element;
}

The push() function adds an element to the top of the stack. It first checks if the stack is already full by comparing top with MAX_SIZE - 1. If the stack is full, it displays an error message indicating a stack overflow and returns. Otherwise, it increments top and assigns the element value to the corresponding position in the stackArray.

4. The pop() operation

To remove the top element from the stack, we return the element at the current top index and decrement the top index.

int Stack::pop() {
    if (top == -1) {
        // Stack is empty
        cout << "Stack Underflow!" << endl;
        return -1; // Or throw an exception
    }
    return stackArray[top--];
}

The pop() function removes and returns the stack’s top element. It first checks if the stack is empty by comparing top with -1. If the stack is empty, it displays an error message indicating a stack underflow and returns -1 (or throws an exception). Otherwise, it returns the value at stackArray[top] and then decrements top to remove the element from the stack.

5. The IsEmpty() operation

To check if the stack is empty, we simply compare the top index with -1.

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

The isEmpty() function checks if the stack is empty by comparing top with -1. It returns true if the stack is empty and false otherwise.

Code Implementaiton

Let’s see the working of Stack using an array with the help of the following Code:

#include <iostream>
using namespace std;
class Stack {
private:
    static const int MAX_SIZE = 100; // Maximum size of the stack
    int stackArray[MAX_SIZE];
    int top; // Index of the top element
public:
    Stack(); // Constructor
    void push(int element); // Pushes an element onto the stack
    int pop(); // Pops the top element from the stack
    bool isEmpty(); // Checks if the stack is empty
    int getTopIndex(); // Returns the index of the top element
    int getElementAt(int index); // Returns the element at the specified index
};
Stack::Stack() {
    top = -1;
}
void Stack::push(int element) {
    if (top == MAX_SIZE - 1) {
        // Stack is full
        cout << "Stack Overflow!" << endl;
        return;
    }
    stackArray[++top] = element;
}
int Stack::pop() {
    if (top == -1) {
        // Stack is empty
        cout << "Stack Underflow!" << endl;
        return -1; // Or throw an exception
    }
    return stackArray[top--];
}
bool Stack::isEmpty() {
    return (top == -1);
}
int Stack::getTopIndex() {
    return top;
}
int Stack::getElementAt(int index) {
    return stackArray[index];
}
int main() {
    Stack stack;
    
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    cout << "Elements in the stack: ";
    for (int i = stack.getTopIndex(); i >= 0; i--) {
        cout << stack.getElementAt(i) << " ";
    }
    cout << endl;
    
    int poppedElement = stack.pop();
    cout << "Popped element: " << poppedElement << endl;
    
    cout << "Remaining elements in the stack: ";
    for (int i = stack.getTopIndex(); i >= 0; i--) {
        cout << stack.getElementAt(i) << " ";
    }
    cout << endl;
    return 0;
}

Explanation

  • Line 54: It declares an object named stack of type Stack. It creates an instance of the Stack class.

  • Lines 56-58: These lines invoke the push() method of the stack object to add elements to the stack. It pushes the values 10, 20, and 30 onto the stack.

  • Lines 60-64: This block of code outputs the elements in the stack. It uses a loop to iterate over the stack starting from the top index and moving towards the bottom.

  • Line 66: It invokes the pop() method of the stack object to remove the top element from the stack.

  • Lines 69-73: This block of code outputs the remaining elements in the stack after the pop() operation.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved