Stack Algorithm PDF

Preview

Summary

stack algorithm detailed...

Description

Stacks “A stack is a list in which insertion and deletion take place at the same end”. This end is called top The other end is called bottom Stacks are known as “LIFO” (Last In, First Out) lists.

Stack operation: There are four basic operations,    

Is stack full() push(); pop() ; Is empty();

Algorithms Algorithm for push operation: If top>=size-1 then Write “stack is overflow” Top=top-1 Stack[top]=x Algorithm for pop operation: If top= -1 then Write “stack is underflow”

Return stack[top] Top=top-1

Stack operation using array

A stack can be implemented using array as fallows: Include all header files and define the constant size with the specific value. Declear all function used in stack implementation. Create one dimensional array with the fixed time(int stack[size]). Define an integer variable top and initialize with -1(int top=-1) In main method display menu with list of operation and make suitable functions calls to perform operation selected by the user on the stack. Push value(inserting value into the stack):  Check whether stack is full If top>=size-1 then Write “stack is overflow” If it is not full then increment by top value by one(top+ +0 Stack[top]=value. pop value(Deleting value into the stack):

 Check whether stack is empty [top= -1 ]then Write “stack is underflow” If it is not empty then Return stack[top] Top=top-1. Display() [Display the element of a stack]: Check whether stack is empty[top=-1] then Display “stack is empty” If it is not empty then define a variable “I” initializes.display stack[i] value and decrement value by one[top--]. Repeat above statement until I vaule becomes “0”.

Stack expression Post fix expression: Algorithm: operand_stack = empty stack while (not end of input) symbol = next input symbol if (symbol is operand) push(operand_stack, symbol) else operand2 = pop(operand_stack) operand1 = pop(operand_stack)

result = apply symbol to operand1 and operand2 push(operand_stack, result) return pop(operand_stack)

convert infix to postfix Algorithm: set operator_stack to empty stack while (not end of input) symbol = next input if (symbol is operand) add symbol to postfix string else while (operator_stack not empty and top element has higher precedence than symbol) pop top element and add it to postfix string push symbol onto operator_stack while (operator_stack not empty) pop top element and add it to postfix string so far: only infix without parentheses  "(" increases precedence of operators to the right and therefore delays operators on the stack ")" just"flushes" all operators on the stack until it finds its matching "(“ Recursion If N=0 then

Factorial=1 PRINT “factorial =” factorial RETURN End if Factorial =1 REPEAT FOR C=1 To N By 1 Factorial=factorial*C [End of loop] PRINT “factorial=” factorial  EXIT...