Facebook

Stacks

Stacks are the linear data structure which stores data in an ordered way.The first element inserted is at the bottom and last element is at the top.It can be implemented using an array or a linked list.It is a LIFO(Last In First Out) data structure.This means that last element inserted will be first element to be removed incase of deletion operation(Fig 1,2).

Examples of Stack

  • Stack of plates.The last plate added is the first one to be removed.
  • A stack of files(Fig 1) .
  • A girl wearing bangles.The last bangle on the arm is the first one to be removed.
  • Luggage placed in truck.
Fig 1 : A Stack of Files
Fig 1 : A Stack of Files
Fig 2  : A Stack
Fig 2 : A Stack

Array Representation of Stack

In stack,the first element is at bottom(0 position) and last element at TOP position.The topmost element of stack is represented by TOP variable.MAX variable is used to store the maximum no of elements that the stack can hold(Fig 3).

  • if TOP =MAX-1,then stack is full.
  • if TOP = NULL,then stack is empty.
Fig 3 : A Stack
Fig 3 : A Stack

 

 

 

Operations on Stack

Each function in a stack runs in O(1) time.

Fig 3 : Push & Pop Operation
Fig 4 : Push & Pop Operation in Stack

 

PEEP Operation

This operation  first checks whether the stack is empty or has some elements(if TOP == NULL) and returns the value of topmost element without deleting it from the stack.In Fig 10, PEEP operation will return 100 to user.

Screen Shot 2014-04-08 at 5.29.36 PM
Fig 10 : A Stack

Applications of Stack

  • Converting a decimal number into binary.
  • Towers of Hanoi
  • Evaluation  of expression and syntax parsing.

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar