Thursday, 14 December 2017

Write an algorithm to implement the Stack ADT using arrays.

Definition of Stack ADT : A stack is an ordered collection of data items into which new items may be inserted and from which data items may be deleted at one end. Stack are also called Last-In-First-out (LIFO) lists.

Basic terminology associated with Stacks:
1) Stack Pointer (TOP) : Keeps track of the current position the stack.
2) Overflow : Occurs when we try to insert (push) more information on a stack than it can hold.
3) Underflow : Occurs when we try to delete (pop) an item off a stack, which is empty.

Basic Operation Associated with Stacks:
1) Insert (Push) an item into the stack.
2) Delete (Pop) an item from the stack.

a) Algorithm For Inserting an Item into the Stack S:
Procedure PUSH(S, SIZE, TOP, ITEM)
S           Array
SIZE     Stack size
TOP     Stack Pointer
ITEM value in a cell
Step 1: {Check for stack overflow}
If TOP==SIZE then
Prints(‘Stack overflow’)
Return
Step 2: {Increment pointer top}
TOP=TOP+1
Step 3: {Insert ITEM at top of the Stack}
S[TOP]=ITEM
Return

b) Algorithm for Deletion of an Item from the Stack S
Procedure POP(S, TOP)
S Array
TOP Stack Pointer
Step 1: {Check for stack underflow}
If TOP==0 then
Prints(‘Stack underflow’)
Return
Step 2: {Return former top element of stack}
ITEM=(S[TOP]);
Step 3: {Decrement pointer TOP}
TOP=TOP-1
Prints(‘Deleted item is:’,item);
Return

c) Algorithm to display the items of a Stack S
Procedure POP(S, TOP)
S Array
TOP Stack Pointer
Step 1: {Check for stack underflow}
If TOP==0 then
Prints(‘stack is empty’)
Return
Step 2: {display stack elements until TOP value}
Prints(S[TOP])
TOP=TOP+1

d) Algorithm to display top item of the Stack S
Procedure POP(S, TOP)
S Array
TOP Stack Pointer
Step 1: {Check for stack underflow}
If TOP=0 then
Prints(‘stack is empty’)
Return
Step 2: {display TOP value into the Stack}
Prints(S[TOP])


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput