Applications of Stack
Stack is one of the most useful data structure and is used in problems like Expression Evaluation, Backtracking, Memory Management and algorithms like Breadth First Search (BFS).
We have explored the applications of Stack in depth.
Stack is a data structure used to for data storage(like linked lists). It is an ordered list in which insertion and deletion is performed from one end. The order may be LIFO(Last In First Out) or FILO(First In Last Out). It mainly has 2 primary operations:
 push, which inserts the element in stack and
 pop, which removes the most recently added element from the stack.
Why Stack?
As discussed above Stack is a linear data structure used to store some data. So what is different about it?
Stack is an abstract data type which, unlike an array, can contain elements of different data types.
When we talk about storage, it's not fixed and is dynamic which is quite the opposite for arrays as they cannot be resized.Hence using the abstract data types such as Stack can surely give us an upper hand.
Applications of Stack
 Expression Evaluation
 Backtracking
 Memory Management
Expression Evaluation
There are mainly 3 methods which is used for evalauting the expression.
 Infix
 Prefix
 Postfix
Let us understand about their working by evaluating some simple arithematic expressions.
Infix  Prefix  Postfix 

a+b  +ab  ab+ 
a+b* c  +a* bc  abc*+ 
operator between operands  Operator before operands  operator after operands 
Infix expression is difficult to parse by the computers.Hence we convert it into either Prefix or Postfix notation for the evaluation purposes.
Let us see how the conversion works.

Infix to Postfix

Algorithm
 Create a stack for each character, let's say 'X', for each character in the input stream
 if(X is an operand),
output X
[end of if]  else if(X is a right parenthesis),
pop the output tokens until a left parenthesis is popped(but not output)
[end of else if]  else(when X is a left parenthesis or an operator),
pop the output tokens until one of the lower priority is encountered or when the stack becomes empty
[end of else]
 if(X is an operand),
 Pop and output token until the stack is empty
For better understanding let us trace out an example: A* B(C+D)+E
Example
Input Character  Operation on stack  stack  Postfix expression 

A  Empty  A  
*  Push  *  A 
B  AB  
  Check and Push    AB* 
(  (  AB*  
C  (  AB* C  
+  (+  AB* C  
D  (+  AB* CD  
)  Pop and append till '('    AB* CD+ 
+  Check and Push  +  AB* CD+ 
E  +  AB* CD+E  
End of Input  Pop till empty  Empty  AB* CD+E+ 
Input Infix Expression: A* B(C+D)+E
Equivalent Postfx Expression: AB* CD+E+
Code for infix to postfix using stack stl
#include<iostream>
#include<stack>
#include<algorithm>
#include<string>
using namespace std;
bool IsOperator(char c)
{
if(c=='+'c==''c=='*'c=='/'c=='^')
{
return True;
}
else
{
return False;
}
}
int OpPrecedence(char c) //Function to return precedence of operators
{
if(c == '^')
return 3;
else if(c == '*'  c == '/')
return 2;
else if(c == '+'  c == '')
return 1;
return 0;
}
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s,stack <char> ch)
{
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
if((infix[i] >= 'a' && infix[i] <= 'z')(infix[i] >= 'A' && infix[i] <= 'Z'))
{
postfix+=infix[i]; // If the scanned character is an operand, add it to output
}
else if(infix[i] == '(')// If scanned char is '(' , push it into stack
{
ch.push(infix[i]);
}
else if(infix[i] == ')')
{
while((s.top()!='(') && (!s.empty()))//If scanned char is ')', pop until ')'
{ // is encountered
char t=ch.top();
postfix+=t;
ch.pop();
}
}
if(ch.top()=='(')
{
ch.pop();
}
}
else if(IsOperator(infix[i])) //to check if scanned char is an operator and pop it
{
if(ch.empty())
{
ch.push(infix[i]);
}
else
{
if(precedence(infix[i])>precedence(ch.top()))
{
ch.push(infix[i]);
}
else if((OpPrecedence(infix[i])==OpPrecedence(s.top()))&&(infix[i]=='^'))
{
ch.push(infix[i]);
}
else
{
while((!ch.empty())&&( OpPrecedence(infix[i])<=OpPrecedence(s.top())))
{
postfix+=ch.top();
ch.pop();
}
ch.push(infix[i]);
}
}
}
}
while(!ch.empty()) //pop all the elements
{
postfix+=ch.top();
ch.pop();
}
return postfix;
}
int main()
{
string inf, post;
cout<<"Enter a Infix Expression :"<<endl;
cin>>inf;
stack <char> ch;
cout<<"INFIX EXPRESSION: "<<inf<<endl;
post = InfixToPostfix(ch, inf);
cout<<endl<<"POSTFIX EXPRESSION: "<<post;
return 0;
}
 Infix to Prefix
 Algorithm
 Reverse the infix expression.
 Examine the next element in the input.
 If it is an operand, add it to the output expression.
 If it is ')', top of the stack is popped and added to the expression until '(' is encountered.
 If it is an operator then,
 If the operator has a higher priority than the operator at the top of stack,
then the operator being scanned is pushed back  If the precedence of the symbol being scanned is lower than or equal to the precedence of the symbol at the top of the stack, the stack is popped to the output.
 If the operator has a higher priority than the operator at the top of stack,
 Repeatedly pop from Stack and push each operator on the top of Stack until a left parenthesis is encountered.
 Reverse the obtained prefix expression.
 END.
 Example
Infix Expression: A+B*(C^ D  E)
Reverse Brackets : )ED^C(* B +A
Reverse Expression : (ED^C)* B+A
Input Token  Operation on Stack  Stack  Prefix Expression 

(  Push  (  
E  Add operand to result  (  E 
  Push  (  E 
D  (  ED  
^  Push  (^  ED 
C  (^  EDC  
)  Pop until '('  Empty  EDC^ 
*  Push  *  EDC^ 
B  *  EDC^B  
+  Pop * (higher precedence) and add to result  +  EDC^B* 
A  +  EDC^B* A  
End of Input  Pop till Empty  Empty  EDC^B* A+ 
Reversing the final expression we get :+A* B^CDE
Input Infix Expression: A+B*(C^ D  E)
Equivalent Prefix Expression: +A* B^CDE
 Code for infix to prefix using stack stl
#include <iostream>
#include<stack>
#include<algorithm>
#include<string>
using namespace std;
bool IsOperator(char ch) //to check for a valid operator
{
if(ch == '+'ch == ''ch == '*'ch == '^'ch == '^')
return true;
else
return false;
}
int OpPrecedence(char ch)
{
if (ch == '^')
return 3;
else if (ch == '*'  ch == '/')
return 2;
else if(ch == ''  ch == '+')
return 1;
return 0;
}
string InfixToPrefix(string infix, stack <char> s)
{
string prefix;
int l = infix.size();
reverse(infix.begin(), infix.end()); //reversing prefix expression
for (int i = 0; i < l; i++) {
if (infix[i] == '(') {
infix[i] = ')';
}
else if (infix[i] == ')') {
infix[i] = '(';
}
for (int i = 0; i < l; i++) //if operator is an operand then add it
//to the output
{
if ((infix[i] >= 'a' && infix[i] <= 'z')  (infix[i] >= 'A' && infix[i] <= 'Z'))
{
prefix += infix[i];
}
else if (infix[i] == '(') // If the traversed character is an '(', push
{ // it into stack
s.push(infix[i]);
}
else if (infix[i] == ')') // If the traversed character is ')', pop from
//stack until '(' is encountered
{
while ((s.top() != '(') && (!s.empty()))
{
prefix += s.top();
s.pop();
}
if (s.top() == '(') //remove '(' from stack
{
s.pop();
}
}
else if (IsOperator(infix[i]))
{
if (s.empty())
{
s.push(infix[i]); //push current operator in stack
}
else
{
if (OpPrecedence(infix[i]) > OpPrecedence(s.top()))
{
s.push(infix[i]); //push current operator in stack
}
else if ((OpPrecedence(infix[i]) == OpPrecedence(s.top()))
&& (infix[i] == '^'))
{
while ((OpPrecedence(infix[i]) == OpPrecedence(s.top()))
&& (infix[i] == '^'))
{
prefix += s.top();
s.pop();
}
s.push(infix[i]); //push current operator in stack
}
else if (OpPrecedence(infix[i]) == OpPrecedence(s.top()))
{
s.push(infix[i]);
}
else
{
while ((!s.empty()) && (OpPrecedence(infix[i]) < OpPrecedence(s.top())))
{
prefix += s.top();
s.pop();
}
s.push(infix[i]);
}
}
}
}
while (!s.empty()) //popping the characters from stack
{
prefix += s.top();
s.pop();
}
reverse(prefix.begin(), prefix.end()); //reversing the prefix expression
return prefix;
}
int main()
{
string in, pre;
cout << "Enter a Infix Expression :" << endl;
cin >> in;
stack<char> ch;
cout << "infix expression " << in << endl;
prefix = InfixToPrefix(ch, in);
cout << endl
<< "prefix expression " << prefix;
return 0;
}
Backtracking
So let us first understand what backtracking is:
Backtracking is an improvement to Bruteforce approach.It systematically searches for 1 possible solution from the given possible options. If we are able to find an optimized solution with the selected option then it becomes our final solution else we backtrack and choose a different option and try solving with it. If all the possible options are worked out then we claim that there is no solution to the problem.
Backtracking is also a form of recursion.
Here we will see the functioning of NQueen Problem to comprehend backtracking clearly.
 NQueen Problem
The N Queen is the problem of placing N chess queens on an NÃ—N chessboard so that no two queens attack each other.
Let us take an example for 4Queen Problem.
 Algorithm
 Start in the leftmost column
 If all queens are placed return true
 Try all rows in the current column. Do following for every tried row.
 If the queen can be placed safely in this row then mark this [row,column] as part of the solution and recursively check if placing queen here leads to a solution.
 If placing queen in [row, column] leads to a solution then return true.
 If placing queen doesn't lead to a solution then mark this [row, column] (Backtrack) and go to step (3.1) to try other rows.
 If all rows have been tried and nothing worked, return false to trigger backtracking.
 Code
#include<iostream>
#define N 4
using namespace std;
void printBoard(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
}
bool isValid(int board[N][N], int r, int c)
{
for (int i = 0; i < col; i++) //check whether there is queen in the left or not
if (board[r][i])
return false;
for (int i=r, j=c; i>=0 && j>=0; i, j)
if (board[i][j]) //check whether there is queen in the left upper diagonal return false;
for (int i=row, j=col; j>=0 && i<N; i++, j)
if (board[i][j]) //check whether there is queen in the left lower diagonal
return false;
return true;
}
bool solnNQueen(int board[N][N], int c)
{
if (c >= N) //when N queens are placed successfully
return true;
for (int i = 0; i < N; i++) //for each row, check if placing of queen is possible
{
if (isValid(board, i, c) )
{
board[i][col] = 1; //if validate, place the queen at place (i, column)
if ( solveNQueen(board, c + 1)) //Go for the other columns recursively
return true;
board[i][c] = 0; //When no place is vacant remove that queen
}
}
return false; /* If queen can not be place in any row in this column
then return false */
}
bool validSolution()
{
int board[N][N];
for(int i = 0; i<N; i++)
for(int j = 0; j<N; j++)
board[i][j] = 0; //set all elements to 0
if ( solnNQueen(board, 0) == false ) //starting from 0th column
{
cout << "Solution does not exist";
return false;
}
printBoard(board);
return true;
}
int main()
{
validSolution();
}
Memory Management
Stacks in computing architectures are regions of memory where data is added or removed in a lastinfirstout (LIFO) manner.The operating system allocates memory segment for stack which includes arguments,the return value and local variable of a function. Stack variable will exist only until the function created them is running and after that they are all popped out of the stack and data is lost forever. Reading and writing from stack variable is very fast as the CPU organizes the memory very efficiently.Allocation and deallocation is an automatic process.
Complexity
Since the expression evaluation works on push() and pull() functions of stack
Complexity for push function: O(n)
Complexity for pull function: O(1)
which gives an overall complexity of O(n)
 InfixPostfix: O(n)
 InfixPrefix: O(n)
 NQueen Problem: O(n!)
Applications
Some standard applications of stack are:

Parenthesis balancing
Opening parenthesis are pushed and when a closing parenthesis is encountered, pop the stack. If all the symbols are popped and no character is left unscanned, we
can say that parenthesis are balanced. 
Used in Recursion
Stack is used to store and restore recursive function along with it's argument(s).
The data is stored from top to bottom in the stack. 
Undo Mechanism
This mechanism is also performed with the help of stack.So stack stores the
history of user mechanisms, and if a new action is performed it is added to the
top of the stack. So an undo mechanism does nothing but pops the item from
the stack. 
Reversing of a String
Reading a string means pushing the items into the stack and reversing is just the
pop operation. The last item will be on the top(LIFO) hence after popping them one
by one we get a string in reverse order. 
Managing Function calls and Return mechanism
Everytime a function is called it is pushed back into the stack along with the
return address.When function is returned, it is first popped out of the stack
and then the control is transferred to the return address(from where the function
was called). 
Finding path in roadmap from one point to another
Generally it is an application of backtracking.The key to backtracking being:
each choice or decision is recorded in the stack and when we run out of decisions,
the stack is popped and continue try for different choices for the previous
decisions (here to find a minimum distance path between two points).
Parenthesis balancing
Parenthesis balancing is one of the major concept used in syntax highlighting editors. So let's take a quick look at the algorithm of how it is implemented
using stack.
 Algorithm
 Scan the expression from left to right
 If the character is an open bracket like '{','(','[', then push it back to
stack.  If the scanned character is a closing bracket like '}',')',']' ,then pop from the stack and check if the popped character is same as the starting bracket of the string.
If it is then the paranthesis is balanced otherwise iunbalanced
 Code using stack stl
#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool IsBalanced(string s)
{
stack <char> stk;
string open="[{(";
char temp;
for(int i=0;i<s.length();i++)
{
if(open.find(s[i])>=0) //find returns the index of first occurance of the //character in the given string
{
stk.push(s[i]);
}
if(stk.empty()) //should have the opening parenthesis
return False;
switch(s[i])
{
case ')':
{
temp=stk.top();
stk.pop();
if(temp!='(')
return False;
break;
}
case '}':
{
temp=stk.top();
stk.pop();
if(temp!='{')
return False;
break;
}
case ']':
{
temp=stk.top();
stk.pop();
if(temp!='[')
return False;
break;
}
default: return False;
}//switch
}//for
return(stk.empty()); //return true if stack becomes empty after going through all //iterations
}//fun
int main()
{
string str;
cout<<"enter the string to be checeked"<<endl;
cin>>str;
if(IsBalanced(str)
cout<<"string "<<str<<" is balanced"<<endl;
else
cout<<"string "<<str<<" is not balanced"<<endl;
}