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)
- If TOP = MAXSTK, then, write: overflow and exit. //checking the stack is full or not
- Set TOP = TOP+1. //Increasing TOP by 1
- Set STACK [TOP] = DATA. //Inserting DATA into the TOP
//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)
- If TOP = 0, then, write: underflow and Exit. //checking for underflow
- Set DATA = STACK [TOP] //DATA is the TOP element
- Set TOP = TOP-1 //decreasing the size of the STACK
Author: Sonia Behal