Stack and Application of stack

 

Stack and  Application of stack

Stack is linear data structure.

Stack use LIFO(Last in first out)which an element may be inserted or deleted at one end called the top of the stack.

Stack has two basic operation.

Push  is the term used to insert the element into a stack.

Pop is the term used to delete an element from a stack.

Algorithm to push an ITEM onto a stack.

PUSH(STACK,TOP,MAXSTK,ITEM)

Step 1: If TOP=MAXSTK then print OVERFLOW and return.

Step 2: Set TOP=TOP+1.

Step 3: Set STACK[TOP]=ITEM.

Step 4: Return.

Algorithm to pop an element  from Stack

POP(STACK,TOP,MAXSTK,ITEM)

Step 1: If TOP=NULL then print UNDERFLOW and return.

Step 2: Set ITEM=STACK[TOP].

Step 3: Top=Top-1.

Step 4: Return.

Application of  Stack

• Infix to Postfix conversion.
• Evaluate Postfix expression.
• Tower of Hanoi.
• Recursion.
• In graph traversal(Depth first search). 

Infix to Postfix conversion

Before Evaluation expression is first convert infix to postfix expression.So need of stack for conversion expression infix to postfix.

Example

Infix expression 2+3.

Postfix expression  23+. 

Evaluate Postfix expression

Postfix expression is evaluate using stack.Operand is push on Stack and if operator occur then pop two top element from the stack and applied operation.

Example

Postfix expression 23+

Result after evaluation using stack 5. 

Recursion 

Recursion refers to the process in which function call itself.Recursion is a technique using which some problems can be expressed in a form which is very close to their natural statement.

 In graph traversal (Depth first search)

To Processed or traverse every node of a graph depth first technique use stack .Stack is used to hold nodes that are waiting to be processed and by using a field STATUS which tells us the current status of any node.

Example

Evaluate Postfix expression  P= 5,5,2,+,*,10,2,/,-

Solution

Scanned Symbol                Stack

       5                                     5

       5                                     5,5

       2                                     5,5,2

      +                                      5,7

      *                                       35

      10                                    35,10

       2                                     35,10,2

       /                                      35,5

        -                                     30

       )                      

               

  So answer of postfix expression is 30. That  postfix expression evaluate using Stack.