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.
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.
Operations on Stack
Each function in a stack runs in O(1) time.
- Push - Refer Push Operation in Stacks
- Pop - Refer Pop Operation in Stacks
- Peep - return topmost value
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.
Applications of Stack
- Converting a decimal number into binary.
- Towers of Hanoi
- Evaluation of expression and syntax parsing.