Data Structure

Data Structure is a branch of Computer Science. The study of data structure allows us to understand the
organization of data and the management of the data flow in order to increase the efficiency of any
process or program. Data Structure is a particular way of storing and organizing data in the memory of
the computer so that these data can easily be retrieved and efficiently utilized in the future when required.
The data can be managed in various ways, like the logical or mathematical model for a specific
organization of data is known as a data structure.

Basic Terminologies related to Data Structures

Data Structures are the building blocks of any software or program. Selecting the suitable data structure
for a program is an extremely challenging task for a programmer.

The following are some fundamental terminologies used whenever the data structures are involved:

1. Data: We can define data as an elementary value or a collection of values. For example, the Employee's
name and ID are the data related to the Employee.
2. Data Items: A Single unit of value is known as Data Item.
3. Group Items: Data Items that have subordinate data items are known as Group Items. For example, an
employee's name can have a first, middle, and last name.
4. Elementary Items: Data Items that are unable to divide into sub-items are known as Elementary Items. For
example, the ID of an Employee.
5. Entity and Attribute: A class of certain objects is represented by an Entity. It consists of different Attributes.
Each Attribute symbolizes the specific property of that Entity

Key Features of Data Structures

Some of the Significant Features of Data Structures are:

1. Robustness: Generally, all computer programmers aim to produce software that yields correct
output for every possible input, along with efficient execution on all hardware platforms. This type
of robust software must manage both valid and invalid inputs.
2. Adaptability: Building software applications like Web Browsers, Word Processors, and Internet
Search Engine include huge software systems that require correct and efficient working or
execution for many years. Moreover, software evolves due to emerging technologies or ever-
changing market conditions.
3. Reusability: The features like Reusability and Adaptability go hand in hand. It is known that the
programmer needs many resources to build any software, making it a costly enterprise. However,
if the software is developed in a reusable and adaptable way, then it can be applied in most future
applications. Thus, by executing quality data structures, it is possible to build reusable software,
which appears to be cost-effective and timesaving.
Classification of Data Structures
A Data Structure delivers a structured set of variables related to each other in various ways. It forms the
basis of a programming tool that signifies the relationship between the data elements and allows
programmers to process the data efficiently.

We can classify Data Structures into two categories:

1. Primitive Data Structure

2. Non-Primitive Data Structure

The following figure shows the different classifications of Data Structures.

Primitive Data Structures

1. Primitive Data Structures are the data structures consisting of the numbers and the characters that
come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under the Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't be divided further

Non-Primitive Data Structures

1. Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.
2. These data structures can't be manipulated or operated directly by machine-level instructions.
3. The focus of these data structures is on forming a set of data elements that is either homogeneous (same
data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data structures into two sub-
categories -
a. Linear Data Structures
b. Non-Linear Data Structures
Linear Data Structures
A data structure that preserves a linear connection among its data elements is known as a Linear Data
Structure. The arrangement of the data is done linearly, where each element consists of the successors
and predecessors except the first and the last data element. However, it is not necessarily true in the case
of memory, as the arrangement may not be sequential.

Based on memory allocation, the Linear Data Structures are further classified into two types:

1. Static Data Structures: The data structures having a fixed size are known as Static Data Structures. The
memory for these data structures is allocated at the compiler time, and their size cannot be changed by the
user after being compiled; however, the data stored in them can be altered.
The Array is the best example of the Static Data Structure as they have a fixed size, and its data can be
modified later.
2. Dynamic Data Structures: The data structures having a dynamic size are known as Dynamic Data
Structures. The memory of these data structures is allocated at the run time, and their size varies during the
run time of the code. Moreover, the user can change the size as well as the data elements stored in these
data structures at the run time of the code.
Linked Lists, Stacks, and Queues are common examples of dynamic data structures

Types of Linear Data Structures

The following is the list of Linear Data Structures that we generally use:

1. Arrays

An Array is a data structure used to collect multiple data elements of the same data type into one variable.
Instead of storing multiple values of the same data types in separate variable names, we could store all
of them together into one variable. This statement doesn't imply that we will have to unite all the values
of the same data type in any program into one array of that data type. But there will often be times when
some specific variables of the same data types are all related to one another in a way appropriate for an
array.

An Array is a list of elements where each element has a unique place in the list. The data elements of the
array share the same variable name; however, each carries a different index number called a subscript.
We can access any data element from the list with the help of its location in the list. Thus, the key feature
of the arrays to understand is that the data is stored in contiguous memory locations, making it possible
for the users to traverse through the data elements of the array using their respective indexes.

Figure 3. An Array
Arrays can be classified into different types:

a. One-Dimensional Array: An Array with only one row of data elements is known as a One-Dimensional
Array. It is stored in ascending storage location.
b. Two-Dimensional Array: An Array consisting of multiple rows and columns of data elements is called a
Two-Dimensional Array. It is also known as a Matrix.
c. Multidimensional Array: We can define Multidimensional Array as an Array of Arrays. Multidimensional
Arrays are not bounded to two indices or two dimensions as they can include as many indices are per the
need.

Some Applications of Array:

a. We can store a list of data elements belonging to the same data type.
b. Array acts as an auxiliary storage for other data structures.
c. The array also helps store data elements of a binary tree of the fixed count.
d. Array also acts as a storage of matrices.

2. Linked Lists

A Linked List is another example of a linear data structure used to store a collection of data elements
dynamically. Data elements in this data structure are represented by the Nodes, connected using links or
pointers. Each node contains two fields, the information field consists of the actual data, and the pointer
field consists of the address of the subsequent nodes in the list. The pointer of the last node of the linked
list consists of a null pointer, as it points to nothing. Unlike the Arrays, the user can dynamically adjust
the size of a Linked List as per the requirements.

Figure 4. A Linked List

Linked Lists can be classified into different types:

a. Singly Linked List: A Singly Linked List is the most common type of Linked List. Each node has data and a
pointer field containing an address to the next node.
b. Doubly Linked List: A Doubly Linked List consists of an information field and two pointer fields. The
information field contains the data. The first pointer field contains an address of the previous node, whereas
another pointer field contains a reference to the next node. Thus, we can go in both directions (backward
as well as forward).
c. Circular Linked List: The Circular Linked List is similar to the Singly Linked List. The only key difference is
that the last node contains the address of the first node, forming a circular loop in the Circular Linked List.
Some Applications of Linked Lists:

a. The Linked Lists help us implement stacks, queues, binary trees, and graphs of predefined size.
b. We can also implement Operating System's function for dynamic memory management.
c. Linked Lists also allow polynomial implementation for mathematical operations.
d. We can use Circular Linked List to implement Operating Systems or application functions that Round Robin
execution of tasks.
e. Circular Linked List is also helpful in a Slide Show where a user requires to go back to the first slide after
the last slide is presented.
f. Doubly Linked List is utilized to implement forward and backward buttons in a browser to move forward
and backward in the opened pages of a website.

3. Stacks

A Stack is a Linear Data Structure that follows the LIFO (Last In, First Out) principle that allows operations
like insertion and deletion from one end of the Stack, i.e., Top. Stacks can be implemented with the help
of contiguous memory, an Array, and non-contiguous memory, a Linked List. Real-life examples of Stacks
are piles of books, a deck of cards, piles of money, and many more.

Figure 5. A Real-life Example of Stack

The above figure represents the real-life example of a Stack where the operations are performed from
one end only, like the insertion and removal of new books from the top of the Stack. It implies that the
insertion and deletion in the Stack can be done only from the top of the Stack. We can access only the
Stack's tops at any given time.

The primary operations in the Stack are as follows:

a. Push: Operation to insert a new element in the Stack is termed as Push Operation.
b. Pop: Operation to remove or delete elements from the Stack is termed as Pop Operation.

Figure 6. A Stack

Some Applications of Stacks:

a. The Stack is used as a Temporary Storage Structure for recursive operations.

b. Stack is also utilized as Auxiliary Storage Structure for function calls, nested operations, and
deferred/postponed functions.
c. We can manage function calls using Stacks.
d. Stacks are also utilized to evaluate the arithmetic expressions in different programming languages.
e. Stacks are also helpful in converting infix expressions to postfix expressions.
f. Stacks allow us to check the expression's syntax in the programming environment.
g. We can match parenthesis using Stacks.
h. Stacks can be used to reverse a String.
i. Stacks are helpful in solving problems based on backtracking.
j. We can use Stacks in depth-first search in graph and tree traversal.
k. Stacks are also used in Operating System functions.
l. Stacks are also used in UNDO and REDO functions in an edit.

4. Queues

A Queue is a linear data structure similar to a Stack with some limitations on the insertion and deletion
of the elements. The insertion of an element in a Queue is done at one end, and the removal is done at
another or opposite end. Thus, we can conclude that the Queue data structure follows FIFO (First In, First
Out) principle to manipulate the data elements. Implementation of Queues can be done using Arrays,
Linked Lists, or Stacks. Some real-life examples of Queues are a line at the ticket counter, an escalator, a
car wash, and many more.

Figure A Real-life Example of Queue

The above image is a real-life illustration of a movie ticket counter that can help us understand the Queue
where the customer who comes first is always served first. The customer arriving last will undoubtedly be
served last. Both ends of the Queue are open and can execute different operations. Another example is a
food court line where the customer is inserted from the rear end while the customer is removed at the
front end after providing the service they asked for.

The following are the primary operations of the Queue:

a. Enqueue: The insertion or Addition of some data elements to the Queue is called Enqueue. The element
insertion is always done with the help of the rear pointer.
b. Dequeue: Deleting or removing data elements from the Queue is termed Dequeue. The deletion of the
element is always done with the help of the front pointer.

Figure A Queue
Some Applications of Queues:

a. Queues are generally used in the breadth search operation in Graphs.

b. Queues are also used in Job Scheduler Operations of Operating Systems, like a keyboard buffer queue to
store the keys pressed by users and a print buffer queue to store the documents printed by the printer.
c. Queues are responsible for CPU scheduling, Job scheduling, and Disk Scheduling.
d. Priority Queues are utilized in file-downloading operations in a browser.
e. Queues are also used to transfer data between peripheral devices and the CPU.
f. Queues are also responsible for handling interrupts generated by the User Applications for the CPU.

Non-Linear Data Structures

Non-Linear Data Structures are data structures where the data elements are not arranged in sequential
order. Here, the insertion and removal of data are not feasible in a linear manner. There exists a
hierarchical relationship between the individual data items.

Types of Non-Linear Data Structures

The following is the list of Non-Linear Data Structures that we generally use:

1. Trees

A Tree is a Non-Linear Data Structure and a hierarchy containing a collection of nodes such that each
node of the tree stores a value and a list of references to other nodes (the "children").

The Tree data structure is a specialized method to arrange and collect data in the computer to be utilized
more effectively. It contains a central node, structural nodes, and sub-nodes connected via edges. We can
also say that the tree data structure consists of roots, branches, and leaves connected.
Figure A Tree

Trees can be classified into different types:

a. Binary Tree: A Tree data structure where each parent node can have at most two children is termed a
Binary Tree.
b. Binary Search Tree: A Binary Search Tree is a Tree data structure where we can easily maintain a sorted list
of numbers.
c. AVL Tree: An AVL Tree is a self-balancing Binary Search Tree where each node maintains extra information
known as a Balance Factor whose value is either -1, 0, or +1.
d. B-Tree: A B-Tree is a special type of self-balancing Binary Search Tree where each node consists of multiple
keys and can have more than two children.

Some Applications of Trees:

a. Trees implement hierarchical structures in computer systems like directories and file systems.
b. Trees are also used to implement the navigation structure of a website.
c. We can generate code like Huffman's code using Trees.
d. Trees are also helpful in decision-making in Gaming applications.
e. Trees are responsible for implementing priority queues for priority-based OS scheduling functions.
f. Trees are also responsible for parsing expressions and statements in the compilers of different
programming languages.
g. We can use Trees to store data keys for indexing for Database Management System (DBMS).
h. Spanning Trees allows us to route decisions in Computer and Communications Networks.
i. Trees are also used in the path-finding algorithm implemented in Artificial Intelligence (AI), Robotics, and
Video Games Applications.

Representing Binary Tree in memory

Let T be a Binary Tree. There are two ways of representing T in the memory as follow

1. Sequential Representation of Binary Tree.

2. Link Representation of Binary Tree.

1) Linked Representation of Binary Tree

Consider a Binary Tree T. T will be maintained in memory by means of a linked list representation which
uses three parallel arrays; INFO, LEFT, and RIGHT pointer variable ROOT as follows. In Binary Tree each
node N of T will correspond to a location k such that

1. LEFT [k] contains the location of the left child of node N.

2. INFO [k] contains the data at the node N.
3. RIGHT [k] contains the location of right child of node N.
Representation of a node:

In this representation of binary tree root will contain the location of the root R of T. If any one of the
subtree is empty, then the corresponding pointer will contain the null value if the tree T itself is empty,
the ROOT will contain the null value.

Example

Consider the binary tree T in the figure. A schematic diagram of the linked list representation
of T appears in the following figure. Observe that each node is pictured with its three fields, and that
the empty subtree is pictured by using x for null entries.

Binary Tree

Linked Representation of the Binary Tree

2) Sequential representation of Binary Tree

Let us consider that we have a tree T. let our tree T is a binary tree that us complete binary tree. Then
there is an efficient way of representing T in the memory called the sequential representation or array
representation of T. This representation uses only a linear array TREE as follows:

1. The root N of T is stored in TREE [1].

2. If a node occupies TREE [k] then its left child is stored in TREE [2 * k] and its right child is stored
into TREE [2 * k + 1].

For Example:

Consider the following Tree:

Its sequential representation is as follow:

Basic Operations of Data Structures

In the following section, we will discuss the different types of operations that we can perform to
manipulate data in every data structure:
 1. Traversal: Traversing a data structure means accessing each data element exactly once so it can
be administered. For example, traversing is required while printing the names of all the employees
in a department.
2. Search: Search is another data structure operation which means to find the location of one or
more data elements that meet certain constraints. Such a data element may or may not be present
in the given set of data elements. For example, we can use the search operation to find the names
of all the employees who have the experience of more than 5 years.
3. Insertion: Insertion means inserting or adding new data elements to the collection. For example,
we can use the insertion operation to add the details of a new employee the company has recently
hired.
4. Deletion: Deletion means to remove or delete a specific data element from the given list of data
elements. For example, we can use the deleting operation to delete the name of an employee who
has left the job.
5. Sorting: Sorting means to arrange the data elements in either Ascending or Descending order
depending on the type of application. For example, we can use the sorting operation to arrange
the names of employees in a department in alphabetical order or estimate the top three
performers of the month by arranging the performance of the employees in descending order and
extracting the details of the top three.
6. Merge: Merge means to combine data elements of two sorted lists in order to form a single list of
sorted data elements.
7. Create: Create is an operation used to reserve memory for the data elements of the program. We
can perform this operation using a declaration statement. The creation of data structure can take
place either during the following:
a. Compile-time
b. Run-time
For example, the malloc() function is used in C Language to create data structure.
8. Selection: Selection means selecting a particular data from the available data. We can select any
particular data by specifying conditions inside the loop.
9. Update: The Update operation allows us to update or modify the data in the data structure. We
can also update any particular data by specifying some conditions inside the loop, like the
Selection operation.
10. Splitting: The Splitting operation allows us to divide data into various subparts decreasing the
overall process completion time.

DS Algorithm
An algorithm is a process or a set of rules required to perform calculations or some other problem-solving
operations especially by a computer. The formal definition of an algorithm is that it contains the finite set
of instructions which are being carried in a specific order to perform the specific task. It is not the complete
program or code; it is just a solution (logic) of a problem, which can be represented either as an informal
description using a Flowchart or Pseudocode.

Characteristics of an Algorithm
The following are the characteristics of an algorithm:

o Input: An algorithm has some input values. We can pass 0 or some input value to an algorithm.
o Output: We will get 1 or more output at the end of an algorithm.
o Unambiguity: An algorithm should be unambiguous which means that the instructions in an algorithm
should be clear and simple.
o Finiteness: An algorithm should have finiteness. Here, finiteness means that the algorithm should contain
a limited number of instructions, i.e., the instructions should be countable.
o Effectiveness: An algorithm should be effective as each instruction in an algorithm affects the overall
process.
o Language independent: An algorithm must be language-independent so that the instructions in an
algorithm can be implemented in any of the languages with the same output.

Dataflow of an Algorithm
o Problem: A problem can be a real-world problem or any instance from the real-world problem for which
we need to create a program or the set of instructions. The set of instructions is known as an algorithm.
o Algorithm: An algorithm will be designed for a problem which is a step by step procedure.
o Input: After designing an algorithm, the required and the desired inputs are provided to the algorithm.
o Processing unit: The input will be given to the processing unit, and the processing unit will produce the
desired output.
o Output: The output is the outcome or the result of the program.

Preliminaries of algorithms include123:

 An algorithm should be clear and unambiguous.
 There should be 0 or more well-defined inputs in an algorithm.
 An algorithm must produce one or more well-defined outputs that are equivalent to the desired
output.
 Algorithms must stop or end after a finite number of steps.
 In an algorithm, step-by-step instructions should be supplied, and they should be independent of
any computer code

Algorithm Analysis
The algorithm can be analyzed in two levels, i.e., first is before creating the algorithm, and second is after
creating the algorithm. The following are the two analysis of an algorithm:
 o Priori Analysis: Here, priori analysis is the theoretical analysis of an algorithm which is done before
implementing the algorithm. Various factors can be considered before implementing the algorithm like
processor speed, which has no effect on the implementation part.
o Posterior Analysis: Here, posterior analysis is a practical analysis of an algorithm. The practical analysis is
achieved by implementing the algorithm using any programming language. This analysis basically evaluate
that how much running time and space taken by the algorithm.

Algorithm Complexity
The performance of the algorithm can be measured in two factors:

o Time complexity: The time complexity of an algorithm is the amount of time required to complete the
execution. The time complexity of an algorithm is denoted by the big O notation. Here, big O notation is
the asymptotic notation to represent the time complexity. The time complexity is mainly calculated by
counting the number of steps to finish the execution. Let's understand the time complexity through an
example.

1. sum=0;
2. // Suppose we have to calculate the sum of n numbers.
3. for i=1 to n
4. sum=sum+i;
5. // when the loop ends then sum holds the sum of the n numbers
6. return sum;

In the above code, the time complexity of the loop statement will be atleast n, and if the value of n
increases, then the time complexity also increases. While the complexity of the code, i.e., return sum will
be constant as its value is not dependent on the value of n and will provide the result in one step only.
We generally consider the worst-time complexity as it is the maximum time taken for any given input
size.

o Space complexity: An algorithm's space complexity is the amount of space required to solve a problem
and produce an output. Similar to the time complexity, space complexity is also expressed in big O notation.

For an algorithm, the space is required for the following purposes:

1. To store program instructions

2. To store constant values
3. To store variable values
4. To track the function calls, jumping statements, etc.

Auxiliary space: The extra space required by the algorithm, excluding the input size, is known as an
auxiliary space. The space complexity considers both the spaces, i.e., auxiliary space, and space used by
the input.

So,
Space complexity = Auxiliary space + Input size.

Stack
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 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 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.

Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in
the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken
the stack of size 5 as shown below in which we are pushing the elements one by one until the stack
becomes full.

Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the
top to the bottom when we were entering the new element in the stack. The stack gets filled up from the
bottom to the top.

When we perform the delete operation on the stack, there is only one way for entry and exit as the other
end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In
the above case, the value 5 is entered first, so it will be removed only after the deletion of all the other
elements.

Standard Stack Operations

The following are some common operations implemented on the stack:
 o push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then
the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty
means that no element exists in the stack, this state is known as an underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.

PUSH operation
The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
o 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.
o The elements will be inserted until we reach the max size of the stack.

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

Applications of Stack
The following are the applications of the stack:

o Balancing of symbols: Stack is used for balancing a symbol. For example, we have the following program:

1. int main()
2. {
3. cout<<"Hello";
4. cout<<"javaTpoint";
5. }

As we know, each program has an opening and closing braces; when the opening braces come, we push
the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack.
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.

o 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.
 o 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.
o 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.
o DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
o 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.
o 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

o 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.

 Convert Infix expression to Postfix expression

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+

How to convert an Infix expression to a Postfix expression?

To convert infix expression to postfix expression, use the stack data structure. Scan the infix
expression from left to right. Whenever we get an operand, add it to the postfix expression
and if we get an operator or parenthesis add it to the stack by maintaining their precedence.
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

 Convert Infix To Prefix Notation

Given an infix expression, the task is to convert it to a prefix expression.
Infix Expression: The expression of type a ‘operator’ b (a+b, where + is an operator) i.e., when
the operator is between two operands.
Prefix Expression: The expression of type ‘operator’ a b (+ab where + is an operator) i.e.,
when the operator is placed before the operands.

Examples:
Input: A * B + C / D
Output: + * A B/ C D
Input: (A – B/C) * (A/K-L)
Output: *-A/BC-/AKL

How to convert infix expression to prefix expression?

To convert an infix expression to a prefix expression, we can use the stack data structure. The
idea is as follows:
 Step 1: Reverse the infix expression. Note while reversing each ‘(‘ will become ‘)’ and each
‘)’ becomes ‘(‘.
 Step 2: Convert the reversed infix expression to “nearly” postfix expression.
 While converting to postfix expression, instead of using pop operation to pop
operators with greater than or equal precedence, here we will only pop the
operators from stack that have greater precedence.
 Step 3: Reverse the postfix expression.
The stack is used to convert infix expression to postfix form.

Illustration:
See the below image for a clear idea:
 Convert infix expression to prefix expression

Evaluation of Postfix Expression

Given a postfix expression, the task is to evaluate the postfix expression.

Postfix expression: The expression of the form “a b operator” (ab+) i.e., when a pair of
operands is followed by an operator.
Examples:
Input: str = “2 3 1 * + 9 -“
Output: -4
Explanation: If the expression is converted into an infix expression, it will be 2 + (3 * 1) – 9 = 5
– 9 = -4.
Input: str = “100 200 + 2 / 5 * 7 +”
Output: 757
Evaluation of Postfix Expression using Stack:
To evaluate a postfix expression we can use a stack.
Iterate the expression from left to right and keep on storing the operands into a stack. Once an
operator is received, pop the two topmost elements and evaluate them and push the result in
the stack again.

Illustration:
Follow the below illustration for a better understanding:
Consider the expression: exp = “2 3 1 * + 9 -“
 Scan 2, it’s a number, So push it into stack. Stack contains ‘2’.

Push 2 into stack

 Scan 3, again a number, push it to stack, stack now contains ‘2 3’ (from bottom to top)

Push 3 into stack

 Scan 1, again a number, push it to stack, stack now contains ‘2 3 1’

Push 1 into stack

 Scan *, it’s an operator. Pop two operands from stack, apply the * operator on operands. We
get 3*1 which results in 3. We push the result 3 to stack. The stack now becomes ‘2 3’.

Evaluate * operator and push result in stack

 Scan +, it’s an operator. Pop two operands from stack, apply the + operator on operands.
We get 3 + 2 which results in 5. We push the result 5 to stack. The stack now becomes ‘5’.

Evaluate + operator and push result in stack

 Scan 9, it’s a number. So we push it to the stack. The stack now becomes ‘5 9’.

Push 9 into stack

 Scan -, it’s an operator, pop two operands from stack, apply the – operator on operands, we
get 5 – 9 which results in -4. We push the result -4 to the stack. The stack now becomes ‘-4’.

Evaluate ‘-‘ operator and push result in stack

 There are no more elements to scan, we return the top element from the stack (which is the
only element left in a stack).
So the result becomes -4.
Follow the steps mentioned below to evaluate postfix expression using stack:

 Create a stack to store operands (or values).

 Scan the given expression from left to right and do the following for every scanned element.
 If the element is a number, push it into the stack.
 If the element is an operator, pop operands for the operator from the stack.
Evaluate the operator and push the result back to the stack.
 When the expression is ended, the number in the stack is the final answer.