Understanding the Stack Data Structure

Stacks

In this article, we’ll be understanding the working and the need for the Stack Data Structure.

When programming, we often deal with a huge amount of uneven and raw data. This calls for the need of data structures to store the data and enable the user to operate on the data efficiently.


Getting started with the Stack Data Structure

A stack is a linear data structure that follows a particular order for the insertion and manipulation of data. Stack uses Last-In-First-Out (LIFO) method for input and output of data.

A stack occupies elements of a particular data type in it in a pre-defined order i.e. LIFO.

Stack
Stack

As seen in the above pictorial representation of stack, the last element is the first to be popped out from the stack.

The insertion and deletion of data items take place from the same end of the stack.

Let’s try to relate stacks with real-life scenarios.

Consider a pile of books. If you observe, the last book placed would be the first one to be accessed by us. Moreover, a new book can be placed only at the top of the pile. Thus, depicting the working of Stacks.


Operations Performed on a Stack

The Stack data structure primarily deals with the following operations on the data:

  • push(): This function adds data elements to the stack.
  • pop(): It removes the top element from the stack.
  • top(): Returns the topmost element i.e. element at the top position of the stack.
  • isEmpty(): Checks whether the stack is empty or not i.e. Underflow condition.
  • isFull(): Checks whether the stack is full or not i.e. Overflow condition.

Working of the Stack Data Structure

Stack data structure follows the LIFO pattern for the insertion and manipulation of elements into it.

Note: We have set a pointer element called ‘top‘ to keep the account of the topmost element in the stack. This would help the insertion and deletion operation to be performed in an efficient manner.

PUSH (insertion) operation:

  • Initially, it checks whether the stack is full or not i.e. checks for the Overflow condition.
  • In case the stack is found to be full, it will exit with an Overflow message.
  • If the stack is found to have space for occupying elements, then the top counter is incremented by 1 and then the data item is added to the stack.

POP (deletion) operation:

  • Initially, it checks whether the stack is empty or not, i.e. checks for the Underflow condition.
  • In case the stack is found to be empty, it will exist with an Underflow message.
  • If the stack is not empty, display the element pointed by the top pointer element and then decrement the top pointer by 1.

Implementation of the Stack Data Structure

Stack can be implemented using either of the following ways:

  • Linked List
  • Array

We’ve already written a comprehensive article on Stack in C++. For the demonstration, I’ll create a simple implementation of a stack using an Array in C++ language.

Example:

# include<iostream>
using namespace std;

class stack_data
{
    public:
    int top;
    int data[5];  
    stack_data()
    {
        top = -1;
    }

    void push_element(int a);
    int pop_element();
    void isEmpty();
    void isFull();
    void display();
};


void stack_data::push_element(int a)
{
    if(top >= 5)
    {
        cout << "Overflow\n";
    }
    else
    {
        data[++top] = a;
        
    }
}


int stack_data::pop_element()
{
    if(top < 0)
    {
        cout << "Underflow\n";
        return 0;
    }
    else
    {
        int pop = data[top--];
        return pop;
    }
}


void stack_data::isEmpty()
{
    if(top < 0)
    {
        cout << "Stack Underflow\n";
    }
    else
    {
        cout << "Stack can occupy elements.\n";
    }
}

void stack_data::isFull()
{
    if(top >= 5)
    {
        cout << "Overflow\n";
    }
    else
    {
        cout << "Stack is not full.\n";
    }
}

void stack_data::display()
{
    for(int i=0;i<5;i++)
    {
        cout<<data[i]<<endl;
    }
}

int main() {

    stack_data obj;
    obj.isFull();
    obj.push_element(40);
    obj.push_element(99);
    obj.push_element(66);
    obj.push_element(40);
    obj.push_element(11);
    
    cout<<"Stack after insertion of elements:\n";
    obj.display();
  
    cout<<"Element popped from the stack:\n";
    cout<<obj.pop_element()<<endl;
    
    
}

Output:

Stack is not full.
Stack after insertion of elements:
40
99
66
40
11
Element popped from the stack:
11

Features of Stack

  • Stack follows Last-In-First-Out fashion to deal with the insertion and deletion of elements.
  • The insertion and deletion of data items happen only from a single end.
  • Stack is considered to be dynamic in nature i.e. it is a dynamic data structure.
  • Stacks do not occupy a fixed size of data items.
  • The size of the stack keeps changing with every push() and pop() operation.

Applications of Stack

  • In programming, Stack can be used to reverse the elements of an array or string.
  • A stack can be useful in situations where Backtracking is necessary such as N-queens problem, etc.
  • In editors, the undo and redo functions can be performed efficiently by Stack.
  • Infix/Prefix/Postfix conversion of Binary Trees.

Time Complexity of Stack Operations

  • Push operation i.e. push(): O(1)
  • Pop operation i.e. pop(): O(1)

The time complexities of push() and pop() operations stay O(1) because the insertion and deletion of the data items happen only from one end of the stack which is a single step process to be performed.


Conclusion

Thus, in this article, we have understood the need for and implementation of a Stack data structure in various programming applications.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages