The stack and its

application.
Chapter two 3 hrs

@suresh Raj Sharma 1

Define Define Stack Data Structure.

Explain
We focus on
Explain stack as an ADT.

following Write
Write an algorithms for Stack
Operations.

question in
this unit List out List out the applications of Stack.

Evaluate Infix, Postfix and Prefix

Evaluate expressions.

Implement an algorithms to convert

Implement infix expression to postfix and prefix
expressions.

@suresh Raj Sharma 2

2.1 The Stack Introduction

2.2 Stack as an ADT

2.3 POP and PUSH Operations

Chapter 2.4 Stack Applications

contents 2.5 Evaluation of Infix

2.6 Postfix,

2.7 and Prefix Expressions

2.8 Conversion of Expression.

@suresh Raj Sharma 3
A Stack is a linear data structure that follows
the LIFO (Last-In-First-Out) principle. Stack
has one end, whereas the Queue has two
ends (front and rear). It contains only one
pointer top pointer pointing to the topmost
2.1 The element of the stack. Whenever an element is
Stack Introduction added in the stack, it is added on the top of
the stack, and the element can be deleted
only from the stack. In other words, a stack
can be defined as a container in which
insertion and deletion can be done from the
one end known as the top of the stack.

@suresh Raj Sharma 4

Some key points related to stack

• It is called as stack because it behaves like a real-world stack, piles of

books, etc.
• A Stack is an abstract data type with a pre-defined capacity, which
means that it can store the elements of a limited size.
• It is a data structure that follows some order to insert and delete the
elements, and that order can be LIFO or FILO.
• A real-world stack allows operations at one end only. For example, we
can place or remove a card or plate from the top of the stack only.

@suresh Raj Sharma 5

• Likewise, Stack ADT
allows all data
operations at one end
only. At any given time,
we can only access the
top element of a stack.

@suresh Raj Sharma 6

• A stack can be implemented by means of Array,
Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense
of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a
fixed size stack implementation.

@suresh Raj Sharma 7

A stack is an Abstract Data Type (ADT),
commonly used in most programming
languages. It is named stack as it behaves like
a real-world stack, for example – a deck of
cards or a pile of plates, etc.
2.2 Stack as
A real-world stack allows operations at one
an ADT end only. For example, we can place or
remove a card or plate from the top of the
stack only. Likewise, Stack ADT allows all data
operations at one end only. At any given time,
we can only access the top element of a stack.

@suresh Raj Sharma 8

• A stack of elements of type T is a finite sequence of
elements of T together with the operations
• CreateEmptyStack(S): Create or make stack S be an empty stack
• Push(S, x): Insert x at one end of the stack, called its top
• Top(S): If stack S is not empty; then retrieve the element at its top
• Pop(S): If stack S is not empty; then delete the element at its top
• IsFull(S): Determine if S is full or not. Return true if S is full stack;
return false otherwise
• IsEmpty(S): Determine if S is empty or not. Return true if S is an empty
stack; return false otherwise.

@suresh Raj Sharma 9

• Primitive operations of stack
2.3 POP and Push()
PUSH POP()
Operations The operation is occurs in a same postion
which is known as top of stack

@suresh Raj Sharma 10

Push Operation
The following operations can be performed on a
stack:
1. PUSH operation: The push operation is used
to add (or push or insert) elements in a Stack.
ü When we add an item to a stack, we say that
we push it onto the stack
ü The last item put into the stack is at the top

@suresh Raj Sharma 11

Push operation

@suresh Raj Sharma 12

PUSH operation
• Before inserting an element in a stack, we check whether the stack is
full.
• If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
• When we initialize a stack, we set the value of top as -1 to check that
the stack is empty.
• When the new element is pushed in a stack, first, the value of the top
gets incremented, i.e., top=top+1, and the element will be placed at
the new position of the top.
• The elements will be inserted until we reach the max size of the
stack.
@suresh Raj Sharma 13
@suresh Raj Sharma 14
Push Operations

@suresh Raj Sharma 15

POP operation: The pop operation is
used to remove or delete the top
element from the stack.

Pop
operation we remove an item, we say that
we pop item from the stack.

s
When an item popped, it is always
the top item which is removed.

@suresh Raj Sharma 16

The steps involved in the POP operation is
given below:
• Before deleting the element from the stack, we check whether the
stack is empty.
• If we try to delete the element from the empty stack, then
the underflow condition occurs.
• If the stack is not empty, we first access the element which is pointed
by the top
• Once the pop operation is performed, the top is decremented by 1,
i.e., top=top-1.

@suresh Raj Sharma 17

@suresh Raj Sharma 18
Pop operations

@suresh Raj Sharma 19

Pop operation

@suresh Raj Sharma 20

The PUSH and the POP operations are the basic or
primitive operations on a stack. Some others
operations are:
• CreateEmptyStack operation: This operation is
used to create an empty stack.
• IsFull operation: The isfull operation is used to
check whether the stack is full or not ( i.e. stack
overflow)
• IsEmpty operation: The isempty operation is used
to check whether the stack is empty or not. (i. e.
stack underflow)
• Top operations: This operation returns the current
item at the top of the stack, it doesn’t remove it
@suresh Raj Sharma 21
Program of Stack using Array.
/* Program of stack using array*/ {
#include<stdio.h> case 1 :
#define MAX 5 push();
break;
int top = -1; case 2:
int stack_arr[MAX]; pop();
break;
main() case 3:
{ display();
int choice; break;
while(1) case 4:
{ exit(1);
printf("1.Push\n"); default:
printf("2.Pop\n"); printf("Wrong choice\n");
printf("3.Display\n"); }/*End of switch*/
printf("4.Quit\n"); }/*End of while*/
printf("Enter your choice : "); }/*End of main()*/
scanf("%d",&choice);
switch(choice) @suresh Raj Sharma 22
push()
{ pop()
int pushed_item; {
if(top == (MAX-1)) if(top == -1)
printf("Stack Overflow\n"); printf("Stack Underflow\n");
else else
{ {
printf("Enter the item to be pushed printf("Popped element is
in stack : "); : %d\n",stack_arr[top]);
scanf("%d",&pushed_item); top=top-1;
top=top+1;
stack_arr[top] = pushed_item; }
} return 0;
return 0; }/*End of pop()*/
}/*End of push()*/

@suresh Raj Sharma 23

display()
{
int i;
if(top == -1)
printf("Stack is empty\n");
else
{
printf("Stack elements :\n");
for(i = top; i >=0; i--)
printf("%d\n", stack_arr[i] );
}
return 0;
}/*End of display()*/

@suresh Raj Sharma 24

• Balancing of symbols: Stack is used for
balancing a symbol. For example, we have
the following program:each program has an
opening and closing braces; when the
opening braces come, we push the braces in
2.4 Stack a stack, and when the closing braces appear,
we pop the opening braces from the stack.
Applications Therefore, the net value comes out to be
zero. If any symbol is left in the stack, it
means that some syntax occurs in a
program.

@suresh Raj Sharma 25

• String reversal: Stack is also used for reversing a string. For example, we want to reverse a
"javaTpoint" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null character.
After pushing all the characters, we start taking out the character one by one until we reach the
bottom of the stack.
• UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an
editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So,
there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which
one stack shows UNDO state, and the other shows REDO state.
If we want to perform UNDO operation, and want to achieve 'ab' state, then we implement pop
operation.
• Recursion: The recursion means that the function is calling itself again. To maintain the previous
states, the compiler creates a system stack in which all the previous records of the function are
maintained.
• DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data
structure.
• Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a
particular path, and we realize that we come on the wrong way. In order to come at the beginning of
the path to create a new path, we have to use the stack data structure.

@suresh Raj Sharma 26

• DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the
stack data structure.
• Backtracking: Suppose we have to create a path to solve a maze problem. If we are
moving in a particular path, and we realize that we come on the wrong way. In order to
come at the beginning of the path to create a new path, we have to use the stack data
structure.

• Expression conversion: Stack can also be used for expression conversion. This is one of
the most important applications of stack. The list of the expression conversion is given
below:Infix to prefix
• Infix to postfix
• Prefix to infix
• Prefix to postfix
• Postfix to infix
• Memory management: The stack manages the memory. The memory is assigned in the
contiguous memory blocks. The memory is known as stack memory as all the variables
are assigned in a function call stack memory. The memory size assigned to the program is
known to the compiler. When the function is created, all its variables are assigned in the
stack memory. When the function completed its execution, all the variables assigned in
the stack are released. @suresh Raj Sharma 27
• An arithmetic expression can be written in three different
but equivalent notations, i.e., without changing the
essence or output of an expression. These notations are −
• Infix Notation
• Prefix (Polish) Notation
• Postfix (Reverse-Polish) Notation
2.5 • These notations are named as how they use operator in
Evaluation of expression. We shall learn the same here in this chapter.
• Infix Notation
Infix • We write expression in infix notation, e.g. a - b + c, where
operators are used in-between operands. It is easy for us
humans to read, write, and speak in infix notation but the
same does not go well with computing devices. An
algorithm to process infix notation could be difficult and
costly in terms of time and space consumption.
@suresh Raj Sharma 28
Types of notation
Infix Notation
In this infix notation the operator in written in between the operand like a+b.
Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is written
ahead of operands. For example, +ab. This is equivalent to its infix
notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation
style, the operator is postfixed to the operands i.e., the operator is written
after the operands. For example, ab+. This is equivalent to its infix
notation a + b.
@suresh Raj Sharma 29
The following table briefly tries to show the
difference in all three notations −

@suresh Raj Sharma 30

Precedence and associativity determines the order of evaluation of an
expression. Following is an operator precedence and associativity table
(highest to lowest) −

@suresh Raj Sharma 31

Algorithm to evaluate the postfix expression
• Scan the expression from left to right until we
encounter any operator.
• Perform the operation
• Replace the expression with its computed value.
• Repeat the steps from 1 to 3 until no more operators
exist.

@suresh Raj Sharma 32

example
Infix expression: 2 + 3 * 4
We will start scanning from the left most of the expression. The
multiplication operator is an operator that appears first while
scanning from left to right. Now, the expression would be:
Expression = 2 + 34*
= 2 + 12
Again, we will scan from left to right, and the expression would be:
Expression = 2 12 +
= 14
@suresh Raj Sharma 33
Evaluation of postfix expression using stack.

• Scan the expression from left to right.

• If we encounter any operand in the expression, then we push the
operand in the stack.
• When we encounter any operator in the expression, then we pop the
corresponding operands from the stack.
• When we finish with the scanning of the expression, the final value
remains in the stack.

@suresh Raj Sharma 34

Let's understand the evaluation of postfix
expression using stack.
Example 1: Postfix expression: 2 3 4 * +

@suresh Raj Sharma 35

Conversion from infix to postfix
• Print the operand as they arrive.
• If the stack is empty or contains a left parenthesis on top, push the
incoming operator on to the stack.
• If the incoming symbol is '(', push it on to the stack.
• If the incoming symbol is ')', pop the stack and print the operators
until the left parenthesis is found.
• If the incoming symbol has higher precedence than the top of the
stack, push it on the stack.

@suresh Raj Sharma 36

• If the incoming symbol has lower precedence than the top of the
stack, pop and print the top of the stack. Then test the incoming
operator against the new top of the stack.
• If the incoming operator has the same precedence with the top of
the stack then use the associativity rules. If the associativity is from
left to right then pop and print the top of the stack then push the
incoming operator. If the associativity is from right to left then push
the incoming operator.
• At the end of the expression, pop and print all the operators of the
stack.

@suresh Raj Sharma 37

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

@suresh Raj Sharma 38

@suresh Raj Sharma 39
@suresh Raj Sharma 40
Infix expression Operator on stack Postfix expression
A A+b-c*(d+e-f/g) A
+ + A
B + Ab
- - Ab+
C - Ab+c
* -* AB+C
( -*( AB+C
D -*( Ab+cd
+ -*(+ ab_+cd
E -*(+ Ab+cde
- -*(- Ab+cde+
F -*(- Ab+cde+f
/ -*(-/ Ab+cde+f
G -*(-/ Ab+cde+fg
) _* Ab+cde+fg/-
Null Null Ab+cde+fg/-*-
@suresh Raj Sharma 41
symbols value op2 op1 result vstack
a 1 … … …. 1
b 4 …. … … 14
+ ….. 4 1 1+4=5 5
C 2 …….. ….. ….. 52
D 8 ….. ….. …. 528
E 3 …. …… …. 5283
+ …. 3 8 8+3=11 5 2 11
F 9 …. …. …. 5 2 11 9
G 3 ….. ….. ….. 5 2 11 9 3
/ …. 3 9 9/3=3 5 2 11 3
- … 3 11 11-3=8 528
* …. 8 2 2*8=16 5 16
- … 16 5 5-16=-11 -11

@suresh Raj Sharma 42

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

@suresh Raj Sharma 43

Evaluation of Prefix Expression using Stack
• Step 1: Initialize a pointer 'S' pointing to the end of the expression.
• Step 2: If the symbol pointed by 'S' is an operand then push it into the
stack.
• Step 3: If the symbol pointed by 'S' is an operator then pop two
operands from the stack. Perform the operation on these two
operands and stores the result into the stack.
• Step 4: Decrement the pointer 'S' by 1 and move to step 2 as long as
the symbols left in the expression.
• Step 5: The final result is stored at the top of the stack and return it.
• Step 6: End

@suresh Raj Sharma 44

Let's understand the evaluation of prefix expression through an
example.
Expression: +, -, *, 2, 2, /, 16, 8, 5
First, we will reverse the expression given above.
Expression: 5, 8, 16, /, 2, 2, *, -, +
We will use the stack data structure to evaluate the prefix expression.

@suresh Raj Sharma 45

@suresh Raj Sharma 46
Convert from infix to prefix
Conversion of Infix to Prefix using Stack
K + L - M * N + (O^P) * W/U/V * T + Q
If we are converting the expression from infix to prefix, we need first to
reverse the expression.
The Reverse expression would be:
Q + T * V/U/W * ) P^O(+ N*M - L + K
To obtain the prefix expression, we have created a table that consists of
three columns, i.e., input expression, stack, and prefix expression. When
we encounter any symbol, we simply add it into the prefix expression. If we
encounter the operator, we will push it into the stack.
@suresh Raj Sharma 47
@suresh Raj Sharma 48
@suresh Raj Sharma 49
The above expression, i.e., QTVUwPO^*//*NM*LK+-++, is
not a final expression. We need to reverse this expression to
obtain the prefix expression.
As
++-+kL*MN*//*^OPwUVTQ
Where infix is as
K + L - M * N + (O^P) * W/U/V * T + Q

@suresh Raj Sharma 50

((a-(b+c))*d)$(e+f)
(a+b*c/d)*(e-f/g)

@suresh Raj Sharma 51

Algorithm to convert infix to prefix is
• First, reverse the infix expression given in the
problem.
• Scan the expression from left to right.
• Whenever the operands arrive, print them.
• If the operator arrives and the stack is found to be
empty, then simply push the operator into the stack.
• If the incoming operator has higher precedence than
the TOP of the stack, push the incoming operator into
the stack. @suresh Raj Sharma 52
• If the incoming operator has the same precedence with
a TOP of the stack, push the incoming operator into the
stack.
• If the incoming operator has lower precedence than the
TOP of the stack, pop, and print the top of the stack. Test
the incoming operator against the top of the stack again
and pop the operator from the stack till it finds the
operator of a lower precedence or same precedence.

@suresh Raj Sharma 53

• If the incoming operator has the same precedence with the top of the
stack and the incoming operator is ^, then pop the top of the stack till
the condition is true. If the condition is not true, push the ^ operator.
• When we reach the end of the expression, pop, and print all the
operators from the top of the stack.
• If the operator is ')', then push it into the stack.
• If the operator is '(', then pop all the operators from the stack till it
finds ) opening bracket in the stack.
• If the top of the stack is ')', push the operator on the stack.
• At the end, reverse the output.

@suresh Raj Sharma 54

Conversion of Prefix to Postfix Expression
Rules for prefix to postfix expression using stack data structure:
• Scan the prefix expression from right to left, i.e., reverse.
• If the incoming symbol is an operand then push it into the stack.
• If the incoming symbol is an operator then pop two operands from
the stack. Once the operands are popped out from the stack, we add
the incoming symbol after the operands. When the operator is added
after the operands, then the expression is pushed back into the stack.
• Once the whole expression is scanned, pop and print the postfix
expression from the stack.

@suresh Raj Sharma 55

If the expression is: * - A / B C - / A K L

@suresh Raj Sharma 56

@suresh Raj Sharma 57
The Any
end query?

@suresh Raj Sharma 58