Breif about STACK

I entered elements as 6 and later selected pop option, then it will delete the top element and decreases the top value by1, pointing to the next bottom element.

Note: deleting in the sense moving the pointer to the bottom level by one.

What is stack?

It is a linear data structure, which allows the elements to follow the last in first out or first in last out property.

Real-time example to understand what is a stack

Consider a DVD stack,

If we have to insert a DVD into the stand, then we have to insert from the top of the stand, and while we have to take out the last DVD, we have to first take out all the DVD's which are above to it, then we have to take the last one. This is the same phenomenon in which the stack data structure follows. The top element/DVD in the top of the stand/stack is considered to be the top of the stack.

The operations which are performed in the stack are:

  • Push
  • Pop
  • Peek
  • Display

PUSH:

Stack uses this method to insert the elements into it. In this insertion and deletion will occur at the same end. Time complexity is O(1).

Example:

Now if we want to insert 6, we have to call push(6), then 6 will be inserted at the top of the stack.

POP:

This is used to delete the elements from the stack. Time complexity is O(1).

Example:

if we want to insert 6, we have to call push(6), then 6 will be inserted at the top of the stack.

if we want to delete 6, we have to call pop(6),

Peak:

It displays the peak/top element of the stack. Time complexity is O(1).

Now, if we call peak(), then it will display the value as 4.

Display:

It is used to display the elements in the stack at the particular instance. For that, we have to call display() function. Time complexity is O(1).

Application of Stacks:

  • Towers of Hanai.
  • Backtracking
  • N-queens.
  • Infix to postfix
  • Topological sorting
  • Depth-first search

PUSH:

in push function we have to scan the element we have to enter and pass the element into the push function, so below is the logic of the push function.

Initially, it checks whether the stack is full or not, if it is full, it will show the error message as full, full indicates our defined capacity is full of elements. Else we have to increase the top because, initially we have declared top as -1, i.e, top is not pointing to any block after it is incremented it points to the first block where the first element is inserted there the procedure continues.

Push methods check for the space in the stack through the isFull function which is predefined.

If after inserting some elements, an automatically top value is incremented, when top reaches to the size of capacity, there we have no place to insert.then this will return 1 and trigger the if loop in the push function else it will trigger the else loop in the push function.

The output of push function:

When we select push and enter the elements which we want to insert, it popups the, message element inserted, and when it meets the size, then the below figure shows as the example.

 

POP:

This function didn’t take any arguments because, as per the law of stack, we have to remove the topmost element first, then we have to traverse down to pop the bottom element.

It checks for the status of the stack through isEmpty function. If its true, it returns 0, else it returns the top of the stack.

isEmpty function returns1 if the stack is empty and triggers the if loop in the pop function.

 

 

Pop function output is captured by the element and returns underflow message if the stack is empty, else return the popped element.

Output:

I entered elements as 6 and later selected pop option, then it will delete the top element and decreases the top value by1, pointing to the next bottom element.

Note: deleting in the sense moving the pointer to the bottom level by one.

 

After removing all, if we again select the pop function it shows the message as sate is underflow!!.

PEAK:

This function returns the top element of the stack. This also uses the isEmpty function to determine the status of the stack.

Output:

I entered the elements 4, 6, 8 and I called the peak function, where it returned the 8 as the peak element.

DISPLAY

This also uses isEmpty to find the status of the stack. If it is empty it will show the empty message else, it will print all the elements of the stack.

Output:

Program for implementation of stack:

#include<stdio.h>

#include <stdlib.h>

#define CAPACITY 5

void push(int);

int pop();

int isFull();

int isEmpty();

void display();

void peak();

int stack[CAPACITY],top=-1;

int main()

{

    int choice,element;

    while(1)

    {

    printf("1.push\n");

    printf("2.pop\n");

    printf("3.peak\n");

    printf("4.traverse\n");

    printf("5.quit\n");

    printf("enter your choice:\n\n");

    scanf("%d",& choice);

    switch(choice)

    {

        case 1: printf("enter element to push\n\n");

                scanf("%d",&element);

                push(element);

                break;

        case 2: element=pop();

                if(element==0)

                {

                    printf("stack is underflow\n\n");

                }

                else

                {

                    printf("poped element %d\n", element);

                }

                break;

        case 3: peak();

                break;

               

        case 4: traverse();

                break;

        case 5: exit(0);

                break;

        default: printf("invalid input\n\n");

                break;

    }

    }

  return 0; 

}

void push(int element)

{

   if(isFull())

   {

    printf("stack is full\n\n");  

   }

   else

   {

   top++;

   stack[top]=element;

   printf("element inserted %d \n\n",element);

   }

}

int isFull()

{

    if(top== CAPACITY-1)

    {

        return 1;

    }

    else

    {

        return 0;

       

    }

}

int pop()

{

    if(isEmpty())

    {

        return 0;

    }

    else

    {

        return stack[top--];

       

    }

   

}

int isEmpty()

{

    if(top==-1)

    {

        return 1;

    }

    else

    {

        return 0;

    }

   

}

void peak()

{

    if(isEmpty())

    {

        printf("stack is empty\n\n");

    }

    else

    {

        printf("peak element is %d\n\n", stack[top]);

    }

}

void traverse()

{

     if(isEmpty())

    {

        printf("stack is empty\n\n");

    }

    else

    {   int i;

        for(i=0;i<=top;i++)

        {

            printf("%d \n\n", stack[i]);

        }

    }

   }

Conclusion:

The stack data structure is used to store the data In the sequence of first in last out, to serve some business needs and to overcome the issues in the stack another data structure named queue is implemented which follows the pattern of first in first out manner.

 

 

 

 

 

Contributor's Info

Created: Edited:
0Comment