STACKS


 StacksDEFINITION1:   Stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end.

DEFINITION2: Stack is a linear list in which insertions and deletions take place at the same end.

The end at which the operations are taking place is called top

The other end is called bottom

Ex:

T<-top

J

K

S

F<-bottom

This is LIFO (Last-in-first-out) structure.

The insertion of element into stack is called push

The deletion of element from stack is called pop.

OVERFLOW:

This situation will come when the stack is implemented using an array.

If an element is pushed into the stack when the size of the stack greater than or equal to maximum size of the array, then we say that the stack is overflowing.

Underflow:

If deletion operation is performed on the stack with no elements then the stack is said to be underflowing .This occurs in both types of implementations of stack.

Algorithm for push operation:

Push(key,top):(Array implementation of stack)

1)If(top>=maximum size of the stack)

  i)Then print “Stack is overflowing”

2)Else

   i)Stack[top]=key;

  ii)top=top+1;

Algorithm for pop operation:

Pop():

1)if(top=0)

          1)print “The stack is underflowing”

2)else

          return stack[–top]

Applications of stack :

1)parenthesis matching

2)Towers of Hanoi

3)Rearranging rail road cars

4)Rat in a maze.

NOTE:

I am writing this notes by referring to the following reference books. The students who are new to data structures are being advised to refer to “CLASSICAL DATA STRUCTURES” by SAMANTHA.

References:

1) Data structures, Algorithms &Applications in c++   by SAHNI

2)classic data structures by  SAMANTHA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s