Data Structures and Algorithms

Module 1: Introduction to algorithms, array and linked list

Introduction of algorithms, analyzing algorithms. Arrays : Representation of Arrays. Implementation of

Stacks and queues. Application of Stack: Evaluation of Expression - Infix to postfix Conversion - Multiple
stacks and Queues, Sparse Matrices. Linked list : Singly Linked list - Linked stacks and queues. polynomial
addition - More on linked Lists - Doubly linked List.

Introduction to data structure:

Definition:

Data Structure can be defined as a group of data elements that provides an efficient way of storing and
organising data in the computer so that it can be used efficiently.

A data structure is a way of organising, managing, and storing data in a computer so that it can be accessed
and modified efficiently. An array is a collection of memory elements in which data is stored sequentially,
i.e., one after another. In other words, an array stores the elements in a continuous manner. This
organisation of data is done with the help of an array of data structures. There are also other ways to
organise the data in memory. Examples: Arrays, Linked List, Stack, Queue, etc.

Need of Data Structure:

• Processor Speed: To handle the large amount of data high-speed processor is required.

• Data Search: If our application contains 100 data, one of the users of our application needs to find a
particular data. At that time, we have to traverse the entire 100 data, in each and every file, so the result
will slow down.

• Multiple Requests: As thousands of users can search data simultaneously on a web server, even the fast
server fails while searching the data.

Advantages of Data Structures

• Efficiency: Efficiency of a program depends upon the choice of data structures. For example: suppose, we
have some data and we need to perform the search for a particular record. In that case, if we organize our
data in an array, we will have to search sequentially element by element. There are better data structures
which can make the search process efficient like ordered array, binary search tree or hash tables.

• Reusability: Data structures are reusable, i.e. once we have implemented a particular data structure, we
can use it at any other place. Implementation of data structures can be compiled into libraries which can be
used by different clients.

• Abstraction: Data structure is specified by the ADT which provides a level of abstraction. The client
program uses the data structure through interface only, without getting into the implementation details.

Characteristics of Data Structures

 Correctness − Data structure implementation should implement its interface correctly.
(it must perform all operations (like insert, delete, search) accurately and reliably, producing the
expected results without errors.)

• Time Complexity − Running time or the execution time of operations of data structure must be as
small as possible.
 • Space Complexity − Memory usage of a data structure operation should be as little as possible.

Basic Terminology
• Data − Data are values or set of values.
• Data Item − Data item refers to single unit of values.

• Group Items − Data items that are divided into sub items are called as Group Items.

• Elementary Items − Data items that cannot be divided are called as Elementary Items.

• Attribute and Entity − An entity is that which contains certain attributes or properties, which may be
assigned values.

• Entity Set − Entities of similar attributes form an entity set.

• Field − Field is a single elementary unit of information representing an attribute of an entity.

• Record − Record is a collection of field values of a given entity.

• File − File is a collection of records of the entities in a given entity set.

Primitive Data Structures

Primitive data structures are the basic building blocks of data manipulation.
They are directly operated upon by machine-level instructions.

Examples:
 Integer (int)
 Float (float)
  Character (char)
 Boolean (bool)
Characteristics:
 Simple and atomic (cannot be broken further).
 Fixed size in memory.
 Directly supported by the programming language.
Example (Python):
a = 10 # integer
b = 3.14 # float
c = 'A' # character
flag = True # Boolean

Non primitive Data Structures

Non-primitive data structures are derived from primitive types.
They are used to store large and complex data. They are mainly classified into two types: Linear Data
Structures and Non-Linear Data Structures

(a) Linear Data Structures

Elements are arranged sequentially and can be traversed one after another.
Examples:
 Array
 Stack
 Queue
 Linked List
Example (Python):
arr = [10, 20, 30] # Array (List)
stack = [] # Stack
queue = [] # Queue

(b) Non-Linear Data Structures

Elements are not stored sequentially.

They are connected in a hierarchical or network manner.
Examples:
 Tree
 Graph
Example (Python):
tree = {'A': ['B', 'C']}
graph = {'A': ['B', 'C'], 'B': ['A', 'D']}

Linear Data Structures: A data structure is called linear if all of its elements are arranged in the linear order.
In linear data structures, the elements are stored in non-hierarchical way where each element has the
successors and predecessors except the first and last element.
Types of Linear Data Structures are :-

Arrays:- An array is a collection of similar type of data items and each data item is called an element of the
array. The data type like char, int, float or double. The array can be one dimensional, two dimensional or
multidimensional. Example:- age[0], age[1], age[2], age[3],......... age[98], age[99].

Linked List:- Linked list is a linear data structure which is used to maintain a list in the memory. It can be
seen as the collection of nodes stored at non-contiguous memory locations. Each node of the list contains a
pointer to its adjacent node.

Stack:- Stack is a linear list in which insertion and deletions are allowed only at one end, called top.

Queue:- Queue is a linear list in which elements can be inserted only at one end called rear and deleted
only at the other end called front.

Non Linear Data Structures

This data structure does not form a sequence i.e. each item or element is connected with two or more
other items in a non-linear arrangement. The data elements are not arranged in sequential structure.

Types of Non Linear Data Structures are :-

➢ Trees:- Trees are multilevel data structures with a hierarchical relationship among its elements known as
nodes. The bottommost nodes in the herierchy are called leaf node while the topmost node is called root
node. Each node contains pointers to point adjacent nodes.

➢ Graphs:- Graphs can be defined as the pictorial representation of the set of elements connected by the
links known as edges.

Operations on data structure

1) Traversing: Every data structure contains the set of data elements. Traversing the data structure means
visiting each element of the data structure in order to perform some specific operation like searching or
sorting.

2) Insertion: Insertion can be defined as the process of adding the elements to the data structure at any
location.

3) Deletion: The process of removing an element from the data structure is called Deletion.

4) Searching: The process of finding the location of an element within the data structure is called Searching.
There are two algorithms to perform searching, Linear Search and Binary Search.

5) Sorting: The process of arranging the data structure in a specific order is known as Sorting. There are
many algorithms that can be used to perform sorting, for example, insertion sort, selection sort, bubble
sort, etc.

6) Merging: When two lists List A and List B of size M and N respectively, of similar type of elements, joined
to produce the third list, List C of size (M+N), then this process is called merging.

Algorithm

Data Structures + Algorithm =Programs

An Algorithm is a finite sequence of instructions, each of which has a clear meaning and can be
performed with a finite amount of effort in a finite length of time. No matter what the input values
may be, an algorithm terminates after executing a finite number of instructions. In addition every
algorithm must satisfy the following criteria:
 Input: there are zero or more quantities, which are externally supplied;
 Output: at least one quantity is produced
 Definiteness: each instruction must be clear and unambiguous;
 Finiteness: if we trace out the instructions of an algorithm, then for all
cases the algorithm will terminate after a finite number of steps;
 Effectiveness: every instruction must be sufficiently basic that it can in
principle be carried out by a person using only pencil and paper. It is not
enough that each operation be definite, but it must also be feasible.

In formal computer science, one distinguishes between an algorithm, and a program. A program does not
necessarily satisfy the fourth condition. One important example of such a program for a computer is its
operating system, which never terminates (except for system crashes) but continues in a wait loop until
more jobs areentered.
We represent algorithm using a pseudo language that is a combination of the constructs of a
programming language together with informal English statements.

For example, we write an algorithm to find the maximum from a set of $n$ positive numbers. We assume
that the numbers are stored in an array, X.

Algorithm to find the maximum from an array, X as follows:

INPUT: An array, X, with n-elements.
OUTPUT: Finding the largest element, MAX, from the array, X.
Step-1: Set MAX=0 /* Initial value of MAX */
Step-2: for j=1 to n do
Step-3: if (X[j] > MAX) then MAX = X[j]
end for.
Step-4: Stop
Example: Write an algorithm to find the greatest of three numbers and then validate your algorithm.
Solution: The algorithm to find the greatest of three numbers, and then validate your algorithm.
Step-1: Input three numbers from the users a,b,c.
Step-2: Check. if (a > b)
Step-3: do if (a > c)
Step-4: then Print 'a' and go to step-12.
Step-5: else
Step-6: Print 'c' and go to step-12.
Step-7: else
Step-8: do if (b > c)
Step-9: then Print 'b' and go to step-12.
Step-10: else
Step-11: Print 'c' and go to step-12.
Step-12: Stop
Certainly! Here is the text converted from the image you provided, which discusses the properties and
analysis of algorithms:
PROPERTIES OF ALGORITHMS
Some Properties/Characteristics of an algorithm are as follows:
1. An algorithm consists of an ordered sequence of instructions.
2. Each step of the algorithms should be unambiguous i.e., it should not have many meanings.
3. It should have a finite number of steps. That is, it should have some limit on the number of steps
rather than going for infinite number of steps.
4. It should terminate/stop after some finite number of steps.
5. It should have some input and may/may not produce any output.
6. It should be effective i.e. it should take a finite amount of time.
7. It should be correct i.e. it must produce the correct output values for all legal input instances of the
problem.
8. It should be general i.e. it should be applicable to all problems of a similar form.
9. It should be possible to have its multiple views i.e. same algorithm may be represented in different
ways.
10. Several algorithms for solving the same problem may exist but with different properties. This is
known as multiple availability of an algorithm.

ANALYSIS OF ALGORITHMS
The efficiency of an algorithm can be decided by measuring the performance of an algorithm. We call this
as the performance analysis of the algorithm. The execution of an algorithm needs various computing
resources to perform a task. The performance of an algorithm can be measured by computing two factors
as follows:
1. Amount of time required by an algorithm to execute (time complexity).
2. Amount of storage required by an algorithm (space complexity).
Analysis of algorithms may be done on the basis of following parameters:
1. Measuring space and time complexities.
2. Measuring the input size.
3. Measuring the running time.
4. Computing best case, worst case and average case efficiencies of the algorithm so developed.
5. Computing the order of growth of algorithms.
The algorithm that needs less space and less time is more efficient than the other ones. The complexity tree
is shown in figure 1.2.
Performance Analysis
The performance of a program is the amount of computer memory and time needed to run a program. We
use two approaches to determine the performance of a program. One is analytical, and the other
experimental. In performance analysis we use analytical methods, while in performance measurement we
conduct experiments.
Time Complexity:
The time needed by an algorithm expressed as a function of the size of a problem is called the time
complexity of the algorithm. The time complexity of a program is the amount of computer time it needs to
run to completion. The limiting behavior of the complexity as size increases is called the asymptotic time
complexity. It is the asymptotic complexity of an algorithm, which ultimately determines the size of
problems that can be solved by the algorithm.
The Running time of a program
When solving a problem, we are faced with a choice among algorithms. The basis for this can be any one of
the following:
i. We would like an algorithm that is easy to understand code and debug.
ii. We would like an algorithm that makes efficient use of the computer’s resources,
especially, one that runs as fast as possible
Measuring the running time of a program
The running time of a program depends on factors such as:
1. The input to the program.
2. The quality of code generated by the compiler used to create the object program.
3. The nature and speed of the instructions on the machine used to execute the program,
4. The time complexity of the algorithm underlying the program.

Space Complexity:
The space complexity of a program is the amount of memory it needs to run to completion. The space need
by a program has the following components:
Instruction space: Instruction space is the space needed to store the compiled version of the program
instructions.
Data space: Data space is the space needed to store all constant and variable values. Data space has two
components:
 Space needed by constants and simple variables in program.
 Space needed by dynamically allocated objects such as arrays and class instances.
Environment stack space: The environment stack is used to save information needed to resume execution of
partially completed functions.
Instruction Space: The amount of instructions space that is needed depends on factors such as:
 The compiler used to complete the program into machine code.
 The compiler options in effect at the time of compilation
 The target computer.
The space requirement s(p) of any algorithm p may therefore be written as,
S(P) = c+ Sp(Instance characteristics)
Where ‘c’ is a constant.
Example 2:
Algorithm sum(a,n)
{
s=0.0;
for I=1 to n
do s= s+a[I];
return s;
}
 The problem instances for this algorithm are characterized by n,the number of elements to be summed.
The space needed d by ‘n’ is one word, since it is of type integer.
 The space needed by ‘a’a is the space needed by variables of type array of floating point numbers.
 This is atleast ‘n’ words, since ‘a’ must be large enough to hold the ‘n’ elements to be summed.
 So,we obtain Ssum(n)>=(n+s) [ n for a[],one each for n,I a&s]

Complexity of Algorithms
The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space
requirement of the algorithm in terms of the size ‘n’ of the input data. Mostly, the storage space required by
an algorithm is simply a multiple of the data size ‘n’. Complexity shall refer to the running time of the
algorithm.
The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of the input data
but also on the particular data. The complexity function f(n) for certain cases are:
1. Best Case : The minimum possible value of f(n) is called the best case.
2. Average Case : The expected value of f(n).
3. Worst Case : The maximum value of f(n) for any key possible input
Asymptotic Notations:
The following notations are commonly use notations in performance
analysis and used to characterize the complexity of an algorithm:
1. Big–OH (O)
2. Big–OMEGA (Ω),
3. Big–THETA (Θ) and
4. Little–OH (o)
Big–OH O (Upper Bound)
f(n) = O(g(n)), (pronounced order of or big oh), says that the growth rate of f(n) is
less than or equal (<) that of g(n).
Big–OMEGA Ω (Lower Bound)
f(n) = Ω (g(n)) (pronounced omega), says that the growth rate of f(n) is greater
than or equal to (>) that of g(n).

Big–THETA Θ (Same order)

f(n) = Θ (g(n)) (pronounced theta), says that the growth rate of f(n)
equals (=) the growth rate of g(n) [if f(n) = O(g(n)) and T(n) = Θ (g(n)].
Array
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of
the same type together. This makes it easier to calculate the position of each element by simply adding an
offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the
name of the array).

Creating a Array
Array in Python can be created by importing array module. array(data_type, value_list) is used to create an
array with data type and value list specified in its arguments.
# Python program to demonstrate
# Creation of Array
# importing "array" for array creations
import array as arr
# creating an array with integer type
a = [Link]('i', [1, 2, 3])
# printing original array
print ("The new created array is : ", end =" ")
for i in range (0, 3):
print (a[i], end =" ")
print()
# creating an array with float type
b = [Link]('d', [2.5, 3.2, 3.3])
# printing original array
print ("The new created array is : ", end =" ")
for i in range (0, 3):
print (b[i], end =" ")

Output :
The new created array is : 1 2 3
The new created array is : 2.5 3.2 3.3
Some of the data types are mentioned below which will help in creating an array of different data types.
Adding Elements to a Array
Elements can be added to the Array by using built-in insert() function. Insert is used to insert one or more
data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or
any given index of array. append() is also used to add the value mentioned in its arguments at the end of the
array.

# Python program to demonstrate

# Adding Elements to a Array
# importing "array" for array creations
import array as arr
# array with int type
a = [Link]('i', [1, 2, 3])
print ("Array before insertion : ", end =" ")
for i in range (0, 3):
print (a[i], end =" ")
print()
# inserting array using
# insert() function
[Link](1, 4)
print ("Array after insertion : ", end =" ")
for i in (a):
print (i, end =" ")
print()
# array with float type
b = [Link]('d', [2.5, 3.2, 3.3])
print ("Array before insertion : ", end =" ")
for i in range (0, 3):
print (b[i], end =" ")
print()
# adding an element using append()
[Link](4.4) //end of the array
print ("Array after insertion : ", end =" ")
for i in (b):
print (i, end =" ")
print()
Output :
Array before insertion : 1 2 3
Array after insertion : 1 4 2 3
Array before insertion : 2.5 3.2 3.3
Array after insertion : 2.5 3.2 3.3 4.4

Accessing elements from the Array

In order to access the array items refer to the index number. Use the index operator [ ] to access an item in a
array. The index must be an integer.
# Python program to demonstrate
# accessing of element from list
# importing array module
import array as arr
# array with int type
a = [Link]('i', [1, 2, 3, 4, 5, 6])
# accessing element of array
print("Access element is: ", a[0])
# accessing element of array
print("Access element is: ", a[3])
# array with float type
b = [Link]('d', [2.5, 3.2, 3.3])
# accessing element of array
print("Access element is: ", b[1])
# accessing element of array
print("Access element is: ", b[2])
Output :
Access element is: 1
Access element is: 4
Access element is: 3.2
Access element is: 3.3

Removing Elements from the Array

Elements can be removed from the array by using built-in remove() function but an Error arises if element
doesn’t exist in the set. Remove() method only removes one element at a time, to remove range of elements,
iterator is used. pop() function can also be used to remove and return an element from the array, but by
default it removes only the last element of the array, to remove element from a specific position of the array,
index of the element is passed as an argument to the pop() method. Note – Remove method in List will only
remove the first occurrence of the searched element.
# Python program to demonstrate
# Removal of elements in a Array
# importing "array" for array operations
import array
# initializing array with array values
# initializes array with signed integers
arr = [Link]('i', [1, 2, 3, 1, 5])
# printing original array
print ("The new created array is : ", end ="")
for i in range (0, 5):
print (arr[i], end =" ")
print ("\r")
# using pop() to remove element at 2nd position
print ("The popped element is : ", end ="")
print ([Link](2))
# printing array after popping
print ("The array after popping is : ", end ="")
for i in range (0, 4):
print (arr[i], end =" ")
print("\r")
# using remove() to remove 1st occurrence of 1
[Link](1)
# printing array after removing
print ("The array after removing is : ", end ="")
for i in range (0, 3):
print (arr[i], end =" ")
Output:
The new created array is : 1 2 3 1 5
The popped element is : 3
The array after popping is : 1 2 1 5
The array after removing is : 2 1 5
Searching element in a Array
In order to search an element in the array we use a python in-built index() method. This function returns the
index of the first occurrence of value mentioned in arguments.

# Python code to demonstrate

# searching an element in array
# importing array module
import array
# initializing array with array values
# initializes array with signed integers
arr = [Link]('i', [1, 2, 3, 1, 2, 5])
# printing original array
print ("The new created array is : ", end ="")
for i in range (0, 6):
print (arr[i], end =" ")
print ("\r")
# using index() to print index of 1st occurrenece of 2
print ("The index of 1st occurrence of 2 is : ", end ="")
print ([Link](2))
# using index() to print index of 1st occurrenece of 1
print ("The index of 1st occurrence of 1 is : ", end ="")
print ([Link](1))
Output:
The new created array is : 1 2 3 1 2 5
The index of 1st occurrence of 2 is : 1
The index of 1st occurrence of 1 is : 0

Stack
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It
is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of
plates, etc.
A real-world stack allows operations at one end only. For example, we can place or remove a
card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations
at one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the
element that is placed (inserted or added) last, is accessed first. In stack terminology,
the insertion operation is called PUSH operation and the removal operation is called POP operation.

Stack Representation
The following diagram depicts a stack and its operations –
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going
to implement stack using arrays, which makes it a fixed size stack implementation-
Static implementation.

Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart
from these basic stuffs, a stack is used for the following two primary operations −
 push() − Pushing (storing) an element on the stack.
 pop() − Removing (accessing) an element from the stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose,
the following functionality is added to stacks −
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 isEmpty() − check if stack is empty.
Push Operation
 The process of putting a new data element onto stack is known as a
Push Operation. Push
 operation involves a series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
  Step 3 − If the stack is not full, increments top to point next empty
space.
 Step 4 − Adds data element to the stack location, where top is
pointing.
 Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −
def push(stack, data, max_size):
if len(stack) == max_size:
return None
[Link](data)
Example
stack = []
max_size = 5

push(stack, 10, max_size)

push(stack, 20, max_size)
print(stack) # Output: [10, 20]

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 linkedlist
implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.
Algorithm for Pop Operation
A simple algorithm for Pop operation can be derived as follows –
def pop(stack):
# check if stack is empty
if len(stack) == 0:
return None

# get top element

data = stack[-1]

# remove top element

[Link]()
return data
Example
stack = [10, 20, 30]
value = pop(stack)
print("Popped:", value) # Output: Popped: 30
print(stack) # Output: [10, 20]
Stack code
stack = []
MAXSIZE = 5

def isEmpty():
return len(stack) == 0

def isFull():
return len(stack) == MAXSIZE

def push():
if isFull():
print("Stack is full!")
else:
data = input("Enter element to push: ")
[Link](data)
print("Pushed:", data)

def pop():
if isEmpty():
print("Stack is empty!")
else:
data = [Link]()
print("Popped:", data)
def peek():
if isEmpty():
print("Stack is empty!")
else:
print("Top element:", stack[-1])

def display():
if isEmpty():
print("Stack is empty!")
else:
print("Stack elements:", stack)

# ---------- MENU ----------

while True:
print("\n--- STACK MENU ---")
print("1. Push")
print("2. Pop")
print("3. Peek")
print("4. Display")
print("5. Exit")

choice = input("Enter your choice: ")

if choice == '1':
push()
elif choice == '2':
pop()
elif choice == '3':
peek()
elif choice == '4':
display()
elif choice == '5':
print("Exiting program.")
break
else:
print("Invalid choice! Try again.")

Queue
Queue is a linear structure which follows a particular order in which the operations are
performed. The order is First In First Out (FIFO). A good example of queue is any queue of
consumers for a resource where the consumer that came first is served first.
The difference between stacks and queues is in removing. In a stack we remove the item the
most recently added; in a queue, we remove the item the least recently added.
Operations on Queue:
Mainly the following basic operations are performed on queue:
Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow
condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which
they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Queue Representation
As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional
array.

Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic operations
associated with queues −
 enqueue() − add (store) an item to the queue.
 dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient.
These are −
 peek() − Gets the element at the front of the queue without removing it.
 isfull() − Checks if the queue is full.
 isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing
(or storing) data in the queue we take help of rear pointer.
Let's first learn about supportive functions of a queue −
peek()
This function helps to see the data at the front of the queue. The algorithm of peek() function
is as follows –
Algorithm
def peek(queue, front):
# return the front element of the queue
return queue[front]
Example
queue = [10, 20, 30]
front = 0
print(peek(queue, front))
isfull()
As we are using single dimension array to implement queue, we just check for the rear
pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the
queue in a circular linked-list, the algorithm will differ. Algorithm of isfull() function –
Algorithm
def isFull(rear, MAXSIZE):
if rear == MAXSIZE:
return True
else:
return False
Example
def isFull(rear, MAXSIZE):
return rear == MAXSIZE – 1
isempty()
Algorithm of isempty() function −
Algorithm
def isEmpty(front, rear, MIN):
if front < MIN or front > rear:
return True
else:
return False
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence
empty.
Example:
def isEmpty(front, rear):
return front < 0 or front > rear

Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are
comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if the queue is full.
 Step 2 − If the queue is full, produce overflow error and exit.
  Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 Step 4 − Add data element to the queue location, where the rear is pointing.
 Step 5 − return success.
Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is
pointing and remove the data after access. The following steps are taken to perform dequeue
operation −
 Step 1 − Check if the queue is empty.
 Step 2 − If the queue is empty, produce underflow error and exit.
 Step 3 − If the queue is not empty, access the data where front is pointing.
 Step 4 − Increment front pointer to point to the next available data element.
 Step 5 − Return success.
Queue Code
MAXSIZE = 5
queue = [None] * MAXSIZE
front = -1
rear = -1

def isEmpty():
return front < 0 or front > rear

def isFull():
return rear == MAXSIZE - 1

def enqueue():
global rear, front
if isFull():
print("Queue is full!")
else:
data = input("Enter element to enqueue: ")
if front == -1:
front = 0
rear += 1
queue[rear] = data
print("Enqueued:", data)

def dequeue():
global front, rear
if isEmpty():
print("Queue is empty!")
else:
data = queue[front]
front += 1
print("Dequeued:", data)

def peek():
if isEmpty():
print("Queue is empty!")
else:
 print("Front element:", queue[front])

def display():
if isEmpty():
print("Queue is empty!")
else:
print("Queue elements:", queue[front:rear + 1])

# ------------------ MENU ------------------

while True:
print("\n--- QUEUE MENU ---")
print("1. Enqueue")
print("2. Dequeue")
print("3. Peek")
print("4. Display")
print("5. Exit")

choice = input("Enter your choice: ")

if choice == '1':
enqueue()
elif choice == '2':
dequeue()
elif choice == '3':
peek()
elif choice == '4':
display()
elif choice == '5':
print("Exiting program.")
break
else:
print("Invalid choice! Try again.")

Sparse Matrices
A sparse matrix is a matrix in which most of the elements are zero.
Example:
007
000

Only 2 non-zero values ⇒ sparse matrix.

400

Why Sparse Matrices are Used?

 To save memory
 To speed up computations
 Useful when the matrix is large but has only a few non-zero values
Examples:
 Graph adjacency matrices
 Machine learning data
 Image processing

Sparse Matrix Code in Python

 In computer programming, a matrix can be defined with a 2-dimensional array. Any array with 'm'
columns and 'n' rows represent a m X n matrix. There may be a situation in which a matrix contains
more number of ZERO values than NON-ZERO values. Such matrix is known as sparse matrix.

Array Representation
In this representation, we consider only non-zero values along with their row and column index values. In this
representation, the 0th row stores the total number of rows, total number of columns and the total number of
non-zero values in the sparse matrix. For example, consider a matrix of size 5 X 6 containing 6 number of non-
zero values. This matrix can be represented as shown in the image.

# Read number of rows and columns

rows = int(input("Enter number of rows: "))
cols = int(input("Enter number of columns: "))

# Read the matrix

print("Enter the matrix elements:")
matrix = []
for i in range(rows):
row = list(map(int, input().split()))
[Link](row)

# Convert to sparse matrix (triplet form)

sparse = []
for i in range(rows):
for j in range(cols):
if matrix[i][j] != 0:
 [Link]([i, j, matrix[i][j]])

# Print original matrix

print("\nOriginal Matrix:")
for r in matrix:
print(r)

# Print sparse matrix

print("\nSparse Matrix (row, column, value):")
for s in sparse:
print(s)

Arithmetic Expression; Polish Notation

Let Q be an arithmetic expression involving constants and operations, here we discuss an algorithm which
finds value of Q by using reverse polish (postfix) notation. The binary operation in Q may have different
level of precedence, specifically, we assume the following three level of precedence for the usual five binary
operation.
Highest - Exponentiation ( ^ )
Next highest - Multiplication (*) and Division (/)
Lowest - Addition (+) and subtraction (-)

Evaluate the following parenthesis-free arithmetic expression.

We assume that Q contains no unary operation(i++).we also assume that in any parenthesis –free expression.
the operations on the same level are performed from left to right.
2 ^ 3 + 5 * 2 ^ 2 – 12 / 6
Evaluate the exponentiation to obtain
8 + 5 * 4 – 12 /6
Evaluate Multiplication and Division
8 + 20 – 2
Evaluate Addition and Subtraction
26
Polish Notation
For most common arithmetic operations, the operator symbol is placed between its operand, this is called
infix notation.
Example A+B ,C-D, E*F
• Expression in which operator is placed before its operands is known as prefix notation.
Example: +AB, -CD, *EF , /GH
• Expression in which Operator symbol is placed after its two operand is known as postfix notation.
Example: AB+, CD-, EF*, GC/
Postfix evaluation (algorithm)
1. Read tokens left → right.
2. If token is operand: push it on stack.
3. If token is operator: pop required number of operands (for binary: pop op2, then op1), compute op1
operator op2, push result.
4. At the end, stack has single result.

function evaluate_postfix(expr):
 stack = empty stack

for token in expr:

if token is operand:
[Link](token)
else: # operator
b = [Link]()
a = [Link]()
result = apply_operator(a, b, token)
[Link](result)

return [Link]()
Example: Evaluate 2 3 4 * + 5 -
 push 2
 push 3
 push 4
 *: pop 4,3 => 3*4=12, push 12
 +: pop 12,2 => 2+12=14, push 14
 push 5
 -: pop 5,14 => 14-5=9 → result = 9
Prefix evaluation (algorithm)
1. Read tokens from right → left.
2. If token is operand, push it on the stack.
3. If token is operator:
o Pop required operands (for binary: pop op1 then op2).
o Compute operator op1 op2.
o Push the result back.
4. At the end, the stack contains a single result.
function evaluate_prefix(expr):
stack = empty stack

# scan from right → left

for token in reverse(expr):

if token is operand:
[Link](token)
else: # operator
a = [Link]()
b = [Link]()
result = apply_operator(token, a, b)
[Link](result)
return [Link]()
Example: Evaluate + 9 * 2 3
Scan right → left
• push 3
• push 2
• * : pop 2,3 → 2*3 = 6 → push 6
• push 9
• + : pop 9,6 → 9+6 = 15 → push 15

Final result = 15
Linked List
A linked list is a non sequential collection of data items. For every data item in the linked list, there is an
associated pointer that gives the memory location of the next data item in the linked list.
The data items in the linked list are not in a consecutive memory locations. But they may be anywhere in
memory. However, accessing of these items is easier as each data item contained within itself the address of
the next data item.

Explain advantages of linked list over array(2m)

• list of advantages :
• Linked List is Dynamic data Structure .
• Linked List can grow and shrink during run time.
• Insertion and Deletion Operations are Easier
• Efficient Memory Utilization ,i.e no need to pre-allocate memory

Components of a linked list

A linked list is a non sequential collection of data items called nodes. Each node in a linked list basically
contains 2 fields namely, an information field called INFO and a pointer field denoted by NEXT. The INFO
field contains the actual value to be stored and processed and the NEXT field contains the address of the next
data item. The address used to access a particular node is known as a pointer.