Tuesday, August 19, 2008

Stack ( ADT ) Data Structure

* Stack is an Abstract data structure (ADT) works on the principle Last In First Out (LIFO)
* The last element add to the stack is the first element to be delete.
* Insertion and deletion can be takes place at one end called TOP.
* It looks like one side closed tube.

* The add operation of the stack is called push operation
* The delete operation is called as pop operation.
* Push operation on a full stack causes stack overflow.
* Pop operation on an empty stack causes stack underflow.
* SP is a pointer, which is used to access the top element of the stack.
* If you push elements that are added at the top of the stack;
in the same way when we pop the elements, the element at the top of the stack is deleted.,

For example the following Fig give an idea about the stack.

From the above Fig 01 it is clear that the size of the stack is having 4Locations and sp = -1 indicates that the stack is empty and we can push the new elements into the stack. Now the fig 02 shows how the stack grows, when we push an elements 12, 13, 14 into the stack. The fig 03 shows the status of the stack after popping 2 times. Now performing (one more) pop operation one more time on the above stack causes an error known as "stack under flow". The fig 04 shows the content of the stack after pushing 16, 17, 18, and 19. If you try to add one more element stack generate error "stack overflow".

Operations of stack:

There are two operations applied on stack they are 1 push 2. pop. While performing push & pop operations the following test must be conducted on the stack.

1) Stack is empty or not

2) Stack is full or not


Push:

Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".

Pop:

Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".

Assumptions:

SP stack pointer whose initial value is -1

max_stack is the size of the queue

stack [] is an array

Element is the elements to be added or deleted

Algorithm to push elements into the stack :-

step :- 1) start

step :- 2) take the element to push into stack

step :- 3) If (Sp == max_stack)

display "The stack overflow"

else

{ Sp = Sp+1

stack [Sp] = item
}

step :- 4) return to main program

Algorithm to pop elements from the stack :-

step :- 1) start

step :- 2) if (Sp == -1)

display "stack underflow"

else

{ element = stack[Sp]

Sp = Sp -1
}

step :- 3) return element

Click to see C++ Stack Array Linked List

0 Comments:

 
^ Scroll to Top