Stack | Data Structure

 

Stack is a data structure which follow the concept of FIFO (First in First Out) /LIFO (Last in last out. In other words stack is structure in which insertion and deletion are possible from only one end.

We use array for making stack.

TOS →Top of stack point to top most element of stack.

Note:

If (TOS == -1) than stack is empty

If (TOS == size-1 than stack is full.

List of basic operations :

1. PUSH

2. POP

3. DISPLAY

4. IS EMPTY

5. IS FULL

6. STACK TOP

7. PEEP

PUSH Operation: 

When we try to insert a new element at the top most position of stack than such operation is called PUSH.

Over Flow: 

If we try to PUSH (insert) a new element & stack is already full than such a situation is called stack overflow.

Algorithm for PUSH (x)

x is new element

STEP 1   : IF TOS== SIZE-1

STEP 1.1: STACK OVER FLOW

STEP 2.1: ELSE

STEP 2.2: TOS = TOS +1

STEP 3   : STACK[TOS] = X

STEP 4   : END IF

STEP 5   : END

PROCEDURE IN C FOR PUSH

int PUSH ( int x, int TOS , int stack[ ],int size)

{        

    if(TOS == size-1)

    {

        printf("Stack Overflow");

    }

    else

    {    

        TOS++;

        stack[TOS]=x;        

    }

    return(TOS);

}

POP Operation :

When we try to remove top most element from stack than such operation is called POP.

Under Flow Condition:

When we try to pop element from the stack and stack is already empty than such a situation is called stack underflow.

Algorithm for POP (X)

STEP 1   : IF TOS == -1

STEP 1.1: STACK UNDER FLOW

STEP 2   : ELSE

STEP 2.1: X=STACK[TOS]

STEP 2.2: TOS =TOS-1

STEP 3   : END IF

STEP 4   : RETURN X

STEP 5   : END 

PROCEDURE IN C FOR POP

int POP(int TOS,int stack[ ])

{

    int x;

    if(TOS==-1)

    {

        printf("Stack under flow");

    }

    else

    {

        x=stack[TOS];

        TOS--;

        printf("POP element is %d\n",x);

    }

    return(TOS);

}

PROCEDURE IN C FOR DISPLAY

void display(int TOS,int stack[ ])

{

    int i;

    printf("Element of STACK:\n");

    for(i=TOS;i>=0;i--)

    {

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

    }

}

PROCDURE IN C FOR CHECKING STACK ISEMPTY

int ISEMPTY ( int TOS )

{

    if (TOS==-1)

    {

        return(1);

    }

    else

    {

        return(0);

    }

}

PROCDURE IN C FOR CHECKING STACK ISFULL

int ISFULL ( int TOS , int size )

{

    if(TOS==size-1)

    {

        return(1);

    }

    else

    {

        return(0);

    }

}

PROCDURE IN C FOR  STACK TOP 

It return top most element of stack.

int stack top ( )

{

    return (stack[TOS] );

}

PROCEDURE IN C FOR PEEP

It return element from any particular position

int peep (int  pos)

{

    if (pos <=TOS +1)

    {

        return (stack[TOS - pos+1]);

    }

    else

    {

        printf("Invalid Position ! ");

    }

Complete Program of implementing Stack 

#include <conio.h>

#include <stdio.h>

int PUSH ( int x, int TOS , int stack[ ],int size)

{        

    if(TOS == size-1)

    {

        printf("Stack Overflow");

    }

    else

    {    

        TOS++;

        stack[TOS]=x;

        //printf("%d",stack[TOS]);

    }

    return(TOS);

}

int POP(int TOS,int stack[ ])

{

    int x;

    if(TOS==-1)

    {

        printf("Stack under flow");

    }

    else

    {

        x=stack[TOS];

        TOS--;

        printf("POP element is %d\n",x);

    }

    return(TOS);

}

void display(int TOS,int stack[ ])

{

    int i;

    printf("Element of STACK:\n");

    for(i=TOS;i>=0;i--)

    {

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

    }

}

int ISEMPTY ( int TOS )

{

    if (TOS==-1)

    {

        return(1);

    }

    else

    {

        return(0);

    }

}

int ISFULL ( int TOS , int size )

{

    if(TOS==size-1)

    {

        return(1);

    }

    else

    {

        return(0);

    }

}

void main()

{

    int x,TOS=-1,size,stack[10],ch=0;

    printf("Enter the size of stack:");

    scanf("%d",&size);

    printf("\n"); 

    do

    {

        printf("\nSelect Operation\n");

        printf("1-PUSH  2-POP  3-Display 0-Exit:");

        scanf("%d",&ch);

        switch (ch)

        {

        case 1:

        {

        int f;

        f=ISFULL(TOS,size);

        if(f==0)

        {

            printf("Enter the element PUSH into stack:");

            scanf("%d",&x);

            TOS=PUSH(x,TOS,stack,size);

            display(TOS,stack);

        }

        else

        {

            printf("Stack is full !");

        }  

        break;

        }   

        case 2:

        {

        int e;

        e=ISEMPTY(TOS);

        if(e==0)

        {

            TOS=POP(TOS,stack);

            display(TOS,stack);

        }

        else

        {

            printf("Stack is empty!");

        }

        break;

        }

        case 3:

        {

        display(TOS,stack);

        break;

        }

        default :

        printf("NONE");    

    }

    } while(ch!=0);

    

    getch();

}