Stack

Algorithms of Stack:

Definition: A Stack is a linear data structure in which both insertion and deletion operations are performed only at one end. The end where insertion and deletion takes place is called the top of the stack or stack top.

·         A Stack also referred as Last in fast out (LIFO).

·         A Stack is an abstract data type that supports the following operations:

Operation	Description
isEmpty()	Check whether the stack is empty.
isFull()	Check whether the number of items in the stack is equal to the maximum allowable capacity of the stack.
push()	Store data items until stack full condition is reached.
pop()	Retrieve elements from the stack until the stack is empty.

Algorithms using Array:
   The simplest way to represent stack is by using one dimensional array, say stack[0 : SIZE-1], where SIZE is the maximum number of allowable entries. The first or bottom element in the stack is stored at stack[0], the second at stack[1], and the i^th at stack[i-1]. Associated with the array is a variable, typically called top which points to the top element in the stack.   

Insertion Algorithm:

      Push an element onto the stack. Return true if successful; else return false. item is the element is to be pushed. Intially top is set to -1.

           Push( Stack, top, SIZE, item)
           {
                 if( top ≥ SIZE-1 ) then
                 {
                          write("Stack is full");
                          return false;
                  }
                  else
                  {
                         top := top+1;
                         stack[top] := item;
                         return true;
                   }

           }

Deletion Algorithm:

         Pop the top element from the stack. Return true if successful; else return false. item is used as output variable.

           Pop( Stack, top, SIZE, item)
           {
                 if( top < 0 ) then
                 {
                          write("Stack is Empty");
                          return false;
                  }
                  else
                  {
                         item := stack[top];
                         top := top-1;
                         return true;
                   }
           }
      Downloads:
             Program: Implementation in C
             Output:            

                Program: Implementation in c++ 
                Output:

         Program: Implementation in JAVA

Application Of Stack:

1. Converting to infix expression to postfix expression.
2. Converting to infix expression to prefix expression.
3. Evaluation of postfix Expression.
4. Evaluation of prefix Expression.