Data Structure and Algorithm

Unit-2: Stack

----------------------------------------------------------------------------------------------------

Syllabus:

 Introduction of Stack
 Stack as an ADT
 Stack Operations
 Stack Applications
 Stack implementation as Array and Linked List
 Conversion from infix to postfix/prefix expression
 Evaluation of postfix/ prefix expressions

----------------------------------------------------------------------------------------------------

Introduction:
A Stack is an Abstract Data-type which is classified in linear data structure where
all insertions and deletions are permitted only at one end of the list that follows
the LIFO (Last-In-First-Out) principle. It is an ordered list of the same type of
elements. Stack has one end, whereas the Queue has two ends (front and rear). It
contains only one pointer top pointer pointing to the topmost element of the stack.
Whenever an element is added in the stack, it is added on the top of the stack, and
the element can be deleted only from the top of 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. It is named stack as it behaves like a real-
world stack, for example: a deck of cards or a pile of plates, etc.

Following diagram represents the structure and operation of stack.

By Sr. Asst. Prof. Pratik Chand, LTU Page 1

 Data Structure and Algorithm

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.

Following table shows the position of the top which indicates the status of the stack.

Position of Top Status of Stack

-1 Stack is Empty
0 Only one element in stack
N-1 Stack is Full
N Stack is Overflow

Stack as a ADT:
The abstract data-type is special kind of data-type, whose behavior is defined by a
set of values and set of operations. The keyword “Abstract” is used as we can use
these data-types, we can perform different operations. But how those operations are
working that is totally hidden from the user. The ADT is made of with primitive
data-types, but operation logics are hidden.

Here we will see the stack ADT. These are few operations or functions of the Stack
ADT.

 isFull(), This is used to check whether stack is full or not

 isEmpry(), This is used to check whether stack is empty or not
 push(x), This is used to push x into the stack

By Sr. Asst. Prof. Pratik Chand, LTU Page 2

 Data Structure and Algorithm

 pop(), This is used to delete one element from top of the stack
 peek(), This is used to get the top most element of the stack
 size(), this function is used to get number of elements present into the stack

PUSH and POP Operation of Stack:

PUSH Operation:
The process of putting a new data element onto stack is known as a Push Operation.

Algorithm for push operation

Step1: Start

Step2: Check whether the stack is full or not.

 If stack is full, then display error message as “Stack overflow” and go to step
4.
 Else if stack is not full, increment top by 1, i.e. top=top+1 and insert element
at the new top of the stack.

if(top==[Link]-1)
{
Display error message “Stack is oveflow”;
Return;
}
top = top + 1;
stack[top] = data;
Step3: Repeat step 2 until top reach to (n-1) position i.e. max size of the stack.

Step4: Stop

By Sr. Asst. Prof. Pratik Chand, LTU Page 3

 Data Structure and Algorithm

POP Operation:
Accessing the content while removing it from the stack, is known as a Pop
Operation. In an array implementation of pop() operation, the data element is not
actually removed, instead top is decremented to a lower position in the stack to point
to the next value. But in linked-list implementation, pop() actually removes data
element and de-allocates memory space.

Algorithm for pop operation

Step1: Start

Step2: Check whether the stack is empty or not.

 If stack is empty, then display error message as “Stack underflow” and go to

step 4
 Else if stack is not empty, pop or delete element from the top of the stack and
decrement top by 1, i.e. top=top-1.

if(top==-1)
{
Display error message “Stack is empty”;
Return;
}

By Sr. Asst. Prof. Pratik Chand, LTU Page 4

 Data Structure and Algorithm

data = stack[top];
top = top - 1;
Step3: Repeat step 2 until top reach to (-1) position i.e. Stack is empty.

Step4: Stop

Example: Stack implementation using array

// Create a stack and perform the push and pop operations using array.
public class stack {
int [] mystack;
int top;
public stack(int size)
{
mystack = new int[size];
top = -1;
[Link]("Stack is creaded");
}
// Push data into the stack
public void push(int data)

By Sr. Asst. Prof. Pratik Chand, LTU Page 5

 Data Structure and Algorithm

{
if(top==[Link]-1)
{
[Link]("Error: Stack overflow.");
return;
}
top=top+1;
mystack[top] = data;
[Link]("Data "+data+ " is pushed into the stack.");
}
// Pop data from stack
public void pop()
{
if(top==-1)
{
[Link]("Error: Stack underflow.");
return;
}
int data = mystack[top];
top = top-1;
[Link]("Data poped from stack is "+data);
}
// Display data remaining in stack
public void display()
{
if(top==-1)
{
[Link]("Stack is empty");
}
else{
[Link]("Data Remaining in stack:");
for(int i=top; i>=0;i--)
{
[Link](mystack[i]+" ");
}

By Sr. Asst. Prof. Pratik Chand, LTU Page 6

 Data Structure and Algorithm

}
}
public static void main(String[] args) {
stack newStack = new stack(5);
[Link](10);
[Link](20);
[Link](30);
[Link](20);
[Link](30);
[Link](100);
[Link]();
[Link]();
[Link]();
[Link]();
}
}
Application of Stack:
The applications of stack in different fields are describe bellow:

 Expression Representation and Evaluation

 Expression Conversion
 Backtracking
 Function Call
 String Reversal

Expression Representation and Evaluation

Expression Representation:
Infix expression: In this expression an operator is in-between every pair of
operands. For example: a+b

Prefix expression: In this expression an operator is place before every pair of

operands. For example: +ab

By Sr. Asst. Prof. Pratik Chand, LTU Page 7

 Data Structure and Algorithm

Postfix expression: In this expression an operator is place after every pair of

operands. For example: ab+

Expression Evaluation:
To evaluate an expression we need to know the Precedence and Associativity of the
expression which determines the order of evaluation of an expression. Following is
an operator precedence and associativity table (highest to lowest)

S.N. Operator Precedence Associativity

1 Parenthesis ( ) { } [ ] Highest Left to Right

2 Exponentiation ^ Second Highest Right to Left

3 Multiplication ( ∗ ) & Division ( / ) Third Highest Left to Right

4 Addition ( + ) & Subtraction ( − ) Lowest Left to Right

In the normal expression evaluation we do evaluation according to precedence of

operator. And iterate the process until result is found. For example, consider the
following expression

5 * ( 6 + 2 ) - 12 / 4

Parenthesis has the highest precedence among the arithmetic operators, (6 +2) =
8 will be evaluated first. Now, the expression becomes

5 * 8 - 12 / 4

* and / have equal precedence and their associativity is from left-to-right. So, start
evaluating the expression from left-to-right.

5 * 8 = 40 and 12 / 4 = 3

By Sr. Asst. Prof. Pratik Chand, LTU Page 8

 Data Structure and Algorithm

Now, the expression becomes

40 - 3

And the value returned after the subtraction operation is 37.

In the above example, we have to scan whole expression for every iteration, if the
expression is complex it took lots of time and memory. To overcome this problem,
stack is used. Using stack we can complete the evaluation within single scan.

There are three types of expression evaluation

 Infix Expression Evaluation

 Prefix Expression Evaluation
 Postfix Expression Evaluation

Let’s discuss expression evaluation of infix, prefix and postfix expression using
stack.

Infix expression evaluation using stack

Algorithm for Infix expression evaluation

Step1: Start

Step2: Read the character from left to right

Step3: If the character is an operand, push it to the operand stack.

Step4: If the character is “(”, then push it onto the operator stack.

Step5: If the character is “)”, then do Process until the corresponding “(” is
encountered in operator stack. Then, just pop out and ignore the “(”.

Step6: If the character is an operator,

a. If the operator stack is empty then push it to the operator stack.

b. If the operator stack is not empty,
 If the character’s precedence is greater than or equal to the
precedence of top of the operator stack, or “(” is encounter, then
push the character to the operator stack.

By Sr. Asst. Prof. Pratik Chand, LTU Page 9

 Data Structure and Algorithm

 If the character’s precedence is less than the precedence of top of

the operator stack then, pop two character from operand stack and
process according to operator in (p2 operator p1) pattern and push
the result in to the operand stack, repeat the process until top of the
operator in stack precedence is less or “(” is encounter or stack is
empty.

Step7: Once the expression iteration is completed and the operator stack is not
empty, Process until the operator stack is empty. The value left in the operand stack
is our final result.

Step8: Stop

Example: Evaluate the expression 2+(5-3*6/2) using stack

Input Character Operand Stack Operator Stack Process

2 2
+ 2 +
( 2 +(
5 2,5 +(
- 2,5 +(-
3 2,5,3 +(-
* 2,5,3 +(-*
6 2,5,3,6 +(-*
/ 2,5,3,6 +(-*/
2 2,5,3,6,2 +(-*/
) 2,5,3,3 +(-* 6/2=3
2,5,9 +(- 3*3=9
2,-4 + 5-9=-4
-2 2+(-4)=-2
Hence, the result is -2.

Prefix expression evaluation using stack

Algorithm for Prefix expression evaluation

Step1: Start

Step2: Read character from right to left in given expression

By Sr. Asst. Prof. Pratik Chand, LTU Page 10

 Data Structure and Algorithm

Step3: If character is operand, push it in to stack

Step4: If the character is “(”, then push it onto the stack.

Step5: If the character is “)”, then do Process according to operator until the
corresponding “(” is encountered in stack. Then, just pop out and ignore the “(”.

Step6: If character is operator

a. Pop the two operand from the top of the stack

b. Perform the operation according to operator in (p1 operator p2) pattern.
Then, push the result to the operand stack

Step7: Stop

Example: Evaluate the prefix expression -,+*2,3,*,5,4,9 using stack

Input Character Stack Evaluation

9 9
4 9,4
5 9,4,5
* 9,20 5*4=20
3 9,20,3
2 9,20,3,2
* 9,20,6 2*3=6
+ 9,26 6+20=26
- 17 26-9=17

Hence, the result is 17.

Postfix expressing evaluation using stack

Algorithm for Postfix expression evaluation

Step1: Start

Step2: Read character from left to right in given expression

Step3: If character is operand, push it in to stack

Step5: If the character is “(“, then push it onto the stack.

By Sr. Asst. Prof. Pratik Chand, LTU Page 11

 Data Structure and Algorithm

Step6: If the character is “)”, then do Process according to operator until the
corresponding “(” is encountered in stack. Then, just pop out and ignore the “(”.

Step4: If character is operator

a. Pop the two operand from the top of the stack

b. Perform the operation according to operator in (p2 operator p1) pattern.
Then, push the result to the stack

Step7: Stop

Example: Evaluate the postfix expression 2,3,*,5,4,*,+,9,- using stack

Input Character Stack Evaluation

2 2
3 2,3
* 6 2*3=6
5 6,5
4 6,5,4
* 6,20 5*4=20
+ 26 6+20=26
9 26,9
- 17 26-9=17

Hence, the result is 17.

Expression Conversion:

Expression conversion is the process of converting expression from one form to

another form. Following are the list of expression conversion.

 Infix to Prefix
 Infix to Postfix
 Prefix to Infix
 Prefix to Postfix
 Postfix to Infix
 Postfix to Prefix

Why we use stack for expression conversion?

By Sr. Asst. Prof. Pratik Chand, LTU Page 12

 Data Structure and Algorithm

Ans: let’s take an example to expression conversion without using stack

Convert infix expression A+(B*C) in to postfix expression

Step1: search for higher precedence operator and perform the operation. Here, ( ) is
there so do operation for ( ) i.e. A+BC*

Step2: then, again repeat the step1, i.e. ABC*+

For this, we have to scan whole expression for every iteration, if the expression is
complex then it takes lots of time and memory. So, to overcome this problem stack
is used in expression conversion.

Conversion of Infix to Prefix expression using stack

Algorithm for Infix to Prefix Conversion:

Step1: Start

Step2: First, reverse the given infix expression.

Step3: Scan the characters one by one.

Step4: If the character is an operand, Display to prefix expression.

Step5: If the character is “)”, then push it to the stack.

Sep6: If the character is “(”, pop the elements from the top of the stack until the
corresponding “)” is not found.

Step7: If the character is an operator

a. If the character has precedence greater than the top of the stack, OR, top of
the stack is “)”, OR, stack is empty, push the operator to the stack.
b. If the character is equals to top of the stack check associativity
 If associativity is left to right push the character in the stack
 If the associativity is right to left, pop the operator from top of the stack
and go to step7.
c. If the character has precedence lesser than the top of the stack, pop the
operator and display it and go to step7.

Step8: If there is no more input, pop out the remaining operators and display.

By Sr. Asst. Prof. Pratik Chand, LTU Page 13

 Data Structure and Algorithm

Step9: After all the characters are scanned, reverse the output.

Step10: Stop

Example: Convert the infix A+B-C*D+(E^F)*G/H/I in to Prefix expression.

First of all reverse the given infix expression I/H/G*)F^E(+D*C-B+A

Input Character Stack Prefix Expression

I I
/ / I
H / IH
/ // IH
G // IHG
* //* IHG
) //*) IHG
F //*) IHGF
^ //*)^ IHGF
E //*)^ IHGFE
( //* IHGFE^
+ // IHGFE^*
/ IHGFE^*//
+ IHGFE^*//
D + IHGFE^*//D
* +* IHGFE^*//D
C +* IHGFE^*//DC
- + IHGFE^*//DC*
+- IHGFE^*//DC*
B +- IHGFE^*//DC*B
+ +-+ IHGFE^*//DC*B
A +-+ IHGFE^*//DC*BA
IHGFE^*//DC*BA+-+

New, reverse the final expression +-+AB*CD//*^EFGHI this is prefix expression.

Conversion of Infix to Postfix using Stack

Algorithm for Infix to Postfix Conversion:

Step1: Start

By Sr. Asst. Prof. Pratik Chand, LTU Page 14

 Data Structure and Algorithm

Step2: Scan the infix expression character.

Step3: If character is operand, display it.

Step4: If character is “(”, insert it on stack.

Step5: If it is “)”, Pop out the operator from stack and display them until “(” is not
found. Then, Pop out and discard the “(”.

Step6: If character is an operator, then

a. If character has higher precedence than the top of stack, OR top of the stack
is empty OR stack has “(”, insert the operator on stack.
b. If the character has lower precedence than top of the stack, pop out the
operator from the stack and display it. Then go to Step5.
c. If it has equal precedence check associativity
 If associativity is Left to Right, then, pop out the operator at top of the
stack and display. Then go to step5.
 If associativity is Right to Left insert the operator in the stack.

Step8: If there is no more input, pop out the remaining operators and display.

Step9: Stop

Example: Covert the Infix expression L-M*N+(O/P)+W^U^V in to Postfix

expression using Stack

Input Character Stack Postfix Expression

L L
- - L
M - LM
* -* LM
N -* LMN
+ + LMN*-
( +( LMN*-
O +( LMN*-O
/ +(/ LMN*-O
P +(/ LMN*-OP
) + LMN*-OP/
+ + LMN*-OP/+

By Sr. Asst. Prof. Pratik Chand, LTU Page 15

 Data Structure and Algorithm

W + LMN*-OP/+W
^ +^ LMN*-OP/+W
U +^ LMN*-OP/+WU
^ +^^ LMN*-OP/+WU
V +^^ LMN*-OP/+WUV
LMN*-OP/+WUV^^+

Hence, the postfix expression is LMN*-OP/+WUV^^+

Conversion of Prefix to Infix

Algorithm for Prefix to Infix Conversion:

Step1: Start

Step2: Read the Prefix expression from right to left

Step3: If the character is an operand, then push to the Stack

Step4: If the character is an operator,

 Pop two operands from the Stack

 Create a string by concatenating the two operands and the operator between
them i.e. string = (operand1, operator, operand2)
 Push the resultant string back to Stack

Step5: Repeat the above steps until end of Prefix expression.

Step6: Stop

Example: Convert Prefix expression *+AB/CD to Infix expression

Input Character Stack New String

D D
C D,C
/ C/D (C/D)
B (C/D),B
A (C/D),B,A
+ (C/D), (A+B) (A+B)
* ((A+B)*(C+D)) (A+B)*(C+D)

By Sr. Asst. Prof. Pratik Chand, LTU Page 16

 Data Structure and Algorithm

Hence, Infix expression if ((A+B)*(C+D))

Conversion of Prefix to Postfix

Algorithm for Prefix to Postfix Conversion:

Step1: Start

Step2: Read the Prefix expression from right to left

Step3: If the character is an operand, then push to the Stack

Step4: If the character is an operator

 Pop two operands from the Stack

 Create a string by concatenating the two operands and the operator after
them. i.e. string = operand1, operand2, operator
 And push the resultant string back to Stack

Step5: Repeat the above steps until end of Prefix expression.

Step6: Stop

Example: Convert prefix expression * - A / B C - / A K L to postfix expression

Input Character Stack New String

L L,
K L,K,
A L,K,A
/ L, AK/ AK/
- AK/L- AK/L-
C AK/L-,C
B AK/L-,C,B
/ AK/L-,BC/ BC/
A AK/L-,BC/,A
- AK/L-, ABC/- ABC/-
* ABC/-AK/L-* ABC/-AK/L-*

Hence, the Postfix expression is ABC/-AK/L-*

By Sr. Asst. Prof. Pratik Chand, LTU Page 17

 Data Structure and Algorithm

Conversion of Postfix to Infix expression

Algorithm for Postfix to Infix Conversion:

Step1: Start

Step2: Read the Prefix expression from left to right

Step3: If the character is an operand, then push to the Stack

Step4: If the character is an operator,

 Pop two operands from the Stack

 Create a string by concatenating the two operands and the operator between
them i.e. string = (operand2, operator, operand1)
 Push the resultant string back to Stack

Step5: Repeat the above steps until end of Prefix expression.

Step6: Stop

Example: Convert the Postfix expression AB+CD/* in to Infix expression

Input Character Stack New String

A A
B A,B
+ (A+B) (A+B)
C (A+B),C
D (A+B),C,D
/ (A+B), (C/D) (C/D)
* ((A+B)*(C/D)) ((A+B)*(C/D))

Hence, Infix expression is ((A+B)*(C/D))

By Sr. Asst. Prof. Pratik Chand, LTU Page 18

 Data Structure and Algorithm

Conversion of Postfix to Prefix expression

Algorithm for Postfix to Prefix Conversion:

Step1: Start

Step2: Read the Postfix expression from left to right

Step3: If the character is an operand, then push to the Stack

Step4: If the character is an operator

 Pop two operands from the Stack

 Create a string by concatenating the two operands and the operator before
them i.e. string = operator, operand2, operand1
 And push the resultant string back to Stack

Step5: Repeat the above steps until end of Prefix expression.

Step6: Stop

Example: Convert Postfix expression AB + CD - * in to Prefix expression

Input Character Stack New String

A A
B A,B
+ +AB +AB
C +AB,C
D +AB,C,D
- +AB, -CD -CD
* *+AB-CD *+AB-CD

Hence, Prefix expression is *+AB-CD

Backtracking

Backtracking is a recursive algorithm which is used for solving the optimization

problem. So, In order to find the optimized solution of a problem with Backtracking,

By Sr. Asst. Prof. Pratik Chand, LTU Page 19

 Data Structure and Algorithm

we have to find each and every possible solution of the problem, doesn’t matter if it
is correct or not.

In Backtracking, while finding the every possible solution of a problem, we store the
solution of a previously calculated problem in Stack and use that solution to solve
the upcoming problems. For example: N-Queen Problem

Function Call

In Programming, whenever you make a call from one function to another function.
The address of the calling function gets stored in the Stack. So, when the called
function gets terminated. The program control move back to the calling function
with the help of the address which was previously stored in the Stack. So, Stack
plays the main role when it comes to Calling a Function from other Function.

String Reversal

String Reversal is another amazing Application of Stack. Here, one by one each
character of the String gets inserted into the Stack. So, the first character of the String
is on the bottom of the Stack and the last character of the String is on the Top of the
Stack. After performing the pop operation in Stack, we get the String in Reverse
order.

Assignment:

1. What is stack? Write the algorithm for Push and Pop operation of stack.
2. Evaluate the infix expression 5+9-(7*4)/2-5 using stack.
3. Convert prefix expression *+9,5-2,4 into postfix expression.
4. Convert infix expression 9+4(8-2)/4 into prefix and postfix expression.
5. Explain the application area of stack.

End of Unit-2

By Sr. Asst. Prof. Pratik Chand, LTU Page 20