MODULE - 1

Contents: Introduction to Data Structures: Definitions, Classifications of Data

Structures- ADT and CDT, Linear and Non-Linear, Static and Dynamic. Algorithm/Program
Development: Analysis of Algorithms- Space Complexity, Understanding the notion of Time
Complexity using graphical and tabular representation for Linear, Quadratic, Cubical,
Logarithmic and Exponential functions. Asymptotic Notations- Best Case, Worst Case,
Average Case. Arrays: Definition, Properties of Array. Representation of
Single/Two-dimensional Arrays, Sparse Matrix, Polynomial representation, and manipulation
using Arrays (Addition only). Stack: Operations on Stack using Array Queues: Definition,
Operations on Queue using Array, Circular Queue implementation using Array, Other types
of Queues: Dequeue, Priority Queue (Concept only) Applications of Stack: Infix to Postfix
conversion and Postfix evaluation.

Data Structure - Definition and Classification

●​ Data structures are the fundamental building blocks of computer programming.

●​ They define how data is organized, stored, and manipulated within a program.
●​ Understanding data structures is very important for developing efficient and effective
algorithms.

A data structure is a storage that is used to store and organize data. It is a way of arranging
data on a computer so that it can be accessed and updated efficiently. A data structure is not
only used for organizing the data. It is also used for processing, retrieving, and storing data.

Types of Data Structures

1.​ Linear Data Structure: Data structure in which data elements are arranged

sequentially or linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure. ​
Example: Array, Stack, Queue, Linked List, etc.
2.​ Static Data Structure: Static data structure has a fixed memory size. It is easier

to access the elements in a static data structure. ​

Example: array.
3.​ Dynamic Data Structure: In dynamic data structure, the size is not fixed. It can

be randomly updated during the runtime which may be considered efficient

concerning the memory (space) complexity of the code. ​
Example: Queue, Stack, etc.
4.​ Non-Linear Data Structure: Data structures where data elements are not placed

sequentially or linearly are called non-linear data structures. In a non-linear data

 structure, we can’t traverse all the elements in a single run only. ​
Examples: Trees and Graphs.

Abstract data types (ADT):

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and
behaviors for a data structure, without specifying how these operations are
implemented or how data is organized in memory. It is a type (or class) of objects whose
behaviour is defined by a set of values and a set of operations. The user interacts with the
interface, using the operations that have been specified by the abstract data type. It offers a
high level use of a concept independent of it's implementation. They package data structure
and operations on them hiding internal details.
A data type refers to the type of values that variables in a programming language hold.
Eg: Integer, real, character, and boolean are inherently provided in programming languages
are referred to as primitive data types.

A list of elements is called as a data object.

Eg: List of integers or list of alphabetical strings as data objects.

The data objects which comprise the data structure, and their fundamental operations are
known as Abstract Data Type (ADT).

ADT is defined as a set of data objects D defined over a domain L and supporting a list of
operations O.

Concrete Data Types(CDT) :

A concrete data type is the opposite of an abstract data type. It is a specialized

solution-oriented data type that represents a well-defined single solution domain concept. A
concrete data type is rarely reusable beyond its original use, but can be embedded or
composed with other data types to form larger data types. They are direct implementations
of a relatively simple concept. It does not hide anything.

Examples -
Use a struct with public data and no functions to represent the record

S. Concrete Data Types or

Abstract Data Types or structure (ADT)
No. structure (CDT)

Concrete data types or

Abstract Data Types or structures
structures provide how these
1 describe the data and the operations to
operations are actually
manipulate and change it.
implemented.
 Most of the program becomes
Which is not possible in
independent of the abstract data types
2 Concrete Data Types or
representation, so it can be improved
structure (CDT)
without breaking the program.

It's easier for each part of a program to

It is not so efficient compared to
3 use an implementation of its data types
ADT.
and that will be more efficient.

Implementation of a simple
4 Implementation of a high level concept
concept

It is rarely reusable beyond its

5 It is usable beyond its original use.
original use.

6 It hides the internal details. It doesn't hide anything.

7 It uses class. It uses structure.

Examples-Arrays, linked lists,

8 Examples- lists, sets, stacks.
trees, graphs.

Algorithm/Program Development: Analysis of Algorithms:

An algorithm is thus a sequence of computational steps that transform the input into the
output

An algorithm is independent of the programming language.

Algorithm analysis is an important part of computational complexity theory, which provides

theoretical estimation for the required resources of an algorithm to solve a specific
computational problem. Analysis of algorithms is the determination of the amount of time and
space resources required to execute it.

The efficiency or running time of an algorithm is stated as a function relating the input length
to the number of steps, known as time complexity, or volume of memory, known as space
complexity.

Algorithm

An algorithm is a finite set of instructions which, if followed, accomplish a particular task.

Every algorithm must satisfy the following criteria

• Input – externally supplied

• Output – at least one quantity is produced
• Definiteness – each instruction must be clear and unambiguous
• Finiteness – for all cases , the algorithm will terminate after a number of steps
• Effectiveness –must be feasible

Algorthm/Program Developement:

Algorithm of Efficiency:-

1. Space efficiency - the memory required, also called, space complexity.

2. Time efficiency - the time required, also called time complexity.

Space Efficiency:- There are some circumstances where the space/memory used must be
analyzed. For example, for large quantities of data or for embedded systems programming.

Components of space/memory use:

1. instruction space : Affected by: the compiler, compiler options, target computer (cpu)
2. data space : Affected by: the data size/dynamically allocated memory, static program
variables,
3. run-time stack space : Affected by: the compiler, run-time function calls and recursion,
local variables, parameters

The space requirement has fixed/static/compile time and a variable/dynamic/runtime

components. Fixed components are the machine language instructions and static variables.
Variable components are the runtime stack usage and dynamically allocated memory usage.
Time Efficiency:-

Clearly the more quickly a program/function accomplishes its task the better.

●​ The actual running time depends on many factors:

●​ The speed of the computer: cpu (not just clock speed), I/O, etc.
●​ The compiler, compiler options .
●​ The quantity of data - ex. search a long list or short.
●​ The actual data - ex. in the sequential search if the name is first or last.

Algorithm Analysis:

●​ To analyze an algorithm is to determine the amount of resource (such as Time and

Storage Space) necessary to execute it.
●​ In theoretical analysis of algorithms, it is common to estimate their complexity in the
asymptotic sense, ie to estimate the complexity function for arbitrarily large input.

Space Complexity

The space complexity of a program is the amount of memory that it needs to run to
completion. The space needed the program is the sum of the following components:

1. Fixed Space Requirements

●​ Do not depend on the number and size of the program’s input and output.
●​ The fixed requirements include, the instruction space(space needed to store the
code), space for simple variable, constants etc.

2. Variable Space Requirements

●​ This component consist of the space needed by structured variables whose size
depends on the particular instance I, of the problem being solved.
●​ It also include the additional space required when a function use recursion.
●​ The variable space requirement of a program P working on an instance I is denoted
S (I).
●​ We can express the total space requirements S(P) of any program as
S(P)= c+ S (I)
●​ Where c is a constant representing the fixed space requirement.
●​ When analyzing the space complexity of a program, we are usually concerned with only the
variable space requirements.

Eg:

float abc(float a, float b, float c)

{
return a+b+b*c+(a+b-c)/(a+b)+4.00
}
 ●​ we have a function abc, which accepts three simple variables as input and returns a
simple value as output.
●​ According to the classification give, this function has only fixed space requirements.

𝐒𝐚𝐛𝐜(I) = 0

●​ Space complexity only consider variable space requirement.

●​ Variable space requirements occurs only when the function contains iteration,
recursion or loop.

Eg: Consider a recursive function for summing a list of numbers

float rsum(float list[], int n)

{
if (n)
return(rsum(list,n-1)+list[n-1]);
return(0);
}

●​ Here, the summation is handled recursively. This means that the compiler must save
the parameters, local variables and the return address for each recursive call.
●​ The following table shows that the number of bytes required for one recursive call
under the assumption that an integer and the array each required 4 bytes.

TYPE NAME NO. OF BYTES

Parameter 1 – array pointer list[] 4

Parameter 2 – integer n 4

return address 4

Total = 12

●​ The variable space is 12 for one time recursion. If ‘n’ is the size of an array,
then

Space complexity = n×12

●​ That is, in recursive function call, the space requirement is more compared
with the iteration space requirement.

Time Complexity

Understanding Time Complexity is essential for analyzing the performance of algorithms. It

tells us how the running time or space requirements of an algorithm grow with the input size.
Let’s explore the common time complexities with tabular and graphical representations
for:

●​ Linear: O(n)​

●​ Quadratic: O(n²)​

●​ Cubic: O(n³)​

●​ Logarithmic: O(log n)​

●​ Exponential: O(2ⁿ)

To dive a bit deeper into the topic of algorithm complexity, let's take a closer look at some
common time complexity functions.

●​ Constant Time Complexity (O(1)): An algorithm that takes the same amount of time
to solve a problem, regardless of the size of the input data, has a constant time
complexity of O(1). An example of an O(1) algorithm is accessing an element in an
array by its index.
●​ Logarithmic Time Complexity (O(log n)): An algorithm that takes time proportional to
the logarithm of the size of the input data has a logarithmic time complexity. An
example of a logarithmic time complexity algorithm is binary search.
●​ Linear Time Complexity (O(n)): An algorithm that takes time proportional to the size
of the input data has a linear time complexity. An example of a linear time complexity
algorithm is linear search.
●​ Quadratic Time Complexity (O(n^2)): An algorithm that takes time proportional to the
square of the size of the input data has a quadratic time complexity. An example of a
quadratic time complexity algorithm is bubble sort.
●​ Cubic Time Complexity (O(n^3)): An algorithm that takes time proportional to the
cube of the size of the input data has a cubic time complexity. An example of a cubic
time complexity algorithm is matrix multiplication.

●​ The time T(P) taken by a program P is the sum of its compile time and its run time.
●​ Time complexity only consider execution(run) time. Type of time complexities are

• Worst case time complexity – The maximum value of f(n) for any possible
input.
• Average case time complexity – The expected value of f(n)
• Best case time complexity – minimum possible value of f(n).
Where f(n) is a function/ computing time of an algorithm.

●​ Worst case time complexity of an algorithm gives an indication about maximum

machine time and other resources required to run an algorithm.
Frequency count method to calculate the computation time of an
algorithm

Two methods for Time Complexity calculation are:

1. Frequency count (Step count)
2. Asymptotic Notation

Frequency count – how many times the instruction is executed.

Rules
●​ Comments & Declarations – Step count=0
●​ Return & Assignment – Step count= 1
●​ Ignore low order exponent when higher order exponents are present

For example consider 5n⁴+7n +10n +n +100.

Here, Time Complexity (TC) = O(n⁴)

Nested Loops

●​ The total running time of a statement inside a group of nested loop is the running
time of the statement multiplied by the product of the size of all the loops.
 Eg: for (i=0;i<n;i++)
for (j=0;j<n;j++)
k++;

●​ This program fragment is O(𝒏𝟐)

Consecutive Statements

These just add, which means that the maximum is the one that counts.

Ie; if T₁(n) = O(f(n)) and T₂(n) = O(g(n)). Then,

a) T₁(n)+T₂(n) = max(O(f(n)), O(g(n)))

b) T₁(n)* T₂(n) = O (f(n)*g(n))

Eg:
for (i=0;i<n;i++) O(n)
a[i]=0;
for (i=0;i<n;i++)
for (j=0;j<n;j++) O(𝑛 )
a[i]+=a[j]+i+j;

This program fragment, which has O(n) works followed by O(n ) work, is also O(𝒏𝟐)

Asymptotic Notations for Complexity of Algorithms

Asymptotic analysis refers to computing the running time of any operation in

mathematical units of computation.

The time required by an algorithm falls under three types :

​ Best Case − Minimum time required for program execution.

​ Average Case − Average time required for program execution.
​ Worst Case − Maximum time required for program execution.

Best case scenario: The best case scenario describes the best-performing version of an
algorithm. This scenario occurs when the input data is particularly well-suited for the
algorithm, and the algorithm is able to solve the problem with minimal time and space
complexity.

Worst case scenario: The worst case scenario describes the worst-performing version of
an algorithm. This scenario occurs when the input data is particularly challenging for the
algorithm, and the algorithm takes a long time and requires a large amount of memory to
solve the problem.
Average case scenario: The average case scenario describes the average-performing
version of an algorithm. This scenario occurs when the input data is typical for the
algorithm, and the algorithm takes an average amount of time and requires an average
amount of memory to solve the problem.

Notations:

There are several notations used to express the time and space complexities of
algorithms. The most commonly used notations are:

1. Big “oh” [O]

●​ f(n) = O(g(n)) iff there exist 2 +ve constants c and n₀ such that |f(n)| ≤ c.|g(n)| for all
n≥ n₀

f(n) = computing time of some algorithm.

●​ When we say that the computing time of an algorithm is O(g(n)), we mean that its
execution takes no more than a constant time g(n).

Eg: 10n +4n +2

|f(n)|≤ c. |g(n)|
f(n) ≤ n for n≥5

TC = O(𝒏𝟐)

Properties of Big “oh”

 ●​ If the time complexity of f(n) is O(g(n)) and the time complexity of g(n) is O(h(n)), then
f(n) has a time complexity of O(h(n))
●​ If f(n)= O(h(n)) and g(n) = O(h(n)), then f(n)+g(n)= O(h(n))
●​ an has a time complexity of O(n ) where, a is constant.
●​ In Big Oh, g(n) is the upper bound of f(n)
●​ Rate of growth – 1, logn, n, nlogn, n^2 , n^3 , 2^n . These functions are general
functions which is same as g(n)

2. Omega (Ω)

f(n) = Ω(g(n)) iff there exist +ve constants c and n₀ such that f(n)≥c.g(n) for all n, n≥n₀

Here g(n) is the lower bound of f(n)

Eg: 10n +4n +2

f(n) ≥ c. g(n)
f(n) ≥ n for n≥1

TC = Ω (𝒏𝟐)

3. Theta (θ)

●​ f(n) = θ(g(n)) iff there exist +ve constants c₁ , c₂ and n₀ such that c₁.g(n)≤ f(n)≤c₂.g(n)
for all n, n≥n₀

●​ Gives average case TC

Eg:3n +2

TC = θ (n)
Array

●​ An array is a consecutive set of memory locations. An array is a set of pairs, ie; index
& values.
●​ For each index which is defined, there is a value associated with the index. In
mathematical term we call this a correspondence or a mapping.
●​ Array can be defined as:

Structure - ARRAY (value, index)

Declare - CREATE() array
RETRIEVE(array, index) value
STORE(array, index, value) array

●​ For all A is an array, i, j are index and x is value

An array is a collection of elements of the same data type, stored in contiguous

memory locations, where each element can be accessed using an index.

It is a linear data structure that allows efficient storage and retrieval of a fixed number of
data items.

Properties of Array:
Property Explanation

Homogeneous All elements in the array are of the same data type (e.g., all
Elements integers, all floats).

Contiguous Memory Array elements are stored in consecutive memory locations,

Allocation improving access efficiency.
 Fixed Size The size of the array is declared initially and remains constant
throughout its use.

Index-Based Access Each element can be directly accessed using an index

(starting from 0).

Efficient Element Accessing any element in an array takes constant time (O(1)),
Access (O(1)) due to direct indexing.

Static and Dynamic Arrays can be statically allocated (fixed at compile time) or
Allocation dynamically allocated (at runtime) in some languages.

Linear Data Structure Arrays are linear, meaning data is stored sequentially in
memory.

Memory Efficiency Arrays are memory efficient for storing similar data types
without additional overhead.

No Automatic Size Once created, an array cannot resize automatically (unless

Increase you use dynamic arrays in some languages).

Addition and Subtraction of Arrays:

The addition (+) and subtraction (-) operators can be used between arrays if and only if the
two arrays have the same dimensions and order, and are defined using the same set of array
labels.

One Dimensional Array

One dimensional array can be represented as follows:

A[lower bound : Upper bound]

Eg: A[3:4]

The address A[i] can be calculated by

Base address + ( i - Lower bound )= α+(i-L)

Here; base address is the starting address.

Total number of elements can be calculated by

Upper bound – Lower bound+1= U-L+1

Two Dimensional Array

It can be represented as
A[L₁…….U₁ , L₂…….U₂]

Row = U₁-L₁+1
Column = U₂-L₂+1

• So, Total number of elements= Row*Column

The two common ways to represent multidimensional arrays are:

1. Row major order
2. Column major order

Row Major

As its name implies, row major order stores multidimensional arrays by rows

A[L₁……..U₁ , L₂…….U₂]

Where U₁ = row representation

U₂ = column representation

Eg:

𝟏𝟐𝟑
𝟒𝟓𝟔 A [3,3] in C, A[3][3]
𝟕𝟖𝟗

we can find the address of A[i, j] using row major,

Base address + (i-L₁)U₂ + (j-L₂)

Where, U₂ represents column

Eg: A[5:7 , 2:4] find the address of A[6,3] , base address α=10.

L₁ U₁ L₂ U₂
A[5:7,2:4]
m (row) = U₁-L₁+1 = 3
n (column) = U₂-L₂+1 = 3

A(6,3)
=Base address + (i-L₁) column + (j-L₂)
= 10+(6-5)3 + (3-2)
= 10+4 = 14

Column Major

As its name implies, Column major order stores multidimensional arrays by columns

Eg:
𝟏𝟐𝟑
𝟒𝟓𝟔
𝟕𝟖𝟗

we can find the address of A[i, j] using row major,

Base address + (i-L₁) + (j-L₂)m

Where, m represents row

Eg: A[6:9 , 3:6] find the address of A[8,5] , base address α=10.
L₁ U₁ L₂ U₂
A[6:9,3:6]
m (row) = U₁-L₁+1 = 9-6+1 = 4
n (column) = U₂-L₂+1 = 6-3+1= 4

A(8,5)
= 10+(8-6) + (5-3)х 4
= 10+2+8 = 20

SPARSE MATRIX

●​ A matrix is a two-dimensional data object made of ‘m’ rows and ‘n’ columns,
therefore having total m x n values. If most of the elements of the matrix have
0 values, then it is called a sparse matrix.
●​ Sparse matrix is a matrix which contains very few non-zero elements.
●​ When a sparse matrix is represented with a 2-dimensional array, we waste a
lot of space to represent that matrix.

Consider a matrix of size 100 X 100 containing only 10 non-zero elements. In this
matrix, only 10 spaces are filled with non-zero values and remaining spaces of the
matrix are filled with zero. Totally we allocate 100 X 100 X 2 = 20000 bytes of space
to store this integer matrix. To access these 10 non-zero elements we have to make
scanning for 10000 times.

Sparse Matrix Representations can be done in many ways following are two
common representations:

​ •​ Array representation
​ •​ Three tuple form
 ​ •​ Linked list representation

2D array is used to represent a sparse matrix in which there are three columns
named as:

​ •​ Row:Index of row, where non-zero element is located

​ •​ Column:Index of column, where non-zero element is located
​ •​ Value:Value of the non zero element located at index
–(row,column)

Triplets
(0,2,3)
(0,4,4)
(1,2,5)
(1,3,7)
(3,1,2)
(3,2,6)

Why to use Sparse Matrix instead of simple matrix ?

●​ Storage: There are lesser non-zero elements than zeros and thus lesser
memory can be used to store only those elements.
●​ Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements.

ADVANTAGES OF USING SPARSE MATRIX

●​ Storage: We know that a sparse matrix contains lesser non-zero elements than zero,
so less memory can be used to store elements. It evaluates only the non-zero
elements.
●​ Computing time: In the case of searching in a sparse matrix, we need to traverse
only the non-zero elements rather than traversing all the sparse matrix elements. It
saves computing time by logically designing a data structure traversing non-zero
elements.

DISADVANTAGES OF USING SPARSE MATRIX

●​ When a sparse matrix is represented with a 2-dimensional array, we waste a lot of

space to represent that matrix.

Representation of Polynomial using Array

1ST METHOD
 ●​ One dimensional array is defined and coefficient is added to the array and
exponent is indicated by the index value
Eg : 2x +3x+1

●​ Here, array size is fixed. Usually it will be larger than the degree of
polynomial.

2ND METHOD

●​ Here a one dimensional array is defined and the coefficient is added to the
array and the exponent is represented by the array index.

●​ It differ from the first method in the size of array. Here size of the array is
defined as the largest degree of the polynomial.

●​ Disadvantage is waste of space.

Eg: 2x +1

3RD METHOD

●​ Here coefficient and exponent is stored in the array. Two pointers are used to
indicate the beginning and end of the polynomial.
●​ In this method , zero coefficient term is not used. There is no fixed size
allocation is needed.

Eg: A(x) = 2x +1 B(x)= x + 10x + 3x +1

Here, af and bf indicate the beginning of the polynomial. al and bl indicate the ending
of the polynomial.

To find the last term of the polynomial, we use

el = ef+(n-1)

Where,

el = last term of the polynomial

ef = first term of the polynomial
n = length of the polynomial
Eg: for B(x), el= 3+(4-1) = 6

STACK

●​ It is a linear data structure in which elements are placed one above another.
●​ A stack is an ordered collection of homogeneous data elements where the insertion and
deletion operations take place only at one end called Top of the stack.
●​ LIFO - In stack elements are arranged in Last-In-First-Out manner (LIFO). So it is also
called LIFO lists.
●​ Anything added to the stack goes on the “top” of the stack.
●​ Anything removed from the stack is taken from the “top” of the stack.
●​ Things are removed in the reverse order from that in which they were inserted

Operations of Stack

●​ Two basic operations of stack:

●​ PUSH : Insert an element at the top of stack
●​ POP: Delete an element from the top of stack
●​ An element in the stack is termed as ITEM.
●​ Initially top is set to -1, to indicate an empty stack. (Top = -1)
●​ The maximum no. of elements that a stack can accommodate is termed MAX_SIZE.
●​ If stack is full Top = MAX_SIZE - 1

Array representation of stack

●​ Stack can be represented using a linear array.

●​ There is a pointer called TOP to indicate the top of the stack top
 ●​ Overflow: If we try to insert a new element in the stack top (push) which is already
full, then the situation is called stack overflow.
●​ Underflow: If we try to delete an element (pop) from an empty stack, the situation is
called stack underflow.

Basic Operations

●​ push() − Pushing (storing) an element on the stack.

●​ pop() − Removing (accessing) an element from the stack.
●​ peek() − get the top data element of the stack, without removing it.

int peek() {
​ return stack[top];
}

isFull() − check if stack is full.

bool isfull() {
​ ​ if (top == MAX_SIZE)
return true;
​ ​ else
​ return false;
}

isEmpty() − check if stack is empty.

bool isempty() {
​ if(top == -1)
​ ​ return true;
​ else
​ ​ return false;
}

Algorithm: PUSH()

●​ Let A be an array with Maximum size as MAX_SIZE. Initially, top= -1

​ ​ Start

●​ if top < MAX_SIZE – 1

●​ set top=top+1
●​ Set A[top]=item
●​ else
●​ print “OVERFLOW”
●​ exit

POP Operation

Algorithm: POP()
​ Start
●​ if top= -1 then
●​ print “UNDERFLOW”
●​ else
●​ set item=A[top]
●​ Set top=top-1
●​ exit

QUEUES

●​ A queue is an ordered collection of homogeneous data elements. In which insertion is

done at one end called REAR and deletion is done at another end called FRONT.
●​ FIFO - In queue elements are arranged in First-In-First-Out manner (FIFO).
●​ First inserted element is removed first
●​ Two basic operations of queue:
●​ Enqueue -> Insert an element at the rear end of queue.
●​ Dequeue-> Delete an element from the front end of queue.
●​ Initial case rear = -1 and front = 0, MAX SIZE is the size of the queue.
●​ If rear = front then queue contains only a single element
●​ If rear < front then queue is empty
●​ Queue full : rear = n-1 and front =0
●​ Whenever an element is deleted from the queue, the value of FRONT is increased by
1.
●​ i.e. FRONT=FRONT+1
●​ Similarly, whenever an element is added to the queue, the REAR is incremented by 1
as,
●​ REAR=REAR+1

Array Representation of Queue

Basic Operations

●​ enqueue() − add (store) an item to the queue.

●​ dequeue() − remove (access) an item from the queue.
●​ peek() − Gets the element at the front of the queue without removing it.

int peek()
{
return queue[front];
}

●​ isfull() − Checks if the queue is full

bool isfull()
{
​ If (rear == MAXSIZE - 1)
 ​ return true;
​ else
​ return false;
}

●​ isempty() − Checks if the queue is empty.

​ bool isempty()
​ {
if(front < 0 || front > rear)
return true;
else
return false;
}
Algorithm : Enqueue
Start

●​ if rear = MAX_SIZE – 1 then

●​ ​ print “OVERFLOW”
●​ else
●​ set rear = rear + 1
●​ Set A[rear]=item
●​ exit

Algorithm : Dequeue
Start

●​ if rear < front then

●​ print “UNDER FLOW”
●​ else
●​ set item = A[front}
●​ set front = front + 1
●​ exit

Type of Queues

●​ Circular Queue
●​ Priority Queue
●​ Doubly ended Queue

5. CIRCULAR QUEUE

●​ To utilize space properly, circular queue is derived.

●​ In this queue the elements are inserted in circular manner.
●​ So that no space is wasted at all.
●​ Circular queue empty:
 FRONT= -1
REAR= -1

●​ Circular queue full:

(rear + 1) % max_size = Front

●​ It is a modification of simple queue in which the rear pointer is set to the initial
location, whenever it reaches the location max_size – 1.

Insertion Algorithm (ENQUEUE)

if (front == -1 & rear == -1)

●​ set front =0 and rear = 0

●​ Set a[rear]=item
●​ else if (front = (rear+1) % max_size) then
●​ Print over flow
●​ else
●​ set rear = (rear + 1)% max_size
●​ Set a[rear] = item
●​ Exit

Deletion Algorithm (DEQUEUE)

if front = -1 and rear = -1 then

print underflow and exit’

else if front = rear

set item= a[front]

set front = -1 and rear = -1​

else

set item= a[front]

set front = (front + 1) % max_size

Exit

Exit

7. PRIORITY QUEUE
 ●​ Regular queue follows a First In First Out (FIFO) order to insert and remove an item.
Whatever goes in first, comes out first.
●​ In a priority queue, an item with the highest priority comes out first.
●​ Therefore, the FIFO pattern is no longer valid.
●​ Every item in the priority queue is associated with a priority.
●​ It does not matter in which order we insert the items in the queue
●​ The item with higher priority must be removed before the item with the lower priority.
●​ If two elements have the same priority, they are served according to their order in the
queue.

Operations on a priority queue

●​ EnQueue: EnQueue operation inserts an item into the queue. The item can be inserted
at the end of the queue or at the front of the queue or at the middle. The item must
have a priority.
●​ DeQueue: DeQueue operation removes the item with the highest priority from the
queue.
●​ Peek: Peek operation reads the item with the highest priority.

Applications of Priority Queue

●​ CPU Scheduling
●​ Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum
Spanning Tree, etc
●​ All queue applications where priority is involved.
●​ For load balancing and interrupt handling in an operating system

8. DOUBLY ENDED QUEUE

A double-ended queue is a versatile data structure that allows for the insertion and deletion of
elements from both ends. A double-ended queue in the data structure is an extension of the
linear queue structure.

Deque provides greater flexibility in data handling. Unlike a standard queue, which follows
the First-In-First-Out (FIFO) principle, a deque can function in both FIFO and
Last-In-First-Out (LIFO) modes, making it suitable for various applications in programming
and algorithms.

Double-ended queues in the data structure are especially useful in scenarios where you need
to manage a collection of items with dynamic size and require efficient access to both ends.
They can be implemented using arrays or linked lists, each offering different performance
characteristics.
CONVERSION & EVALUATION OF EXPRESSIONS

●​ Infix Expression: The operator occurs between the operands

<operand> <operator> <operand>

Eg: a+b

●​ Prefix Expression (Polish notation): The operators occurs before the operand

<operator> <operand> <operand>

Eg : +ab

●​ Postfix Expression (Reverse Polish notation): The operators occurs after the
operand

<operand> <operand> <operator>

Eg : ab+

●​ Postfix Expression Evaluation

Given P is the postfix expression, the following algorithm uses a stack to hold operands. It
finds the value of the arithmetic expression P, Written in postfix notation.

Algorithm:
Step 1: Add “ ) “ at the end of P
Step 2: Scan P from left – right & repeat the steps 3 & 4
Step 3: If an operand occurs, PUSH it to stack.
Step 4: If an operator occurs, then
​ A: Remove the top elements of the stack.
When A is the top element and B is the next top element
B: Evaluate B A
C: Place the result of step B back to stack
Step 5: Set the value equals to TOP element of the stack.
Evaluate the expression 5 * ( 6 + 2 ) – 12 / 4

Ans : Convert to postfix notation

5 * 6 2 + - 12 / 4
5 6 2 + * - 12 4 /
= 5 6 2 + * 12 4 / -
Add “ ) “ at the end of P
P = 5 6 2 + * 12 4 / - )
Scanned Symbol Stack
5 5
6 5, 6
2 5, 6, 2
+ 5, 8
* 40
12 40, 12
4 40, 12, 4
/ 40, 3
- 37

Evaluate the expression ( 6 + 2 ) / ( 4 – 2 * 1 )

Ans: Convert to postfix notation

6 2 + / ( 4 – 2 1 *)
62+/421*-
62+421*-/
P=62+421*-/)
Scanned
Stack
Symbol
6 6
2 62
+ 8
4 84
2 842
1 8421
* 842
- 82
/ 4

Infix to Postfix conversion

Here the operators used are ^ , * , / , + , -. The following algorithm converts an Infix
expression Q to postfix expression P. This algorithm also uses a stack which holds the left
parenthesis and operators. We begin by pushing a Left parenthesis to stack and adding a right
parenthesis at the end of Q.
Algorithm
Step 1: PUSH left parenthesis “(“ into stack and add right parenthesis “ ) ” at the
end of Q.
Step 2: Scan the expression Q from Left – Right and repeat the step 3 to 6 for
each element of Q until this stack is empty.
Step 3: If an operand occurs add it to P.
Step 4: If a Left parenthesis occurs then PUSH it to stack
Step 5: If an operator occurs then
​ A: Repeatedly POP the stack and add to P, each operator which has same or
higher precedence than
​ B: add to stack
Step 6: If a Right parenthesis occurs then
​ A: Repeatedly POP from stack and add to P each operator until a left
parenthesis occurs.
​ B: Remove the left parenthesis
Step 7: Exit

●​ Q = A + ( B * C - ( D / E ^ F ) * G ) * H

Ans : Add right parenthesis at the end of the expression

Q=A+(B*C-(D/E^F)*G)*H)

Symbol
Stack p
Scanned
(
A ( A
+ (+ A
( (+( A
B (+( AB
* (+(* AB
C (+(* ABC
- (+(- ABC*
( (+(-( ABC*
D (+(-( ABC*D
/ (+(-(/ ABC*D
E (+(-(/ ABC*DE
^ (+(-(/^ ABC*DE
F (+(-(/^ ABC*DEF
) (+(- ABC*DEF ^ /
* (+(- * ABC*DEF ^ /
G (+(- * ABC*DEF ^ /G
) (+ ABC*DEF ^ /G * -
* (+* ABC*DEF ^ /G * -
H (+* ABC*DEF ^ /G * - H
) ABC*DEF ^ /G * - H * +

Q=((A+B)*C–(D–E))^(F+G)

Ans:
Q=((A+B)*C–(D–E))^(F+G))
Symbol
Stack p
Scanned
0 (
( ((
( (((
A ((( A
+ (((+ A
B (((+ AB
) (( AB+
* ((* AB+
C ((* AB+C
- ((- AB+C*
( ((-( AB+C*
D ((-( AB+C*D
- ((-(- AB+C*D
E ((-(- AB+C*DE
) ((- AB+C*DE-
) ( AB+C*DE--
^ (^ AB+C*DE--
( (^( AB+C*DE--
F (^( AB+C*DE--F
+ (^(+ AB+C*DE--F
G (^(+ AB+C*DE--FG
) (^ AB+C*DE--FG+
) AB+C*DE—FG+^

Q=(A+B)*C/D+E^F/G

Ans :
 Q=(A+B)*C/D+E^F/G)
Symbol
Stack p
Scanned
(
( ((
A (( A
+ ((+ A
B ((+ AB
) ( AB+
* (* AB+
C (* AB+C
/ (/ AB+C*
D (/ AB+C*D
+ (+ AB+C*D/
E (+ AB+C*D/E
^ (+^ AB+C*D/E
F (+^ AB+C*D/EF
/ (+/ AB+C*D/EF^
G (+/ AB+C*D/EF^G
) AB+C*D/EF^G/+