In the realm of computer science and programming, data structures are fundamental. The stack is one such data structure, known for its simplicity and usefulness. In this article, we will delve into the implementation of stack using array in C++ programming language.

Table of Contents

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

Download Now

We earn a commission if you make a purchase, at no additional cost to you.

Toggle

What is a Stack?

A “stack” is a linear data structure that adheres to the Last-In, First-Out (LIFO) principle. It is a collection of elements that perform two fundamental operations:

Push: This operation adds an element to the head of the array. As a consequence, the newly inserted element ascends to the highest position.

Pop: Pop is an operation that removes and returns the element at the top of the array. Following a pop operation, the element beneath the one that was removed becomes the new upper element.

Additionally, a third operation known as “Peek” or “Top” is frequently supported, allowing you to observe the top element of the stack without eliminating it.

Commonly, a stack is pictured as a pile of plates or volumes to which you can only add or remove items from the top. This structure is beneficial for several computer science applications, including managing function calls in a program (call stack), monitoring undo/redo functionality in software, and parsing expressions in compilers and interpreters.

Stacks are a fundamental data structure in many programming languages and systems and are used to implement algorithms such as depth-first search in graph traversal.

How Implementation of Stack using Array in C++ can be done

To implement a stack using an array in C++, you can create a class that encapsulates the stack operations. Here’s an example of how to implement a stack using an array in C++:

#include <iostream>
using namespace std;

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

public:
    Stack() {
        top = -1; // Initialize the top to -1 to indicate an empty stack
    }

    // Push operation to add an element to the stack
    void push(int value) {
        if (top < MAX_SIZE - 1) {
            arr[++top] = value;
        } else {
            cout << "Stack is full. Cannot push " << value << endl;
        }
    }

    // Pop operation to remove and return the top element
    int pop() {
        if (!isEmpty()) {
            return arr[top--];
        } else {
            cout << "Stack is empty." << endl;
            return -1; // You can choose a different value to indicate an error
        }
    }

    // Peek operation to view the top element without removing it
    int peek() {
        if (!isEmpty()) {
            return arr[top];
        } else {
            cout << "Stack is empty." << endl;
            return -1; // You can choose a different value to indicate an error
        }
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == -1;
    }
};

int main() {
    Stack stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    cout << "Top element: " << stack.peek() << endl;

    cout << "Popped element: " << stack.pop() << endl;

    cout << "Is the stack empty? " << (stack.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}

In this code, we define a ‘Stack’ class with push, pop, peek, and isEmpty member functions. The stack is implemented using an array of fixed size. The variable ‘top’ maintains note of the index of the top element, and elements are added or removed from the stack’s top. The ‘isEmpty’ function verifies that the stack is empty, and displays error messages as required.

Creating the Stack

Step 1: Include Necessary Libraries

To start implementing a stack using an array in C++, we need to include the necessary libraries. The key library we require is `<iostream>` for input and output operations.

#include <iostream>

Step 2: Define the Maximum Size

Define the maximum size of the stack, which will determine how many elements it can hold. For this example, let’s set the maximum size to 100.

#define MAX_SIZE 100

Step 3: Define the Stack

Create an array to represent the stack, and initialize a variable `top` to keep track of the top element in the stack.

int stack[MAX_SIZE];
int top = -1;

Stack Operations

Stack operations are the fundamental operations that can be carried out on a stack data structure. A stack is a linear data structure that adheres to the Last-In-First-Out (LIFO) principle, in which the last element introduced to the stack is the first element withdrawn. There are four principal stack operations that can be divided into two categories: fundamental operations and auxiliary operations.

Fundamental Stack Operations:

Push: Using the “push” operation, an element is added to the top of the stack. When an element is pushed onto a stack, it becomes the new topmost element.

Pop: The “pop” operation eliminates the highest element of the stack and returns it. Following a pop operation, the element immediately beneath the one that was removed becomes the new main element.

Additional Stack Operations:

Peek or Top: The “peek” operation enables the viewing of the top element of a stack without eliminating it. It provides access to the value of the topmost element without modifying the stack.

isEmpty: The “isEmpty” operation determines whether or not the array is vacant. It returns a boolean value, typically true if the stack does not contain any elements (is vacant) and false otherwise.

These fundamental and auxiliary stack operations are required for managing and manipulating stack data. They provide a straightforward and efficient method for manipulating a stack data structure. Stacks are used extensively in computer science and programming for a variety of purposes, including:

– Managing function call stacks in a program

– Monitoring undo/redo functionality in application software

– Expression parsing within compilers and interpreters

– Storing and managing data in depth-first search algorithms

– Implementing backtracking in algorithms such as N-Queens dilemma and labyrinth-solving techniques

The fundamental operations (push and pop) are used to modify the stack, whereas the auxiliary operations (peek and isEmpty) are used to investigate and verify the state of the stack without altering its contents.

Push Operation

Using the push operation, an element is added to the top of the stack. Before moving an element, we must first determine whether the stack is complete. If not, we can add a new element and advance the ‘top’ pointer.

void push(int data) {
    if (top < MAX_SIZE - 1) {
        stack[++top] = data;
    } else {
        std::cout << "Stack overflow! Cannot push " << data << std::endl;
    }
}

Pop Operation

The pop operation eliminates the item at the top of the array. Before removing an element, we must ensure that the stack is emptied to avoid errors.

void pop() {
    if (top >= 0) {
        std::cout << "Popped element: " << stack[top--] << std::endl;
    } else {
        std::cout << "Stack is empty! Cannot pop." << std::endl;
    }
}

Peek Operation

The peek operation enables us to observe the element on top without removing it. This is beneficial for a variety of applications.

int peek() {
    return stack[top];
}

Implementation Example

Let’s demonstrate the implementation of a stack using an array in C++ with a simple example:

int main() {
    push(10);
    push(20);
    push(30);

    std::cout << "Top element: " << peek() << std::endl;
    pop();

    std::cout << "Top element after pop: " << peek() << std::endl;

    return 0;
}

Creating the Stack using Array in C++

Create a basic stack data structure using an array in C++. Here’s a simple example of how to implement a stack using an array:

#include <iostream>

const int MAX_SIZE = 100; // Maximum size of the stack

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

public:
    Stack() {
        top = -1; // Initialize the top to -1 to indicate an empty stack
    }

    // Push operation to add an element to the stack
    void push(int value) {
        if (top < MAX_SIZE - 1) {
            arr[++top] = value;
        } else {
            std::cout << "Stack is full. Cannot push " << value << std::endl;
        }
    }

    // Pop operation to remove and return the top element
    int pop() {
        if (top >= 0) {
            return arr[top--];
        } else {
            std::cout << "Stack is empty." << std::endl;
            return -1; // You can choose a different value to indicate an error
        }
    }

    // Peek operation to view the top element without removing it
    int peek() {
        if (top >= 0) {
            return arr[top];
        } else {
            std::cout << "Stack is empty." << std::endl;
            return -1; // You can choose a different value to indicate an error
        }
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == -1;
    }
};

int main() {
    Stack stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.peek() << std::endl;

    std::cout << "Popped element: " << stack.pop() << std::endl;

    std::cout << "Is the stack empty? " << (stack.isEmpty() ? "Yes" : "No") << std::endl;

    return 0;
}

This code defines a ‘Stack’ class that stores its constituents in an array. Using the class’s supplied methods, you can push, pop, look, and verify that the stack is empty.

Conclusion

This article examined the implementation of a stack in C++ using an array. Stacks are flexible data structures that are utilized in numerous computer science applications. They adhere to the Last-In, First-Out (LIFO) principle, which makes them useful for efficiently managing data.

Now that you comprehend the fundamentals of implementing a stack in C++, you can investigate more advanced stack-based applications and algorithms.

Frequently Asked Questions (FAQs)