What is Data Structure:

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. There are different basic and advanced types of data structures that are used in almost
every program or software system that has been developed. So we must have good knowledge of data
structures.

Data structures are an integral part of computers used for the arrangement of data in memory. They are
essential and responsible for organizing, processing, accessing, and storing data efficiently. But this is
not all. Various types of data structures have their own characteristics, features, applications,
advantages, and disadvantages. So how do you identify a data structure that is suitable for a particular
task? What is meant by the term ‘Data Structure’? How many types of data structures are there and
what are they used for?

How Data Structure varies from Data Type:

We already have learned about data structure. Many times, what happens is that people get confused
between data type and data structure. So let’s see a few differences between data type and data
structure to make it clear.
Classification of Data Structure:

Data structure has many different uses in our daily life. There are many different data structures that are
used to solve different mathematical and logical problems. By using data structure, one can organize
and process a very large amount of data in a relatively short period. Let’s look at different data
structures that are used in different situations.
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 of non-linear data structures are trees and graphs.

Need Of Data structure :

The structure of the data and the synthesis of the algorithm are relative to each other. Data
presentation must be easy to understand so the developer, as well as the user, can make an efficient
implementation of the operation.

Data structures provide an easy way of organizing, retrieving, managing, and storing data.

Here is a list of the needs for data.

Data structure modification is easy.

It requires less time.

Save storage memory space.

Data representation is easy.

Easy access to the large database.

ADT:

Now there might be a situation when we need operations for our user-defined data type which have to
be defined. These operations can be defined only as and when we require them. So, in order to simplify
the process of solving problems, we can create data structures along with their operations, and such
data structures that are not in-built are known as Abstract Data Type (ADT).

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and
a set of operations. The definition of ADT only mentions what operations are to be performed but not
how these operations will be implemented. It does not specify how data will be organized in memory
and what algorithms will be used for implementing the operations. It is called “abstract” because it gives
an implementation-independent view.

The process of providing only the essentials and hiding the details is known as abstraction.

The user of data type does not need to know how that data type is implemented, for example, we have
been using Primitive values like int, float, char data types only with the knowledge that these data type
can operate and be performed on without any idea of how they are implemented.

So a user only needs to know what a data type can do, but not how it will be implemented. Think of ADT
as a black box which hides the inner structure and design of the data type. Now we’ll define three ADTs
namely List ADT, Stack ADT, Queue ADT.
1. List ADT:

The data is generally stored in key sequence in a list which has a head structure consisting of
count, pointers and address of compare function needed to compare the data in the list.
The data node contains the pointer to a data structure and a self-referential pointer which
points to the next node in the list.
The List ADT Functions is given below:
get() – Return an element from the list at any given position.
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.

2. Queue ADT:

The queue abstract data type (ADT) follows the basic design of the stack abstract data type.
Each node contains a void pointer to the data and the link pointer to the next element in the
queue. The program’s responsibility is to allocate memory for storing the data.
enqueue() – Insert an element at the end of the queue.
dequeue() – Remove and return the first element of the queue, if the queue is not empty.
peek() – Return the element of the queue without removing it, if the queue is not empty.
size() – Return the number of elements in the queue.
isEmpty() – Return true if the queue is empty, otherwise return false.
isFull() – Return true if the queue is full, otherwise return false.
Features of ADT:
Abstract data types (ADTs) are a way of encapsulating data and operations on that data into a
single unit. Some of the key features of ADTs include:

Abstraction: The user does not need to know the implementation of the data structure only
essentials are provided.
Better Conceptualization: ADT gives us a better conceptualization of the real world.
Robust: The program is robust and has the ability to catch errors.
Encapsulation: ADTs hide the internal details of the data and provide a public interface for users
to interact with the data. This allows for easier maintenance and modification of the data
structure.
Data Abstraction: ADTs provide a level of abstraction from the implementation details of the
data. Users only need to know the operations that can be performed on the data, not how those
operations are implemented.
Data Structure Independence: ADTs can be implemented using different data structures, such
as arrays or linked lists, without affecting the functionality of the ADT.
Information Hiding: ADTs can protect the integrity of the data by allowing access only to
authorized users and operations. This helps prevent errors and misuse of the data.
Modularity: ADTs can be combined with other ADTs to form larger, more complex data
structures. This allows for greater flexibility and modularity in programming.
Overall, ADTs provide a powerful tool for organizing and manipulating data in a structured and
efficient manner.

Abstract data types (ADTs) have several advantages and disadvantages that should be
considered when deciding to use them in software development. Here are some of the main
advantages and disadvantages of using ADTs:

Advantages of ADT:
Encapsulation: ADTs provide a way to encapsulate data and operations into a single unit,
making it easier to manage and modify the data structure.
Abstraction: ADTs allow users to work with data structures without having to know the
implementation details, which can simplify programming and reduce errors.
Data Structure Independence: ADTs can be implemented using different data structures, which
can make it easier to adapt to changing needs and requirements.
Information Hiding: ADTs can protect the integrity of data by controlling access and preventing
unauthorized modifications.
 Modularity: ADTs can be combined with other ADTs to form more complex data structures,
which can increase flexibility and modularity in programming.
Disadvantages of ADT:
Overhead: Implementing ADTs can add overhead in terms of memory and processing, which can
affect performance.
Complexity: ADTs can be complex to implement, especially for large and complex data
structures.
Learning Curve: Using ADTs requires knowledge of their implementation and usage, which can
take time and effort to learn.
Limited Flexibility: Some ADTs may be limited in their functionality or may not be suitable for all
types of data structures.
Cost: Implementing ADTs may require additional resources and investment, which can increase
the cost of development.
Overall, the advantages of ADTs often outweigh the disadvantages, and they are widely used in
software development to manage and manipulate data in a structured and efficient way.
However, it is important to consider the specific needs and requirements of a project when
deciding whether to use ADTs.

From these definitions, we can clearly see that the definitions do not specify how these ADTs
will be represented and how the operations will be carried out. There can be different ways to
implement an ADT, for example, the List ADT can be implemented using arrays, or singly linked
list or doubly linked list. Similarly, stack ADT and Queue ADT can be implemented using arrays or
linked lists.

This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to
contribute, you can also write an article using [Link] or mail your article to
review-team@[Link]. See your article appearing on the GeeksforGeeks main page
and help other Geeks.

Defining the List ADT

What basic operations do we want our lists to support? Our common intuition about lists tells us
that a list should be able to grow and shrink in size as we insert and remove elements. We
should be able to insert and remove elements from anywhere in the list. We should be able to
gain access to any element’s value, either to read it or to change it. Finally, we should be able to
know the size of the list, and to iterate through the elements in the list – i.e., the list should be a
Collection.

Now we can define the ADT for a list object in terms of a set of operations on that object. We
will use an interface to formally define the list ADT. List defines the member functions that any
list implementation inheriting from it must support, along with their parameters and return
types.
True to the notion of an ADT, an interface does not specify how operations are implemented.
Two complete implementations are presented later (array-based lists and linked lists), both of
which use the same list ADT to define their operations. But they are considerably different in
approaches and in their space/time tradeoffs.

The code below presents our list ADT. The comments given with each member function describe
what it is intended to do. However, an explanation of the basic design should help make this
clearer. There are four main operations we want to support:

get(i) to read the value of an element at the given position i

set(i,x) to set the value at position i to value x

add(i,x) to add (insert) an element x, at position i, thus increasing the size of the list

remove(i) to remove the element at position i, thus decreasing the size of the list.
Linked list Data Structure:
A linked list is a linear data structure that includes a series of connected nodes. Here, each node
stores the data and the address of the next node. For example,

You have to start somewhere, so we give the address of the first node a special name called
HEAD. Also, the last node in the linked list can be identified because its next portion points to
NULL.
 Linked lists can be of multiple types: singly, doubly, and circular linked list. In this article, we will
focus on the singly linked list.

Linked List Operations: Traverse, Insert and Delete

There are various linked list operations that allow us to perform different actions on linked lists. For

example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

 Traversal - access each element of the linked list

 Insertion - adds a new element to the linked list

 Deletion - removes the existing elements

 Search - find a node in the linked list

 Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

 head points to the first node of the linked list

 next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of

the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node

structure as below:
Traverse a Linked List
Displaying the contents of a linked list is very simple. We keep moving the temp node to the
next one and display its contents.

When temp is NULL, we know that we have reached the end of the linked list so we get out of
the while loop.

Insert Elements to a Linked List

You can add elements to either the beginning, middle or end of the linked list.
 1. Insert at the beginning

 Allocate memory for new node

 Store data

 Change next of new node to point to head

 Change head to point to recently created node

2. Insert at the End

 Allocate memory for new node

 Store data

 Traverse to last node

 Change next of last node to recently created node

3. Insert at the Middle

 Allocate memory and store data for new node

 Traverse to node just before the required position of new node

 Change next pointers to include new node in between

Delete from a Linked List

You can delete either from the beginning, end or from a particular position.

1. Delete from beginning

 Point head to the second node

2. Delete from end

 Traverse to second last element

 Change its next pointer to null

3. Delete from middle

 Traverse to element before the element to be deleted

 Change next pointers to exclude the node from the chain

Search an Element on a Linked List

You can search an element on a linked list using a loop using the following steps. We are finding item on

a linked list.
 Make head as the current node.

 Run a loop until the current node is NULL because the last element points to NULL.

 In each iteration, check if the key of the node is equal to item. If it the key matches the item,

return true otherwise return false.

Sort Elements of a Linked List

We will use a simple sorting algorithm, Bubble Sort, to sort the elements of a linked list in ascending

order below.
1. Make the head as the current node and create another node index for later use.

2. If head is null, return.

3. Else, run a loop till the last node (i.e. NULL).

4. In each iteration, follow the following step 5-6.

5. Store the next node of current in index.

6. Check if the data of the current node is greater than the next node. If it is greater,
swap current and index.
Program python:

# Linked list operations in Python

# Create a node
class Node:
 def __init__(self, data):
[Link] = data
[Link] = None

class LinkedList:

def __init__(self):
[Link] = None

# Insert at the beginning

def insertAtBeginning(self, new_data):
new_node = Node(new_data)

new_node.next = [Link]
[Link] = new_node

# Insert after a node

def insertAfter(self, prev_node, new_data):

if prev_node is None:
print("The given previous node must inLinkedList.")
return

new_node = Node(new_data)
new_node.next = prev_node.next
prev_node.next = new_node

# Insert at the end

def insertAtEnd(self, new_data):
new_node = Node(new_data)

if [Link] is None:
[Link] = new_node
return

last = [Link]
while ([Link]):
last = [Link]

[Link] = new_node

# Deleting a node
def deleteNode(self, position):

if [Link] is None:
return

temp = [Link]

if position == 0:
[Link] = [Link]
temp = None
return

# Find the key to be deleted

for i in range(position - 1):
temp = [Link]
if temp is None:
break

# If the key is not present

if temp is None:
return

if [Link] is None:
return

next = [Link]

[Link] = None

[Link] = next

# Search an element
def search(self, key):

current = [Link]

while current is not None:

if [Link] == key:
return True

current = [Link]

return False
 # Sort the linked list
def sortLinkedList(self, head):
current = head
index = Node(None)

if head is None:
return
else:
while current is not None:
# index points to the node next to current
index = [Link]

while index is not None:

if [Link] > [Link]:
[Link], [Link] = [Link],
[Link]

index = [Link]
current = [Link]

# Print the linked list

def printList(self):
temp = [Link]
while (temp):
print(str([Link]) + " ", end="")
temp = [Link]

if __name__ == '__main__':

llist = LinkedList()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link]([Link], 5)

print('linked list:')
[Link]()

print("\nAfter deleting an element:")

[Link](3)
[Link]()

print()
item_to_find = 3
if [Link](item_to_find):
print(str(item_to_find) + " is found")
else:
print(str(item_to_find) + " is not found")

[Link]([Link])
print("Sorted List: ")
[Link]()

Types of Linked List - Singly linked, doubly linked and circular

There are three common types of Linked List.

Singly Linked List

Doubly Linked List
Circular Linked List
Singly Linked List
It is the most common. Each node has data and a pointer to the next node.

Doubly Linked List

We add a pointer to the previous node in a doubly-linked list. Thus, we can go in either
direction: forward or backward.

Circular Linked List

A circular linked list is a variation of a linked list in which the last element is linked to the first
element. This forms a circular loop.
Applications of the Linked list:
Different applications of linked lists are as follows:

Linked lists are used to implement stacks, queues, graphs, etc.

Linked lists are used to perform arithmetic operations on long integers.
It is used for the representation of sparse matrices.
It is used in the linked allocation of files.
It helps in memory management.
It is used in the representation of Polynomial Manipulation where each polynomial term
represents a node in the linked list.
Linked lists are used to display image containers. Users can visit past, current, and next images.
They are used to store the history of the visited page.
They are used to perform undo operations.
Linked are used in software development where they indicate the correct syntax of a tag.
Linked lists are used to display social media feeds.
Real-Life Applications of a Linked list:
A linked list is used in Round-Robin scheduling to keep track of the turn in multiplayer games.
It is used in image viewer. The previous and next images are linked, and hence can be accessed
by the previous and next buttons.
In a music playlist, songs are linked to the previous and next songs.

Application of Linked list in Polynomial Equations:

Polynomial manipulations are one of the most important applications of linked lists. Polynomials
are an important part of mathematics not inherently supported as a data type by most
languages. A polynomial is a collection of different terms, each comprising coefficients, and
exponents. It can be represented using a linked list. This representation makes polynomial
manipulation efficient.
While representing a polynomial using a linked list, each polynomial term represents a node in
the linked list. To get better efficiency in processing, we assume that the term of every
polynomial is stored within the linked list in the order of decreasing exponents. Also, no two
terms have the same exponent, and no term has a zero coefficient and without coefficients. The
coefficient takes a value of 1.
Each node of a linked list representing polynomial constitute three parts:
 The first part contains the value of the coefficient of the term.
The second part contains the value of the exponent.
The third part, LINK points to the next term (next node).
The structure of a node of a linked list that represents a polynomial is shown below:

Consider a polynomial P(x) = 7x2 + 15x3 - 2 x2 + 9. Here 7, 15, -2, and 9 are
the coefficients, and 4,3,2,0 are the exponents of the terms in the
polynomial. On representing this polynomial using a linked list, we have

Observe that the number of nodes equals the number of terms in the
polynomial. So we have 4 nodes. Moreover, the terms are stored to decrease
exponents in the linked list. Such representation of polynomial using linked
lists makes the operations like subtraction, addition, multiplication, etc., on
polynomial very easy.
Addition of Polynomials:
To add two polynomials, we traverse the list P and Q. We take corresponding terms of the list P
and Q and compare their exponents. If the two exponents are equal, the coefficients are added
to create a new coefficient. If the new coefficient is equal to 0, then the term is dropped, and if
it is not zero, it is inserted at the end of the new linked list containing the resulting polynomial. If
one of the exponents is larger than the other, the corresponding term is immediately placed
into the new linked list, and the term with the smaller exponent is held to be compared with the
next term from the other list. If one list ends before the other, the rest of the terms of the
longer list is inserted at the end of the new linked list containing the resulting polynomial.

Let us consider an example an example to show how the addition of two

polynomials is performed,

P(x) = 3x4 + 2x3 - 4 x2 + 7

Q (x) = 5x3 + 4 x2 - 5

These polynomials are represented using a linked list in order of decreasing

exponents as follows:
To generate a new linked list for the resulting polynomials that is formed on
the addition of given polynomials P(x) and Q(x), we perform the following
steps,

1. Traverse the two lists P and Q and examine all the nodes.
2. We compare the exponents of the corresponding terms of two
polynomials. The first term of polynomials P and Q contain exponents 4
and 3, respectively. Since the exponent of the first term of the
polynomial P is greater than the other polynomial Q, the term having a
larger exponent is inserted into the new list. The new list initially looks
as shown below:
We then compare the exponent of the next term of the list P with the
exponents of the present term of list Q. Since the two exponents are equal,
so their coefficients are added and appended to the new list as follows:

Then we move to the next term of P and Q lists and compare their exponents.
Since exponents of both these terms are equal and after addition of their
coefficients, we get 0, so the term is dropped, and no node is appended to
the new list after this,

Moving to the next term of the two lists, P and Q, we find that the
corresponding terms have the same exponents equal to 0. We add their
coefficients and append them to the new list for the resulting polynomial as
shown below:

Polynomial of Multiple Variables

We can represent a polynomial with more than one variable, i.e., it can be
two or three variables. Below is a node structure suitable for representing a
polynomial with three variables X, Y, Z using a singly linked list.
 Consider a polynomial P(x, y, z) = 10x 2y2z + 17 x2y z2 - 5 xy2 z+ 21y4z2 + 7.
On represnting this polynomial using linked list are:

Terms in such a polynomial are ordered accordingly to the decreasing degree

in x. Those with the same degree in x are ordered according to decreasing
degree in y. Those with the same degree in x and y are ordered according to
decreasing degrees in z.
3. Stack ADT:

Stack is a liner ADT, with restrictions in inserting and deleting elements from the same end. It’s
like making a pile of plates in which the first plate will be the last plate to be taken. It works on
the principle of LIFO (last-in, last-out). It stores only one type of data
The entering and retrieving of data is also called push and pop operation in a stack. There are
different operations possible in a stack like reversing a stack using recursion, Sorting, Deleting
the middle element of a stack, etc.
In Stack ADT Implementation instead of data being stored in each node, the pointer to data is
stored.
The program allocates memory for the data and address is passed to the stack ADT.
The head node and the data nodes are encapsulated in the ADT. The calling function can only
see the pointer to the stack.
The stack head structure also contains a pointer to top and count of number of entries currently
in stack.
push() – Insert an element at one end of the stack called top.
pop() – Remove and return the element at the top of the stack, if it is not empty.
peek() – Return the element at the top of the stack without removing it, if the stack is not
empty.
size() – Return the number of elements in the stack.
isEmpty() – Return true if the stack is empty, otherwise return false.
isFull() – Return true if the stack is full, otherwise return false.
Insertion: push()
push() is an operation that inserts elements into the stack. The following is an algorithm that
describes the push() operation in a simpler way.
Algorithm
1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
3 − If the stack is not full, increments top to point next empty space.
4 − Adds data element to the stack location, where top is pointing.
5 − Returns success.
pop() is a data manipulation operation which removes elements from the stack. The following
pseudo code describes the pop() operation in a simpler way.
Algorithm
1 − Checks if the stack is empty.
2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
 4 − Decreases the value of top by 1.
5 − Returns success.
class Stack:
def __init__(self):
[Link] = []
def __str__(self):
return str([Link])
def push(self, data):
if data not in [Link]:
[Link](data)
return True
else:
return False
def remove(self):
if len([Link]) <= 0:
return ("No element in the Stack")
else:
return [Link]()
stk = Stack()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)
print("Stack Elements:")
print(stk)
print("----Deletion operation in stack----")
p = [Link]()
print("The popped element is: " + str(p))
print("Updated Stack:")
print(stk)

peek()
The peek() is an operation retrieves the topmost element within the stack, without
deleting it. This operation is used to check the status of the stack with the help of the top
pointer.
Algorithm
1. START
2. return the element at the top of the stack
3. END

class Stack:
def __init__(self):
[Link] = []
def __str__(self):
return str([Link])
def push(self, data):
if data not in [Link]:
[Link](data)
return True
else:
return False
# Use peek to look at the top of the stack
def peek(self):
return [Link][-1]
stk = Stack()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)
print("Stack Elements:")
print(stk)
print("topmost element: ",[Link]())

isFull()
isFull() operation checks whether the stack is full. This operation is used to check the
status of the stack with the help of top pointer.
Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack, the stack is
full. Return 1.
3. Otherwise, return 0.
4. END
isEmpty()
The isEmpty() operation verifies whether the stack is empty. This operation is used to
check the status of the stack with the help of top pointer.
Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

Python Implementation
class Stack:
def __init__(self):
[Link] = []
def add(self, data):
if data not in [Link]:
[Link](data)
return True
else:
return False

# Use peek to look at the top of the stack

def peek(self):
return [Link][-1]

# Use list pop method to remove element

def remove(self):
if len([Link]) <= 0:
return ("No element in the Stack")
else:
return [Link]()
stk = Stack()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)
print("topmost element: ",[Link]())
print("----Deletion operation in stack----")
[Link]()
[Link]()
print("topmost element after deletion: ",[Link]())

Characteristics of a Stack:
Stack has various different characteristics which are as follows:
Stack is used in many different algorithms like Tower of Hanoi, tree traversal, recursion, etc.
Stack is implemented through an array or linked list.
It follows the Last In First Out operation i.e., an element that is inserted first will pop in last and
vice versa.
The insertion and deletion are performed at one end i.e. from the top of the stack.
In stack, if the allocated space for the stack is full, and still anyone attempts to add more
elements, it will lead to stack overflow.
Applications of Stack:
Different applications of Stack are as follows:

The stack data structure is used in the evaluation and conversion of arithmetic expressions.
Stack is used in Recursion.
It is used for parenthesis checking.
While reversing a string, the stack is used as well.
Stack is used in memory management.
It is also used for processing function calls.
The stack is used to convert expressions from infix to postfix.
The stack is used to perform undo as well as redo operations in word processors.
The stack is used in virtual machines like JVM.
The stack is used in the media players. Useful to play the next and previous song.
The stack is used in recursion operations.
Real-Life Applications of Stack:
Real life example of a stack is the layer of eating plates arranged one above the other. When you
remove a plate from the pile, you can take the plate to the top of the pile. But this is exactly the
plate that was added most recently to the pile. If you want the plate at the bottom of the pile,
you must remove all the plates on top of it to reach it.
Browsers use stack data structures to keep track of previously visited sites.
Call log in mobile also uses stack data structure.
Advantages of Stack:
Stacks are simple data structures with a well-defined set of operations, which makes them easy
to understand and use.
Stacks are efficient for adding and removing elements, as these operations have a time
complexity of O(1).
In order to reverse the order of elements we use the stack data structure.
Stacks can be used to implement undo/redo functions in applications.
Drawbacks of Stack:
Restriction of size in Stack is a drawback and if they are full, you cannot add any more elements
to the stack.
Stacks do not provide fast access to elements other than the top element.
Stacks do not support efficient searching, as you have to pop elements one by one until you find
the element you are looking for.
Application of Stack Data Structure:
Function calls and recursion: When a function is called, the current state of the program is
pushed onto the stack. When the function returns, the state is popped from the stack to resume
the previous function’s execution.
Undo/Redo operations: The undo-redo feature in various applications uses stacks to keep track
of the previous actions. Each time an action is performed, it is pushed onto the stack. To undo
the action, the top element of the stack is popped, and the reverse operation is performed.
Expression evaluation: Stack data structure is used to evaluate expressions in infix, postfix, and
prefix notations. Operators and operands are pushed onto the stack, and operations are
performed based on the stack’s top elements.
Browser history: Web browsers use stacks to keep track of the web pages you visit. Each time
you visit a new page, the URL is pushed onto the stack, and when you hit the back button, the
previous URL is popped from the stack.
Balanced Parentheses: Stack data structure is used to check if parentheses are balanced or not.
An opening parenthesis is pushed onto the stack, and a closing parenthesis is popped from the
stack. If the stack is empty at the end of the expression, the parentheses are balanced.
Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the states of
the problem-solving process. The current state is pushed onto the stack, and when the
algorithm backtracks, the previous state is popped from the stack.
Application of Stack in real life:

CD/DVD stand.
Stack of books in a book shop.
Call center systems.
Undo and Redo mechanism in text editors.
The history of a web browser is stored in the form of a stack.
Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack.
YouTube downloads and Notifications are also shown in LIFO format(the latest appears first ).
Allocation of memory by an operating system while executing a process.
Advantages of Stack:

Easy implementation: Stack data structure is easy to implement using arrays or linked lists, and
its operations are simple to understand and implement.
Efficient memory utilization: Stack uses a contiguous block of memory, making it more efficient
in memory utilization as compared to other data structures.
Fast access time: Stack data structure provides fast access time for adding and removing
elements as the elements are added and removed from the top of the stack.
Helps in function calls: Stack data structure is used to store function calls and their states, which
helps in the efficient implementation of recursive function calls.
Supports backtracking: Stack data structure supports backtracking algorithms, which are used in
problem-solving to explore all possible solutions by storing the previous states.
Used in Compiler Design: Stack data structure is used in compiler design for parsing and syntax
analysis of programming languages.
Enables undo/redo operations: Stack data structure is used to enable undo and redo operations
in various applications like text editors, graphic design tools, and software development
environments.
Disadvantages of Stack:

Limited capacity: Stack data structure has a limited capacity as it can only hold a fixed number
of elements. If the stack becomes full, adding new elements may result in stack overflow,
leading to the loss of data.
No random access: Stack data structure does not allow for random access to its elements, and it
only allows for adding and removing elements from the top of the stack. To access an element in
the middle of the stack, all the elements above it must be removed.
Memory management: Stack data structure uses a contiguous block of memory, which can
result in memory fragmentation if elements are added and removed frequently.
Not suitable for certain applications: Stack data structure is not suitable for applications that
require accessing elements in the middle of the stack, like searching or sorting algorithms.
Stack overflow and underflow: Stack data structure can result in stack overflow if too many
elements are pushed onto the stack, and it can result in stack underflow if too many elements
are popped from the stack.
Recursive function calls limitations: While stack data structure supports recursive function calls,
too many recursive function calls can lead to stack overflow, resulting in the termination of the
program.

Application of stack to check delimiter:

Delimiter Checking
The common application of Stack is delimiter checking, i.e., parsing that involves analyzing a
source program syntactically. It is also called parenthesis checking. When the compiler
translates a source program written in some programming language such as C, C++ to a machine
language, it parses the program into multiple individual parts such as variable names, keywords,
etc. By scanning from left to right. The main problem encountered while translating is the
unmatched delimiters. We make use of different types of delimiters include the parenthesis
checking (,), curly braces {,} and square brackets [,], and common delimiters /* and */. Every
opening delimiter must match a closing delimiter, i.e., every opening parenthesis should be
followed by a matching closing parenthesis. Also, the delimiter can be nested. The opening
delimiter that occurs later in the source program should be closed before those occurring
earlier.
 To perform a delimiter checking, the compiler makes use of a stack. When a compiler translates
a source program, it reads the characters one at a time, and if it finds an opening delimiter it
places it on a stack. When a closing delimiter is found, it pops up the opening delimiter from the
top of the Stack and matches it with the closing delimiter.
On matching, the following cases may arise.
If the delimiters are of the same type, then the match is considered successful, and the process
continues.
If the delimiters are not of the same type, then the syntax error is reported.
When the end of the program is reached, and the Stack is empty, then the processing of the
source program stops.

Example: To explain this concept, let's consider the following expression.

[{(a -b) * (c -d)}/f]

Appliction of stack to convert prefix to postfix:
Evaluation of Arithmetic Expression requires two steps:
First, convert the given expression into special notation.
Evaluate the expression in this new notation.
Notations for Arithmetic Expression
There are three notations to represent an arithmetic expression:

Infix Notation
Prefix Notation
Postfix Notation
Infix Notation

The infix notation is a convenient way of writing an expression in which each operator is placed
between the operands. Infix expressions can be parenthesized or unparenthesized depending
upon the problem requirement.
All these expressions are in infix notation because the operator comes
between the operands. Example: A + B, (C - D) etc.

Prefix Notation

The prefix notation places the operator before the operands. This notation was introduced by
the Polish mathematician and hence often referred to as polish notation.

Example: + A B, -CD etc.

All these expressions are in prefix notation because the operator comes before the operands.

Postfix Notation
The postfix notation places the operator after the operands. This notation is just the reverse of
Polish notation and also known as Reverse Polish notation.

Example: AB +, CD+, etc. A*B= *AB, AB*. (A+B)*(C-D)=*+AB-CD, AB+CD-*

All these expressions are in postfix notation because the operator comes after the operands
Prefix to Postfix Conversion
Prefix: An expression is called the prefix expression if the operator appears in the expression
before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )

Postfix: An expression is called the postfix expression if the operator appears in the expression
after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B * (C-D) )
Given a Prefix expression, convert it into a Postfix expression.
Conversion of Prefix expression directly to Postfix without going through the process of
converting them first to Infix and then to Postfix is much better in terms of computation and
better understanding the expression (Computers evaluate using Postfix expression).
Examples:

Input : Prefix : *+AB-CD = (A+B)*(C-D)=AB+CD-*

Output : Postfix : AB+CD-*
Explanation : Prefix to Infix : (A+B) * (C-D)
Infix to Postfix : AB+CD-*

Input : Prefix : *-A/BC-/AKL

Output : Postfix : ABC/-AK/L-*
Explanation : Prefix to Infix : (A-(B/C))*((A/K)-L)
ABC/-AK/L-*
Infix to Postfix : ABC/-AK/L-*
Algorithm for Prefix to Postfix:
Read the Prefix expression in reverse order (from right to left)
If the symbol is an operand, then push it onto the Stack
If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator after them. AK/
string = operand1 + operand2 + operator
And push the resultant string back to Stack
Repeat the above steps until end of Prefix expression.
Program to convert prefix to postfix:
# Write Python3 code here
# -*- coding: utf-8 -*-

# Example Input
s = "*-A/BC-/AKL"

# Stack for storing operands

stack = []

operators = set(['+', '-', '*', '/', '^'])

# Reversing the order
s = s[::-1]

# iterating through individual tokens

for i in s:

# if token is operator
if i in operators:

# pop 2 elements from stack

a = [Link]()
b = [Link]()

# concatenate them as operand1 +

# operand2 + operator
temp = a+b+i
[Link](temp)

# else if operand
else:
[Link](i)

# printing final output

print(*stack)

What is a Queue?
Queue is a linear data structure in which the insertion and deletion operations are performed at
two different ends. In a queue data structure, adding and removing elements are performed at
two different positions. The insertion is performed at one end and deletion is performed at
another end. In a queue data structure, the insertion operation is performed at a position which
is known as 'rear' and the deletion operation is performed at a position which is known as
'front'. In queue data structure, the insertion and deletion operations are performed based on
FIFO (First In First Out) principle.

In a queue data structure, the insertion operation is performed using a function called
"enQueue()" and deletion operation is performed using a function called "deQueue()".
Operations on a Queue
The following operations are performed on a queue data structure...

1. enQueue(value) - (To insert an element into the queue)

2. deQueue() - (To delete an element from the queue)
3. display() - (To display the elements of the queue)
4. Isempty()
5. Isfull()

Queue data structure can be implemented in two ways. They are as follows...

1. Using Array
2. Using Linked List

When a queue is implemented using an array, that queue can organize an only limited number
of elements. When a queue is implemented using a linked list, that queue can organize an
unlimited number of elements.

Representation of Queues
Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked
lists, or pointers. As a small example in this tutorial, we implement queues using a one-
dimensional array.
Basic Operations
Queue operations also include initialization of a queue, usage and permanently deleting
the data from the memory.
The most fundamental operations in the queue ADT include: enqueue(), dequeue(),
peek(), isFull(), isEmpty(). These are all built-in operations to carry out data
manipulation and to check the status of the queue.
Queue uses two pointers − front and rear. The front pointer accesses the data from the
front end (helping in enqueueing) while the rear pointer accesses data from the rear end
(helping in dequeuing).

Insertion operation: enqueue()

The enqueue() is a data manipulation operation that is used to insert elements into the stack.
The following algorithm describes the enqueue() operation in a simpler way.

Algorithm

1 − START

2 – Check if the queue is full.

3 − If the queue is full, produce overflow error and exit.

4 − If the queue is not full, increment rear pointer to point the next empty space.

5 − Add data element to the queue location, where the rear is pointing.

6 − return success.

7 – END

class Queue:
def __init__(self):
[Link] = list()
 def __str__(self):
return str([Link])
def addtoqueue(self,data):

# Insert method to add element

if data not in [Link]:
[Link](0,data)
return True
return False

q = Queue()
[Link]("36")
[Link]("24")
[Link]("48")
[Link]("12")
[Link]("66")
print("Queue:")

print(q)

Deletion Operation: dequeue()

The dequeue() is a data manipulation operation that is used to remove elements from the stack.
The following algorithm describes the dequeue() operation in a simpler way.

Algorithm

1 – START

2 − Check if the queue is empty.

3 − If the queue is empty, produce underflow error and exit.

4 − If the queue is not empty, access the data where front is pointing.

5 − Increment front pointer to point to the next available data element.

6 − Return success.

7 – END
class Queue:
def __init__(self):
[Link] = list()
def __str__(self):
return str([Link])
def addtoqueue(self,data):

# Insert method to add element

if data not in [Link]:
[Link](0,data)
return True
return False
def removefromqueue(self):
if len([Link])>0:
return [Link]()
return ("Queue is empty")

q = Queue()
[Link]("36")
[Link]("24")
[Link]("48")
[Link]("12")
[Link]("66")
print("Queue:")
print(q)

print("Element deleted from queue: ",[Link]())

The peek() Operation

The peek() is an operation which is used to retrieve the frontmost element in the queue,
without deleting it. This operation is used to check the status of the queue with the help of the
pointer.

Algorithm

1 – START

2 – Return the element at the front of the queue

3 – END
class Queue:
def __init__(self):
[Link] = list()
def __str__(self):
return str([Link])
def addtoqueue(self,data):

# Insert method to add element

if data not in [Link]:
[Link](0,data)
return True
return False
def peek(self):
return [Link][-1]

q = Queue()
[Link]("36")
[Link]("24")
[Link]("48")
[Link]("12")
[Link]("66")
print("Queue:")
print(q)

print("The frontmost element of the queue: ",[Link]())

The isFull() Operation

The isFull() operation verifies whether the queue is full.

Algorithm

1 – START

2 – If the count of queue elements equals the queue size, return true

3 – Otherwise, return false

4 – END
The isEmpty() operation

The isEmpty() operation verifies whether the queue is empty. This operation is used to check the
status of the queue with the help of top pointer.

Algorithm

1 – START

2 – If the count of queue elements equals zero, return true

3 – Otherwise, return false

4 – END
Queue Implementation:
# Queue implementation in Python

class Queue:

def __init__(self):
[Link] = []

# Add an element
def enqueue(self, item):
[Link](item)

# Remove an element
def dequeue(self):
if len([Link]) < 1:
return None
return [Link](0)

# Display the queue

def display(self):
print([Link])

def size(self):
return len([Link])

q = Queue()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)

[Link]()

[Link]()

print("After removing an element")

[Link]()

Applications of Queue:
 Multi programming: Multi programming means when multiple programs are
running in the main memory. It is essential to organize these multiple
programs and these multiple programs are organized as queues.

 Network: In a network, a queue is used in devices such as a router or a

switch. another application of a queue is a mail queue which is a directory
that stores data and controls files for mail messages.
 Job Scheduling: The computer has a task to execute a particular number of
jobs that are scheduled to be executed one after another. These jobs are
assigned to the processor one by one which is organized using a queue.
 Shared resources: Queues are used as waiting lists for a single shared
resource.
Real-time application of Queue:
 ATM Booth Line
 Ticket Counter Line
 Key press sequence on the keyboard
 CPU task scheduling
 Waiting time of each customer at call centers.
Advantages of Queue:
 A large amount of data can be managed efficiently with ease.
 Operations such as insertion and deletion can be performed with ease as it
follows the first in first out rule.
 Queues are useful when a particular service is used by multiple consumers.
 Queues are fast in speed for data inter-process communication.
 Queues can be used in the implementation of other data structures.
Disadvantages of Queue:
 The operations such as insertion and deletion of elements from the middle
are time consuming.
 Limited Space.
 In a classical queue, a new element can only be inserted when the existing
elements are deleted from the queue.
 Searching an element takes O(N) time.
 Maximum size of a queue must be defined prior.

Linked List representation of Queue:

 Create a class QNode with data members integer data and QNode* next
 A parameterized constructor that takes an integer x value as a
parameter and sets data equal to x and next as NULL
 Create a class Queue with data members QNode front and rear
 Enqueue Operation with parameter x:
 Initialize QNode* temp with data = x
 If the rear is set to NULL then set the front and rear to temp and

return(Base Case)
 Else set rear next to temp and then move rear to temp
 Dequeue Operation:
 If the front is set to NULL return(Base Case)
 Initialize QNode temp with front and set front to its next
 If the front is equal to NULL then set the rear to NULL
 Delete temp from the memory

Python code for linked list representation of queue:

# A linked list (LL) node

# to store a queue entry

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

# A class to represent a queue

# The queue, front stores the front node

# of LL and rear stores the last node of LL

class Queue:
def __init__(self):

[Link] = [Link] = None

def isEmpty(self):

return [Link] == None

# Method to add an item to the queue

def EnQueue(self, item):

temp = Node(item)

if [Link] == None:

[Link] = [Link] = temp

return

[Link] = temp

[Link] = temp

# Method to remove an item from queue

def DeQueue(self):

if [Link]():

return

temp = [Link]

[Link] = [Link]
 if([Link] == None):

[Link] = None

# Driver Code

if __name__ == '__main__':

q = Queue()

[Link](10)

[Link](20)

[Link]()

[Link]()

[Link](30)

[Link](40)

[Link](50)

[Link]()

print("Queue Front : " + str([Link] if [Link] != None else -1))

print("Queue Rear : " + str([Link] if [Link] != None else -1))

Output:

Types of Queue
There are four different types of queue that are listed as follows -
 o Simple Queue or Linear Queue
o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion
occurs from another end. The end at which the insertion takes place is
known as the rear end, and the end at which the deletion takes place is
known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only
from the rear end. If the first three elements are deleted from the Queue, we
cannot insert more elements even though the space is available in a Linear
 Queue. In this case, the linear Queue shows the overflow condition as the
rear is pointing to the last element of the Queue.

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the
linear Queue except that the last element of the queue is connected to the
first element. It is also known as Ring Buffer, as all the ends are connected to
another end. The representation of circular queue is shown in the below
image –

The drawback that occurs in a linear queue is overcome by using the circular
queue. If the empty space is available in a circular queue, the new element
can be added in an empty space by simply incrementing the value of rear.
The main advantage of using the circular queue is better memory utilization.

The operations are performed based on FIFO (First In First Out) principle.
It is also called ‘Ring Buffer’.

Operations on Circular Queue:

 Front: Get the front item from the queue.
 Rear: Get the last item from the queue.
 enQueue(value) This function is used to insert an element into the circular
queue. In a circular queue, the new element is always inserted at the rear
position.
 Check whether the queue is full – [i.e., the rear end is in just before
the front end in a circular manner].
 If it is full then display Queue is full.
 If the queue is not full then, insert an element at the end of
the queue.
 deQueue() This function is used to delete an element from the circular
queue. In a circular queue, the element is always deleted from the front
position.
 Check whether the queue is Empty.
 If it is empty then display Queue is empty.
 If the queue is not empty, then get the last element and
remove it from the queue.
Illustration of Circular Queue Operations:
Follow the below image for a better understanding of the enqueue and dequeue
operations.

How to Implement a Circular Queue?

A circular queue can be implemented using two data structures:
 Array
 Linked List
 Here we have shown the implementation of a circular queue using an array data
structure.

Implement Circular Queue using Array:

1. Initialize an array queue of size n, where n is the maximum number of
elements that the queue can hold.
2. Initialize two variables front and rear to -1.
3. Enqueue: To enqueue an element x into the queue, do the following:
 Increment rear by 1.
 If rear is equal to n, set rear to 0.
 If front is -1, set front to 0.
 Set queue[rear] to x.
4. Dequeue: To dequeue an element from the queue, do the following:
 Check if the queue is empty by checking if front is -1.
 If it is, return an error message indicating that the queue is
empty.
 Set x to queue[front].
 If front is equal to rear, set front and rear to -1.
 Otherwise, increment front by 1 and if front is equal to n, set front to 0.
 Return x.
Below is the implementation of the above idea:

 Python 3
class CircularQueue():

# constructor
def __init__(self, size): # initializing the class
[Link] = size

# initializing queue with none

[Link] = [None for i in range(size)]
[Link] = [Link] = -1

def enqueue(self, data):

# condition if queue is full

if (([Link] + 1) % [Link] == [Link]):
print(" Queue is Full\n")

# condition for empty queue

elif ([Link] == -1):
[Link] = 0
[Link] = 0
[Link][[Link]] = data
else:
 # next position of rear
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = data

def dequeue(self):
if ([Link] == -1): # condition for empty queue
print ("Queue is Empty\n")

# condition for only one element

elif ([Link] == [Link]):
temp=[Link][[Link]]
[Link] = -1
[Link] = -1
return temp
else:
temp = [Link][[Link]]
[Link] = ([Link] + 1) % [Link]
return temp

def display(self):

# condition for empty queue

if([Link] == -1):
print ("Queue is Empty")

elif ([Link] >= [Link]):

print("Elements in the circular queue are:",
end = " ")
for i in range([Link], [Link] + 1):
print([Link][i], end = " ")
print ()

else:
print ("Elements in Circular Queue are:",
end = " ")
for i in range([Link], [Link]):
print([Link][i], end = " ")
for i in range(0, [Link] + 1):
print([Link][i], end = " ")
print ()

if (([Link] + 1) % [Link] == [Link]):

print("Queue is Full")

# Driver Code
ob = CircularQueue(5)
[Link](14)
[Link](22)
[Link](13)
[Link](-6)
[Link]()
print ("Deleted value = ", [Link]())
print ("Deleted value = ", [Link]())
[Link]()
[Link](9)
[Link](20)
[Link](5)
[Link]()

Priority Queue
It is a special type of queue in which the elements are arranged based on the
priority. It is a special type of queue data structure in which every element
has a priority associated with it. Suppose some elements occur with the
same priority, they will be arranged according to the FIFO principle. The
representation of priority queue is shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in
the priority queue occurs based on the priority. Priority queue is mainly used
to implement the CPU scheduling algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements

can be inserted in arbitrary order, but only smallest can be deleted
 first. Suppose an array with elements 7, 5, and 3 in the same order, so,
insertion can be done with the same sequence, but the order of
deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements
can be inserted in arbitrary order, but only the largest element can be
deleted first. Suppose an array with elements 7, 3, and 5 in the same
order, so, insertion can be done with the same sequence, but the order
of deleting the elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from
both ends of the queue either from the front or rear. It means that we can
insert and delete elements from both front and rear ends of the queue.
Deque can be used as a palindrome checker means that if we read the string
from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and
deletion operations on both ends. Deque can be considered as stack because
stack follows the LIFO (Last In First Out) principle in which insertion and
deletion both can be performed only from one end. And in deque, it is
possible to perform both insertion and deletion from one end, and Deque
does not follow the FIFO principle.

The representation of the deque is shown in the below image -

There are two types of deque that are discussed as follows -

 o Input restricted deque - As the name implies, in input restricted
queue, insertion operation can be performed at only one end, while
deletion can be performed from both ends.

Output restricted deque - As the name implies, in output restricted queue,

deletion operation can be performed at only one end, while insertion can be
performed from both ends.

Operations on deque
Example 1: Appending Items Efficiently
 append():- This function is used to insert the value in its argument to the
right end of the deque.
 appendleft():- This function is used to insert the value in its argument to the
left end of the deque.
 Python3

# importing "collections" for deque operations

import collections

# initializing deque

de = [Link]([1, 2, 3])

print("deque: ", de)

# using append() to insert element at right end

# inserts 4 at the end of deque

[Link](4)

# printing modified deque

print("\nThe deque after appending at right is : ")

print(de)

# using appendleft() to insert element at left end

# inserts 6 at the beginning of deque

[Link](6)
 # printing modified deque

print("\nThe deque after appending at left is : ")

print(de)

Output:

Example 2: Popping Items Efficiently

 pop():- This function is used to delete an argument from the right end of the
deque.
 popleft():- This function is used to delete an argument from the left end of
the deque.
 Python3

# importing "collections" for deque operations

import collections

# initializing deque

de = [Link]([6, 1, 2, 3, 4])

print("deque: ", de)

# using pop() to delete element from right end

# deletes 4 from the right end of deque

[Link]()

# printing modified deque

print("\nThe deque after deleting from right is : ")

print(de)

# using popleft() to delete element from left end

# deletes 6 from the left end of deque

[Link]()

# printing modified deque

print("\nThe deque after deleting from left is : ")

print(de)

Output:
What are Scheduling Queues?
The processes waiting for a device are placed in Device Queues. There are unique
device queues which are available for every I/O device.
First place a new process in the Ready queue and then it waits in the ready queue till it
is selected for execution.
Once the process is assigned to the CPU and is executing, any one of the following
events occur −
 The process issue an I/O request, and then placed in the I/O queue.
 The process may create a new sub process and wait for termination.
 The process may be removed forcibly from the CPU, which is an interrupt, and it
is put back in the ready queue.
 In the first two cases, the process switches from the waiting state to the ready state, and
then puts it back in the ready queue. A process continues this cycle till it terminates, at
which time it is removed from all queues and has its PCB and resources deallocated.

Types of Schedulers
There are three types of schedulers available which are as follows −

Long Term Scheduler

Long term scheduling is performed when a new process is created, if the number of
ready processes in the ready queue becomes very high. Then, there is an overhead on
the operating system, for maintaining long lists, containing switching and dispatching
increases. Therefore, allowing only a limited number of processes into the ready queue,
the long term scheduler manages this.
Long term scheduler runs less frequently. It decides which program must get into the
job queue. From the job queue, the job processor selects processes and loads them
into the memory for execution.
The main aim of the Job Scheduler is to maintain a good degree of Multiprogramming.
The degree of Multiprogramming means the average rate of process creation is equal
to the average departure rate of processes from the execution memory.
The diagram of long term and short term scheduler is as follows −

Short Term Scheduler

Short term scheduler is called a CPU Scheduler and runs very frequently. The aim of
the scheduler is to enhance CPU performance and increase process execution rate.

Medium Term Scheduler

This type of scheduling removes the processes from memory and thus reduces the
degree of multiprogramming. Later, the process is reintroduced into memory and its
execution is continued where it left off. This is called swapping. The process is
swapped out, and is later swapped in, by the medium term scheduler.
The diagram of medium term scheduler is as follows −

Job sequencing problem using Priority-Queue (Max-

Heap):
Sort the jobs in the increasing order of their deadlines and then calculate the
available slots between every two consecutive deadlines while iterating from
the end. Include the profit of the job at the root of the Max-Heap while the
empty slots are available and Heap is not empty, as this would help to choose
the jobs with maximum profit for every set of available slots.
Follow the given steps to solve the problem:
 Sort the jobs based on their deadlines.
 Iterate from the end and calculate the available slots between every two
consecutive deadlines. Insert the profit, deadline, and job ID of ith job in the
max heap.
 While the slots are available and there are jobs left in the max heap, include
the job ID with maximum profit and deadline in the result.
 Sort the result array based on their deadlines.

Program:
# Python3 program for the above approach
import heapq

def printJobScheduling(arr):
 n = len(arr)

# arr[i][0] = job_id, arr[i][1] = deadline, arr[i][2] = profit

# sorting the array on the

# basis of their deadlines
[Link](key=lambda x: x[1])

# initialise the result array and maxHeap

result = []
maxHeap = []

# starting the iteration from the end

for i in range(n - 1, -1, -1):

# calculate slots between two deadlines

if i == 0:
slots_available = arr[i][1]
else:
slots_available = arr[i][1] - arr[i - 1][1]

# include the profit of job(as priority), deadline

# and job_id in maxHeap
# note we push negative value in maxHeap to convert
# min heap to max heap in python
[Link](maxHeap, (-arr[i][2], arr[i][1], arr[i][0]))

while slots_available and maxHeap:

# get the job with max_profit

profit, deadline, job_id = [Link](maxHeap)

# reduce the slots

slots_available -= 1

# include the job in the result array

[Link]([job_id, deadline])

# jobs included might be shuffled

# sort the result array by their deadlines
[Link](key=lambda x: x[1])

for job in result:

print(job[0], end=" ")
print()

# Driver's Code
if __name__ == '__main__':
arr = [['a', 2, 100], # Job Array
 ['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]

print("Following is maximum profit sequence of jobs")

# Function Call
printJobScheduling(arr)

# This code is contributed