Stack data structure

In the stack data structure, we will cover following:-

What is Stack?
Main operations of stack
Applications of stack
Stack implementation in C language
Stack implementation in Java

What is stack?
A stack is a hypothetical data structure which is nothing but restricted form of an array. The word hypothetical means, it is a programmer define data structure and it is actually an array with certain restrictions.
These restrictions are:-
1) A stack is open from one end and by close from the other end. This means that insertion and deletion of elements in stack takes place from one end.
2) A stack is an ordered collection of data. The term ordered means programmer has to follow certain rules by inserting and deleting elements from a stack. This rule is Last in fist out(LIFO) or First in last out(FILO) which means that will grow from bottom to top and will be remove from top to bottom.
3) To work with stack, we require two things, an array to hold values and a pointer called tos to hold indexes, but it just a variable which can hold indexes of the array.
All insertion and deletion takes place with the help of tos(top of the stack).
4) Since stack is a special data structure, the process of inserting element in a stack is called push while the process of deleting element from a stack is called pop.

Example:-

Note:- If stack is empty than tos points at -1 index position.

Main Operations of stack:-
Mainly the following two basic operations are performed in the stack:-
1. void push (int data):- inserts data in a stack
2. int pop( ):- delete and returns the last inserted element from the stack

Push operation of stack:- push operation of stack involves a series of steps-
step 1- Check whether the stack is full or not.
step 2- If stack is full then print the message "stack overflow" and return.
step 3- If stack is not full then increment tos by one.
step 4- Place the element in the stack at the position where tos is pointing.
step 5- finish and return.

Pop operation of stack:- pop operation of stack involves a series of steps-
step 1- Check whether the stack is empty or not.
step 2- If stack is empty then print the message "stack underflow" and return.
step 3- If stack is not empty then remove the element from the stack at which tos is pointing.
step 4- Decrement the value of tos by one.
step 5- Return the deleted element.

Time complexities of operations on stack:- Time complexity will be O(1) because we do not run any loop in any of these operations.

Applications of stack:- There are following some important applications of stack-
1) Infix to postfix/prefix conversion
2) Evaluation of postfix/prefix/infix expression
3) Balancing of symbols
4) Implementing function calls
5) Recursion
6) Auxiliary data structure for other algorithms like- tree traversals algorithm, backtracking
7) Undo sequence in text editor
8) Matching tags in HTML and XML

Implementation of stack in C:-