So hey, in this article we are going to learn to Implement A Stack Using an Array

Why?

Implementing a stack using an array is a common approach in computer programming for several reasons:

1. Efficiency: Arrays offer constant-time access to elements in the array based on their index, which makes it efficient to implement a stack. Pushing and popping elements from an array-based stack can be done in constant time (O(1)), which means that the time complexity of these operations does not depend on the size of the stack. This can be advantageous in terms of time complexity compared to other data structures.

2. Simplicity: Implementing a stack using an array is relatively simple compared to other data structures like linked lists. Arrays are a fundamental data structure in most programming languages, and their usage is widely understood. Implementing a stack using an array can be straightforward to understand, making it an attractive option for simple stack implementations.

3. Memory Management: Arrays have a contiguous block of memory allocated for storing elements, which can be advantageous in terms of memory management. Arrays do not require additional memory allocation compared to linked lists, which may require dynamic memory allocation for each node. In scenarios where memory usage is a concern, an array-based stack can be a more memory-efficient option.

4. Random Access: Arrays allow for random access to elements based on their index, which can be useful in some stack implementations. For example, if there is a need to access elements at arbitrary positions in the stack, an array-based stack can provide faster access compared to a linked list, where traversal may be required.

However, it's worth mentioning that using an array to implement a stack also has some limitations. One major limitation is that the size of the stack may be fixed at the time of array allocation, which can result in wasted memory if the stack size needs to be dynamically adjusted during runtime. Additionally, if the stack size exceeds the allocated array size, it may require resizing the array, which can be an expensive operation. Care should be taken to handle such scenarios appropriately to avoid potential issues.

Code

#include<iostream>
#include<stack>
using namespace std;

class Stack {
    //properties
    public:
        int *arr;
        int top;
        int size;

    // behaviour
    Stack(int size) {
        this -> size = size;
        arr = new int[size];
        top = -1;
    }

    void push( int element) {
        if(size - top > 1) {
            top++;
            arr[top] = element;
        }
        else{
            cout << "Stack OverFlow" << endl;
        }
    }

    void pop() {
        if(top >=0 ) {
            top--;
        }
        else{
            cout << "Stack UnderFlow" << endl;
        }
    }

    int peek() {
        if(top >=0 )
            return arr[top];
        else
        {
            cout << "Stack is Empty" << endl;
            return -1;
        }
    }

    bool isEmpty() {
        if( top == -1) {
            return true;
        }
        else{
            return false;
        }
    }

};


int main() {

    Stack st(5);

    st.push(22);
    st.push(43);
    st.push(44);
    st.push(22);
    st.push(43);
    st.push(44);

    cout << st.peek() << endl;

    st.pop();

    cout << st.peek() << endl;

    st.pop();

    cout << st.peek() << endl;

    st.pop();

    cout << st.peek() << endl;

    if(st.isEmpty()) {
        cout << "Stack is Empty mere dost " << endl;
    }
    else{
        cout << "Stack is not Empty mere dost " << endl;
    }
    return 0;
}

Code Explanation

1. The code includes the necessary header files iostream and stack for input/output operations and stack implementation respectively.

2. A Stack class is defined with the following properties:

   • arr: a dynamic integer array to store the elements of the stack

   • top: an integer to keep track of the top of the stack

   • size: an integer to represent the size of the stack

3. The Stack class has the following behaviors:

   • A constructor Stack(int size) which takes the size of the stack as an argument and initializes the properties of the stack, such as allocating memory for the dynamic array arr, initializing top to -1, and setting the size of the stack.

   • push(int element): a function to push an element onto the stack. It first checks if there is space in the stack (i.e., size - top > 1), and if so, increments the top and stores the element at the corresponding index in arr. If the stack is already full, it displays a "Stack Overflow" message.

   • pop(): a function to pop the top element from the stack. It first checks if the stack is not empty (i.e., top >= 0), and if so, decrements top. If the stack is empty, it displays a "Stack Underflow" message.

   • peek(): a function to get the value of the top element of the stack without removing it. It first checks if the stack is not empty, and if so, returns the element at the top of the stack from arr[top]. If the stack is empty, it displays a "Stack is Empty" message and returns -1.

   • isEmpty(): a function to check if the stack is empty. It returns true if the stack is empty (i.e., top == -1), and false otherwise.

4. In the main() function:

   • An instance of the Stack class named st is created with a maximum size of 5.

   • Elements (22, 43, 44, 22, 43, and 44) are pushed onto the stack using the push() function.

   • The peek() function is called to print the top element of the stack.

   • The pop() function is called twice to remove the top two elements from the stack.

   • The peek() function is called again to print the new top element of the stack.

   • The pop() function is called twice more to remove the remaining elements from the stack.

   • The isEmpty() function is called to check if the stack is empty and display a corresponding message.