Stack

The stack was first proposed in 1946, in the computer design of Alan M. Turing (who used the terms “bury” and “unbury”) as a means of calling and returning from subroutines.

A stack is a list of elements in which an element may be inserted or deleted only at one end called the TOP of the stack. It is Last In First Out (LIFO) or First In Last Out (FILO) data structure. Elements are removed in the reverse order of which they were inserted into the stack.

Examples: Stack of Dishes, Stack of Books, A packet of biscuits, etc.

AVAIL LIST (List of free memory spaces) is also implemented using Stack.

Algorithm: (Array representation)

– Inserting elements into the stack –

PUSH (STACK, TOP, MAXSTK, DATA)

  1. If TOP = MAXSTK, then, write: overflow and exit.                //checking the stack is full or not
  2. Set TOP = TOP+1.                                  //Increasing TOP by 1
  3. Set STACK [TOP] = DATA.                   //Inserting DATA into the TOP
  4. Exit.

//STACK: Name of the stack

//TOP: Pointer that points to the topmost element of the stack

//DATA: information/data to be inserted.

//MAXSTK: Maximum index of the stack (maximum size)

– Deleting elements from the stack –

POP (STACK, TOP, DATA)

  1. If TOP = 0, then, write: underflow and Exit.        //checking for underflow
  2. Set DATA = STACK [TOP]               //DATA is the TOP element
  3. Set TOP = TOP-1                               //decreasing the size of the STACK
  4. Exit

 

Author: Sonia Behal

Advertisements

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