Stack Implementation using Array

The Stack data structure can be easily implemented using a 1D array. You can easily perform all the basic stack operations like push(), pop(), peek(), and isEmpty() in constant time O(1) without using any loop and by following the LIFO (Last In First Out) principle.

To implement all the stack operations, you need one fixed-size array and a very important variable name top that always points to the topmost element of the stack data structure. In your case, the top variable is going to hold the index of the top element of the stack.

Initially, the top is initialized with a -1 value which means that your stack is empty and if you met a condition when (size of the array - top) is less than 1 then you can say your stack is full.

Stack operations using Array.

push(): It is a function used to insert an element at the top of the stack.

Check if the stack is full or not. When (SIZE - 1 == top), "STACK is FULL" you cannot insert any further value to terminate the function.
If (SIZE-1 is not equal to top), increment the top value by 1 (top++) and initialize arr[top] = value.

pop(): It is a function used to delete an element from the top of the stack.

Check if the stack is empty or not. When top == -1, "STACK IS EMPTY" there is no element present to delete so terminate the function.
If top > -1, delete the top element by decreasing the top value by one. (top--).

peek(): It is a function that returns the topmost value present in the stack.

Check if top == -1, the stack is empty so there is no element present in the stack.
If top > - 1, return the top value using arr[top].

isEmpty(): It is a function to check if the stack is empty or not. If the stack is empty return TRUE else return FALSE.

If top == -1, return true else return false.

Stack Implementation using Array

Example: C++ code for Implementation of Stack using Array.

#include <bits/stdc++.h>
using namespace std;

class Stack
{
public:
    // integer type pointer
    int *arr;
    int top;
    int size;
    // behaviour
    Stack(int size)
    {
        this->size = size;
        // dynamically allocating memory
        arr = new int[size];

        top = -1;
    }
    // function to push element in stack
    void push(int element)
    {
        if (size - 1 == top)
        {
            cout << "Stack OverFlow" << endl;
        }
        else
        {
            top++;
            arr[top] = element;
        }
    }
    // function to pop element in stack
    void pop()
    {
        if (top == -1)
        {
            cout << "Stack is Empty" << endl;
        }
        else
        {
            top--;
        }
    }
    // function to peek element in stack
    int peek()
    {
        if (top == -1)
        {
            cout << "stack is empty !!" << endl;
            return -1;
        }
        else
        {
            return arr[top];
        }
    }
    // check if stack is empty or not.
    bool isEmpty()
    {
        if (top == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

int main()
{
    Stack s(5);

    s.push(20);
    s.push(30);
    s.push(40);
    s.push(50);

    cout << "Top Element: " << s.peek() << endl;
    // delete the top element of the stack which is now 50
    s.pop();
    // top element after deleting 50
    cout << "Top Element: " << s.peek() << endl;

    if (s.isEmpty())
    {
        cout << "Stack is Empty !!!" << endl;
    }
    else
    {
        cout << "Stack is not Empty !!!" << endl;
    }
}

Output:

Top Element: 50
Top Element: 40
Stack is not Empty !!!

Implementation of Stack using Array is easy to use but it is not dynamic in nature so we can increase or decrease the size of Stack at runtime. To solve this problem, you can use Linked List for the implementation of Stack because as we know that the size of the Linked List data structure is not fixed.

Stack Implementation using Array | C++ Code

Stack operations using Array.

Example: C++ code for Implementation of Stack using Array.

No comments:

Post a Comment