LINEAR DATA STRUCTURE : STACK

 What is a stack?

A stack is a linear data structure in which the addition and deletion of data are done from the same end.
This end is often referred to as the top of a stack.

Last-In-First-Out (LIFO) structure.


stack:last in first out


STACK ADT:
DATA: It is a finite sequence of elements of a particular type. (arrays / linked list)
OPERATIONS:
1. Initialize a stack.
2. check whether the stack is empty.
3. check whether the stack is full.
4. Insert at the top of stack if a stack is not full. This operation is called Push.
5. Delete a element from the top of stack if it is not empty. This operation is called Pop.
6. Retrieve an element from the top of stack. This operation is called Peek.


stack
STACK OPERATION


Implementation of Stack:
1. Using Array
2. Using Linked List.


Message Passing Methods in C:
1. Pass by Value / Call by Value.
2. Pass by Address / Call by Address.


Implementation of a stack using arrays

#include<stdio.h>   //pre-processor directive
#include<unistd.h>
#define MAX 5
struct stack
{
    int a[MAX];
    int top;
};
void initialize(struct stack *st)  //called
{
    st->top=-1;  //= ->assignment operator
}
int isEmpty(struct stack *st)
{
    if(st->top==-1)     //IsEmpty condition // == -> conditional or equality operator
        return 1;
    else
        return 0;
}
int isFull(struct stack *st)
{
    if(st->top==MAX-1)  //IsFull condition
        return 1;
    else
        return 0;
}
int push(struct stack *st, int d)  //The task of the push function is to insert a given data          element into a given stack
{
    if(isFull(st))
        return 0;       //stack overflow->Overflow is when your try to add extra item above the defined limit.
    else
    {
        st->top++;
        st->a[st->top]=d;
        return 1;
    }
    
}
void pop(struct stack *st)
{
    int d;
    if(isEmpty(st))
        printf("\nStack is Empty.");       //stack underflow ->Under flow is when you try to get value when there is no data or the list is empty.
    else
    {
        d=st->a[st->top];
        st->top--;
        printf("\nPopped element is %d",d);
    }
}
void peek(struct stack *st)
{
    int d;
    if(isEmpty(st))
        printf("\nStack is Empty.");       //stack underflow
    else
    {
        d=st->a[st->top];
        printf("\nPeak element is %d",d);
    }
}
void display(struct stack st)
{
    int i;
    if(isEmpty(&st))
        printf("\nStack is Empty.");
    else
    {
        printf("\nStack Elements:");
        for(i=st.top;i>=0;i--)
        printf("\n%d",st.a[i]);
    }
}
int main()              //calling
{
    struct stack s;
    int ch,e,chk;
    initialize(&s);
    while(1)
    {
        printf("\n\n\t\t\tMENU");
        printf("\n1. Push.\n2. Pop.\n3. Peek.\n4. Display.");
        printf("\n5. Exit.\n\tEnter your Choice: ");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:
            printf("\nEnter Data Element: ");
            scanf("%d",&e);
            chk=push(&s,e);
            if(chk)
            printf("Successfully Pushed.");
            else
            printf("Stack is Full.");            
            break;
            case 2:
            pop(&s);
            break;
            case 3:
            peek(&s);
            break;
            case 4:
            display(s);
            break;
            case 5:
            exit(0);
            default:
            printf("\nPlease enter correct choice...");
        }
    }
}

output:
menu

  1. push   (Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.)
  2. pop  (Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.)
  3. peek (Returns the top element of the stack)
  4. display ( display the elements that are push in the stack)
  5. exit

Enter your choice:1
11 pushed into stack
22 pushed into stack

33 popped from stack
33 pushed into stack

Application of stack
  1. Stacks can be used for expression evaluation.
  2. Stacks can be used to check parenthesis matching in an expression.
  3. Stacks can be used for Conversion from one form of expression to another.
  4. Stacks can be used for Memory Management.
  5. Stack data structures are used in backtracking problems.

Polish notation

infix: an operator is placed between the operands
for eg:a+b   (a&b are operands & '+' is a operator)

postfix: an operator is placed after the operands
for eg:ab+   (a&b are operands & '+' is a operator)

prefix: an operator is placed before the operands
for eg:+ab   (a&b are operands & '+' is a operator)

Real-life applications of stack

  1. Women’s Bangles
  2. Books,Clothes piled on top of each other
  3. Floors in a building.


























































Comments















Post a Comment