Pages

Saturday, April 13, 2013

Stack In Data Structure with algoritham


Stack is one of the Linear data structure (Non-primitive data structure).  In stack, Insert Operation & delete Operation are performed at one end i.e. on the top of the stack.
Stack is the linear data structure having collection of elements which follows LIFO (Last In First Out) pattern i.e. element which comes last is served first.
One of the best applications where stack can be viewed is, Shipment in Cargo. For the shipment of goods, they have to be loaded into a cargo. While for unloading they are unloaded  in opposite sequence of  loading. That is, the last goods loaded should be unloaded first.
In stack Insert operation is known as PUSH and deletion is known as POP and the position of the stack where these operations are performed is known as TOP of the stack.
Operations on STACK :
Basic operations required to manipulate a stack are:
PUSH : To insert an item into the stack
POP : To remove an item from a stack.
PEEP : To find ith element from stack.
CHANGE : To change ith element from stack.
Initially top of the stack is zero as there is no element in stack, top is incremented by one as element is added to stack i.e. PUSH Operation and top is decremented by one when element is deleted from stack i.e. POP operation.
Application of Stack :
1. Recursion
2. Polish expressions and their compilation
3. Stack machines
Let us see Pseudo code or Algorithm of each stack operation.
PUSH Operation
PUSH (S, TOP, X)
Step – 1: [Check for Stack overflow]
If TOP > N then
Write (‘Stack Overflow’)
Return
Step – 2 : [Increase value of TOP]
TOP <- TOP + 1
Step – 3 : [Insert element into stack]
S[Top] <- X
Step – 4: [Finished]
Return
POP Operation
POP(S, TOP)
Step – 1: [Check for Stack Underflow]
If TOP == 0 then
Write (‘Stack Underflow’)
Return
Step – 2 : [Decrease value of TOP]
TOP <- TOP – 1
Step – 3 : [Return top element of stack]
Return S[Top + 1]
PEEP Operation
PEEP(S, TOP, i)
Step – 1: [Check for Stack Underflow]
If TOP- i +1 < 0 then
Write (‘Stack Underflow For PEEP’)
Return
Step – 2 : [Return ith element from top of stack]
Return S [Top – i + 1]
CHANGE Operation
Change(S, TOP, i, X)
Step – 1: [Check for Stack Underflow]
If TOP- i +1 < 0 then
Write (‘Stack Underflow on Change’)
Return
Step – 2 : [Change ith element from top of stack]
S[Top – i + 1] <- X
Step – 3 : [Finished]
Return

0 comments:

Post a Comment