What is Stack?

Stack is a linear data structure that follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies
that the element that is inserted last, comes out first and FILO implies that the element that is
inserted first, comes out last.

There are many real-life examples of a stack. Consider an example of plates stacked over one
another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate
which has been placed at the bottommost position remains in the stack for the longest period of
time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.

Stack mainly supports push(insert an element to the top of stack), pop(remove an element from the
top of stack) and peek(return top element without removing it) operations.

push(): It stacks up a new item. A stack overflow circumstance is when the stack is completely full.
Time Complexity is O(1)

Algorithm for push():

1. begin
2. if stack is full
3. return
4. endif
5. else
6. increment top
7. stack[top] assign value
8. end else
9. end procedure
 pop() : It takes something out of the stack. In the opposite sequence from which they were pushed, the
things are popped. The condition is referred to as an underflow if the stack is empty. Time Complexity is
O(1)

Algorithm for pop():

1. begin
2. if stack is empty
3. return
4. endif
5. else
6. store value of stack[top]
7. decrement top
8. return value
9. end else
10. end procedure

// C Program for stack operations, push(), pop() and peek()

#include <stdio.h>
#define N 5
int top=-1;
int stack[5];

void push(int item)

{
if(top ==N-1)
{
printf("\nthe stack is overflow");
return;
}
else
{
top++;
stack[top]=item;
}
}
int pop()
{ int item ;
if(top==-1)
{
printf("\nunderflow");
 }
else
{
item=stack[top];
top--;
return item;

}
}

int peek()
{ int item ;
if(top==-1)
{
printf("\nunderflow");

}
else
{
item=stack[top];
return item;

}
}
void display()
{
for (int i = top;i>=0;i--)
printf("\n%d ",stack[i]);

}
void main()
{
push(10);
push(20);
printf("\nPeek = %d",peek());
display();
pop();
printf("\nPeek = %d",peek());
pop();
pop();
display();
}
Stack Applications:
1. Infix to Postfix Conversion
2. Postfix Expression Evaluation
 3. Recursion
4. DFS(Depth First Search) – to be covered in graph unit
5. Undo Operation (real life example)

1. Infix to Postfix Conversion:

Infix expression: The expression of the form “a operator b” (a + b) i.e., when an operator is
in-between every pair of operands.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., When every pair of
operands is followed by an operator.
Examples:
Input: A + B * C + D
Output: ABC*+D+
Input: ((A + B) – C * (D / E)) + F
Output: AB+CDE/*-F+

Below are the steps to implement the above idea:

1. Scan the infix expression from left to right.
2. If the scanned character is an operand, put it in the postfix expression.
3. Otherwise, do the following
 If the precedence and associativity of the scanned operator are greater than the
precedence and associativity of the operator in the stack [or the stack is empty or the
stack contains a ‘(‘ ], then push it in the stack. [‘^‘ operator is right associative and
other operators like ‘+‘,’–‘,’*‘ and ‘/‘ are left-associative].
 Check especially for a condition when the operator at the top of the stack
and the scanned operator both are ‘^‘. In this condition, the precedence of
the scanned operator is higher due to its right associativity. So it will be
pushed into the operator stack.
 In all the other cases when the top of the operator stack is the same as the
scanned operator, then pop the operator from the stack because of left
associativity due to which the scanned operator has less precedence.
 Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator.
 After doing that Push the scanned operator to the stack. (If you encounter
parenthesis while popping then stop there and push the scanned operator in
the stack.)
4. If the scanned character is a ‘(‘, push it to the stack.
5. If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is encountered, and
discard both the parenthesis.
6. Repeat steps 2-5 until the infix expression is scanned.
7. Once the scanning is over, Pop the stack and add the operators in the postfix expression
until it is not empty.
8. Finally, print the postfix expression.
Illustration:
Follow the below illustration for a better understanding
Consider the infix expression exp = “a+b*c+d”
and the infix expression is scanned using the iterator i, which is initialized as i = 0.
1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix expression.
Therefore, postfix = “a”.

Add ‘a’ in the postfix

2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the stack. postfix =
“a” and stack = {+}.

Push ‘+’ in the stack

3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix
expression. postfix = “ab” and stack = {+}.
 Add ‘b’ in the postfix

4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the stack. postfix =
“ab” and stack = {+, *}.

Push ‘*’ in the stack

5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix
expression. postfix = “abc” and stack = {+, *}.
 Add ‘c’ in the postfix

6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of the stack has
higher precedence. So pop until the stack becomes empty or the top element has less
precedence. ‘*’ is popped and added in postfix. So postfix = “abc*” and stack = {+}.

Pop ‘*’ and add in postfix

Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix = “abc*+”.
 Pop ‘+’ and add it in postfix

Now stack is empty. So push ‘+’ in the stack. stack = {+}.

Push ‘+’ in the stack

7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix
expression. postfix = “abc*+d”.
 Add ‘d’ in the postfix

Final Step: Now no element is left. So empty the stack and add it in the postfix
expression. postfix = “abc*+d+”.

Pop ‘+’ and add it in postfix

Example: Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Input Expression Stack Postfix Expression

K K

+ +

L + KL

- - K L+

M - K L+ M

* -* K L+ M

N -* KL+MN

+ + K L + M N*
K L + M N* -

( +( K L + M N *-

O +( KL+MN*-O

^ +(^ K L + M N* - O

P +(^ K L + M N* - O P

) + K L + M N* - O P ^

* +* K L + M N* - O P ^

W +* K L + M N* - O P ^ W

/ +/ K L + M N* - O P ^ W *

U +/ K L + M N* - O P ^W*U

/ +/ K L + M N* - O P ^W*U/

V +/ KL + MN*-OP^W*U/V The
final
* +* KL+MN*-OP^W*U/V/

T +* KL+MN*-OP^W*U/V/T

+ + KL+MN*-OP^W*U/V/T*
KL+MN*-OP^W*U/V/T*+

Q + KL+MN*-OP^W*U/V/T*Q

KL+MN*-OP^W*U/V/T*+Q+
postfix expression of infix expression (K + L - M*N + (O^P) * W/U/V * T + Q) is KL+MN*-
OP^W*U/V/T*+Q+.

Other applications of stack not covered in syllabus:

Infix to Prefix Conversion:
1. Reverse the expression
2. Convert ‘(‘ to ‘)’ and ‘)’ to ‘(‘
3. Pop only higher precedence operator from the top of the stack unlike Infix to Postfix Conversion
where heavy operator (higher precedence operator + left associative operator) is popped out.
For example: from Infix to Postfix Conversion of a+b-c(ab+c-), on occurring of ‘-‘, ‘+’ operator
will be popped out from the stack.
While from Infix to Prefix Conversion of a+b-c(-+abc) on occurring of ‘-‘, nothing will be popped
out but ‘+’ operator will be pushed to the stack.
4. in the last again reverse the expression.
Example:
Convert a + b - c to prefix expression:
Reverse a + b - c = c - b + a

Scanned Symbols Operator Stack Output Expression Remark

c - c
- - c
b - cb
+ -+ Equal precedence
operator will be
pushed in stack
a -+ cba
cba+- Popped out all
operator

Reverse the expression:

Ans: final prefix expression: - + c b a

2. Evaluation Rules of Postfix Expression

The following are the rules for evaluation of a postfix expression:

1. While reading the expression from left to right, push the element in the stack if it
is an operand.
 2. Pop the two operands from the stack, if the element is an operator and then
evaluate it.
3. Push back the result of the evaluation. Repeat it till the end of the expression.

Algorithm for Evaluation of Postfix Expression

1. Add ) to postfix expression.
2. Read postfix expression Left to Right until ) encountered
3. If operand is encountered, push it onto Stack
[End If]
4. If operator is encountered, Pop two elements
1. A -> Top element
2. B-> Next to Top element
3. Evaluate B operator A
4. Push B operator A onto Stack
5. Set result = pop
6. END

Example for Evaluation of Postfix Expression

Let's see an example to better understand the algorithm:

Expression: 456*+
Algorithm for Evaluation of Prefix Expression
1. Read prefix expression Right to Left
2. If operand is encountered, push it onto Stack
[End If]
3. If operator is encountered, Pop two elements
1. A -> Top element
2. B-> Next to Top element
3. Evaluate A operator B
4. Push A operator B onto Stack
4. Set result = pop
5. END
Q. What is the outcome of the given prefix expression: +, -, *, 3, 2, /, 8, 4, 1.

Asn: 5

Detailed Solution:

3. Recusrsion:

Recursion In this section we are going to discuss recursion which is an implicit application of
the STACK ADT.

A recursive function is defined as a function that calls itself to solve a smaller version of its task
until a final call is made which does not require a call to itself. Since a recursive function
repeatedly calls itself, it makes use of the system stack to temporarily store the return address and
local variables of the calling function.

Every recursive solution has two major cases. They are

 Base case, in which the problem is simple enough to be solved directly without making any
further calls to the same function.
 Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second
the function calls itself but with sub-parts of the problem obtained in the first step. Third, the
result is obtained by combining the solutions of simpler sub-parts.

Therefore, recursion is defining large and complex problems in terms of smaller and more easily
solvable problems. In recursive functions, a complex problem is defined in terms of simpler
problems and the simplest problem is given explicitly.

To understand recursive functions, let us take an example of calculating factorial of a number.

To calculate n!, we multiply the number with factorial of the number that is 1 less than that
number. In other words, n! = n X (n–1)!

Let us say we need to find the value of 5! 5! = 5 X 4 X 3 X 2 X 1 = 120

This can be written as 5! = 5 X 4!, where 4!= 4 X 3!

Therefore, 5! = 5 X 4 X 3!

Similarly, we can also write, 5! = 5 X 4 X 3 X 2!

Expanding further 5! = 5 X 4 X 3 X 2 X 1!

We know,1! = 1

Now if you look at the problem carefully, you can see that we can write a recursive function to
calculate the

Now if you look at the problem carefully, you can see that we can write a recursive
function to calculate the factorial of a number. Every recursive function must have a base
case and a recursive case. For the factorial function
 Base case is when n = 1, because if n = 1, the result will be 1 as 1! = 1.
 Recursive case of the factorial function will call itself but with a smaller value of n, this
case can be given as factorial(n) = n × factorial (n–1)
Look at the following program which calculates the factorial of a number recursively.
 Programming Example
Write a program to calculate the factorial of a given number.
#include <stdio.h>
int Fact(int); // FUNCTION DECLARATION

int main()
{
int num, val;
printf("\n Enter the number: ");
scanf("%d", &num);
val = Fact(num);
printf("\n Factorial of %d = %d", num, val);
return 0; }
int Fact(int n)
{
if(n==1) return 1;
else return (n * Fact(n–1));
}
Output Enter the number: 5
Factorial of 5 = 120

Different types of the recursion:

1. Direct Recursion
2. Indirect Recursion
3. Tail Recursion
4. No Tail/ Head Recursion

3. 1. Direct Recursion

When a function calls itself within the same function repeatedly, it is called the direct recursion.

Structure of the direct recursion

1. fun()
2. {
3. // write some code
4. fun();
5. // some code
6. }

In the above structure of the direct recursion, the outer fun() function recursively calls the inner
fun() function, and this type of recursion is called the direct recursion.

//Direct Recursion
#include <stdio.h>
void print(int n)
{
if(n < 1) //Base Condition
return;
else
print(n-1); //Direct recursion involves a function calling itself directly
printf("%d ",n);
}

int main()
{
print(5);
return 0;
}

O/P: 1 2 3 4 5

3.2 Indirect Recursion

When a function is mutually called by another function in a circular manner, the function is
called an indirect recursion function.

Structure of the indirect recursion

1. fun1()
2. {
3. // write some code
4. fun2()
5. }
6. fun2()
7. {
8. // write some code
9. fun3()
10. // write some code
11. }
12. fun3()
13. {
14. // write some code
15. fun1()
16. }

In this structure, there are four functions, fun1(), fun2(), fun3() and fun4(). When the fun1()
function is executed, it calls the fun2() for its execution. And then, the fun2() function starts its
execution calls the fun3() function. In this way, each function leads to another function to makes
their execution circularly. And this type of approach is called indirect recursion.

Let's write a program to demonstrate the indirect recursion in C programming language.

//InDirect Recursion
#include <stdio.h>
void print1(int n); //function declaration
void print2(int n); //function declaration
void print1(int n)
{
if(n < 1) //Base Condition
return;
else
print2(n-1); //print1 calls print2
printf("%d ",n);
}
void print2(int n)
{
if(n < 1) //Base Condition
return;
else
print1(n-1); //print2 calls print1
printf("%d ",n);
}

int main()
{
print1(5);
return 0;
 }
O/P: 1 2 3 4 5

3.3 Tail Recursion

A recursive function is called the tail-recursive if the function makes recursive calling itself, and
that recursive call is the last statement executes by the function. After that, there is no function or
statement is left to call the recursive function.

Let's write a program to demonstrate the tail recursion in C programming language.

Program

1. #include <stdio.h>
2. // function definition
3. void fun1( int num)
4. {
5. // if block check the condition
6. if (num == 0)
7. return;
8. else
9. printf ("\n Number is: %d", num); // print the number
10. return fun1 (num - 1); // recursive call at the end in the fun() function
11. }
12. int main ()
13. {
14. fun1(7); // pass 7 as integer argument
15. return 0;
16. }

Output

Number is: 7
Number is: 6
Number is: 5
Number is: 4
Number is: 3
Number is: 2
Number is: 1
 3.4 Non-Tail / Head Recursion

A function is called the non-tail or head recursive if a function makes a recursive call itself, the
recursive call will be the first statement in the function. It means there should be no statement or
operation is called before the recursive calls. Furthermore, the head recursive does not perform
any operation at the time of recursive calling. Instead, all operations are done at the return time.

Let's write a program to demonstrate the Head/Non-Tail recursion in C programming language.

Program

1. #include <stdio.h>
2. void head_fun (int num)
3. {
4. if ( num > 0 )
5. {
6. // Here the head_fun() is the first statement to be called
7. head_fun (num -1);
8. printf (" %d", num);
9. }
10. }
11. int main ()
12. {
13. int a = 5;
14. printf (" Use of Non-Tail/Head Recursive function \n");
15. head_fun (a); // function calling
16. return 0;
17. }

Output

Use of Non-Tail/Head Recursive function

12345

Data Structure Multiple Stack

A single stack is sometimes not sufficient to store a large amount of data. To overcome this
problem, we can use multiple stack. For this, we have used a single array having more than one
stack. The array is divided for multiple stacks.
Suppose there is an array STACK[n] divided into two stack STACK A and STACK B, where n
= 10.
 STACK A expands from the left to the right, i.e., from 0th element.
 STACK B expands from the right to the left, i.e., from 10th element.
 The combined size of both STACK A and STACK B never exceeds 10.

Multi STACK Program in C

The following program demonstrates Multiple Stack -
#include <stdio.h>
#include <malloc.h>
#define MAX 10
int stack[MAX], topA = -1, topB = MAX;
void push_stackA(int val)
{
if(topA == topB-1)
printf("\n STACK OVERFLOW");
else
{
topA+=1;
stack[topA] = val;
}
}
int pop_stackA()
{
int val;
if(topA == -1)
{
printf("\n STACK UNDERFLOW");
}
else
{
val = stack[topA];
topA--;
}
return val;
}
void display_stackA()
{
int i;
if(topA == -1)
printf("\n Empty STACK A");
else
{
for(i = topA;i >= 0;i--)
printf("\t %d",stack[i]);
}
}
void push_stackB(int val)
{
if(topB-1 == topA)
printf("\n STACK OVERFLOW");
else
{
topB-=1;
stack[topB] = val;
}
}
int pop_stackB()
{
int val;
if(topB == MAX)
{
printf("\n STACK UNDERFLOW");
}
else
{
val = stack[topB];
topB++;
}
}
void display_stackB()
{
int i;
if(topB == MAX)
printf("\n Empty STACK B");
 else
{
for(i = topB; i < MAX;i++)
printf("\t %d",stack[i]);
}
}