Stack is a data structure that follows the policy of LIFO (Last In First Out). That is the element which is added at the end will be the first to be deleted.
Stack is a very import data structure and is used widely. Some of the important applications of stacks include:
Reversing a word / line
A simple example of stack application is reversal of a given line. This can be accomplished by pushing each character on to a stack as it is read. When the line is finished , characters are then popped off the stack and they will come off in the reverse order.
Browser
Browser also uses stack to store the sites visited by the user. On clicking back button we are taken to previous sites visited.
Recursion
The compiler uses stack to store the previous state of a program when a function is called or during recursion.
Syntax Parsing
Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code.
Backtracking
Another important application is backtracking (backtracking is a form of recursion, but it involves choosing only one option out of the possibilities.) Backtracking is used in large number of puzzles like Sudoku and in optimization problem such as knapsack.
Parenthesis Checking
Stack is used to check the proper opening and closing of parenthesis.
Undo mechanism
Undo mechanism in text editors: this operation is accomplished by keeping all the text changes in a stack.
Expression Evaluation
Stack is used to evaluate prefix, postfix and infix expressions.
Expression Conversion
An expression can be represented in prefix, postfix or infix notation. Stack can be used to convert one form of expression to another.
String Reversal
Stack is used to reverse a string. We push the characters of string one by one into stack and then pop character from stack.
Function Call
Stack is used to keep information about the active functions or subroutines.
