How to Implement a Stack Using an Array in C++

Stacks are fundamental data structures that follow the Last In, First Out (LIFO) principle. In this article, we will explore how to implement a stack using an array in C++. Understanding this concept is essential for programmers, as stacks are widely used in various applications, including function calls, expression evaluation, and backtracking problems.

What is a Stack?

A stack is a collection of elements with two primary operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the top element from the stack.

The stack also typically supports a few additional operations, such as:

• Peek: Returns the top element without removing it.
• IsEmpty: Checks if the stack is empty.
• Size: Returns the number of elements in the stack.

Why Use a Stack?

Stacks are useful in many scenarios, including:

• Function Call Management: Stacks keep track of active function calls in programming languages.
• Expression Evaluation: Postfix and infix expressions can be evaluated using stacks.
• Undo Mechanism: Applications like text editors use stacks to manage the undo operation.

Implementing a Stack Using an Array

Step 1: Define the Stack Structure

To begin, we will define a structure for our stack. We will use an array to hold the elements and an integer to track the current position of the top element.

Here’s how you can define a stack structure in C++:

#include <iostream>
using namespace std;

#define MAX 100 // Define maximum size of the stack

class Stack {
private:
    int arr[MAX]; // Array to hold stack elements
    int top;      // Index of the top element

public:
    Stack() { top = -1; } // Constructor initializes top to -1

    void push(int x);
    int pop();
    int peek();
    bool isEmpty();
    int size();
};

Step 2: Implement Push Operation

The push function adds an element to the top of the stack. We first check if the stack is full to avoid overflow.

void Stack::push(int x) {
    if (top >= MAX - 1) {
        cout << "Stack Overflow\n";
        return;
    }
    arr[++top] = x;
    cout << x << " pushed to stack\n";
}

Step 3: Implement Pop Operation

The pop function removes and returns the top element. If the stack is empty, we handle the underflow condition.

int Stack::pop() {
    if (isEmpty()) {
        cout << "Stack Underflow\n";
        return -1; // Return a sentinel value
    }
    return arr[top--];
}

Step 4: Implement Peek Operation

The peek function allows us to see the top element without removing it. We again check if the stack is empty.

int Stack::peek() {
    if (isEmpty()) {
        cout << "Stack is empty\n";
        return -1; // Return a sentinel value
    }
    return arr[top];
}

Step 5: Implement Utility Functions

The isEmpty and size functions help us manage the stack effectively.

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

int Stack::size() {
    return top + 1;
}

Complete Stack Implementation

Combining all of the above, here’s the complete implementation of a stack using an array in C++:

#include <iostream>
using namespace std;

#define MAX 100 // Define maximum size of the stack

class Stack {
private:
    int arr[MAX]; // Array to hold stack elements
    int top;      // Index of the top element

public:
    Stack() { top = -1; } // Constructor initializes top to -1

    void push(int x);
    int pop();
    int peek();
    bool isEmpty();
    int size();
};

void Stack::push(int x) {
    if (top >= MAX - 1) {
        cout << "Stack Overflow\n";
        return;
    }
    arr[++top] = x;
    cout << x << " pushed to stack\n";
}

int Stack::pop() {
    if (isEmpty()) {
        cout << "Stack Underflow\n";
        return -1; // Return a sentinel value
    }
    return arr[top--];
}

int Stack::peek() {
    if (isEmpty()) {
        cout << "Stack is empty\n";
        return -1; // Return a sentinel value
    }
    return arr[top];
}

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

int Stack::size() {
    return top + 1;
}

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    cout << s.pop() << " popped from stack\n";
    cout << "Top element is: " << s.peek() << endl;
    cout << "Stack size is: " << s.size() << endl;
    return 0;
}

Conclusion

Implementing a stack using an array in C++ is a straightforward task that provides valuable insights into how data structures work. By following the steps outlined in this article, you can create a functional stack that supports essential operations like push, pop, and peek.

Further Considerations

• Dynamic Resizing: For more advanced implementations, consider using dynamic arrays or linked lists to accommodate varying sizes.
• Error Handling: Improve user experience by implementing better error handling and user feedback.
• Performance: Stacks implemented using arrays can run into memory limitations, so consider the use cases where a linked list might be more appropriate.

With this foundation, you can explore more complex data structures and algorithms that leverage the power of stacks in C++. Happy coding!