DATASTRUCTURE AND ALGORITHM PART 3

What is stack? How the stack will be implemented?

Stack is an ordered  collection of data item into which new data may be inserted and deleted at one end called the top of stack. It is dynamically changing object.

A stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data. A stack is a restricted data structure because only a small number of operations are performed on it (push and pop).

The contiguous implementation of stack as array is:

1.      TOS (Top of Stack) vary

2.      TOS fixed

Algorithm for TOS vary

Push Algorithm

if stack is not full

§  add 1 to sp or increment sp.

§  store the data item at the top of stack or sp location

Pop Algorithm

If stack is not empty

§  read data item at sp location

§  Decrement sp by 1.

Algorithm for TOS vary

Push Algorithm

If stack is not full then,

§  shift the entire item up to new sp

§  store data item at 0 sp location

Pop Algorithm

§  Read the item

§  If the item at 0 location is not special character then,

§  print the item at 0 location

§  shift the entire item at the stack down to new sp.