Python - DataStructure - InshortsView

Divnesh BLOG

Data structures represent the way of arranging data in computer so that it can be accessed and used efficiently. It is all about grouping and storing collections of data in memory, operations that can be performed on these collections and algorithms that can be used for these operations.

Scenario-1:
It was a Saturday morning and Maria was in the grocery shop with her list of grocery items. The list kept on changing as she moved from one section of the shop to another. She added few items, removed few and kept on scanning the list.
She in fact, started with a list of 4 items and ended up buying many more.

In this case, we can use list data structure to represent Maria’s list of grocery items.

List is

a linear data structure
used to store a sequence of values
can grow and shrink dynamically based on need

#Do not remove the below import statement

import sys

'''This function provides the capacity, size and space left in the list.

You can invoke it to get the details of the list'''

def list_details(lst):

#Number of elements that can be stored in the list

print("Capacity:", (sys.getsizeof(lst)-36)//4)

#Number of elements in the list

print("Size:", len(lst))

#Number of elements that can be accommodated in the space left

print("Space Left:", ((sys.getsizeof(lst)-36) - len(lst*4))//4)

#formula changes based on the system architecture

#(size-36)/4 for 32 bit machines and

#(size-64)/8 for 64 bit machines

# 36, 64 - size of an empty list based on machine

# 4, 8 - size of a single element in the list based on machine

marias_lst=[]

print("Empty list created!!!")

print("List details:")

list_details(marias_lst)

List Using Array

Operation	Description
add	Add an element to the end of the list or append an element	.append(element)
insert	Insert an element at a given position	.insert(pos,element)
delete	Delete an element from a given position	pop(pos)
display	Display the elements of the list	List[index]

Add Operation:

add(element):
1. When the list is initially created, it is created 
   with a certain capacity.
2. While adding the elements, if the list is filled 
   to the capacity,
   a. Create a new list with increased capacity
   b. Copy the elements of initial list to the new list
3. Add the element to the end of the existing elements 
   in the list

Insert Operation:

insert(pos, element):
 1. If the list is filled to capacity
    a. Create a new list with increased capacity
    b. Copy the elements of initial list to the new list
 2. Shift right all the existing elements from index 
    position (pos) by 1 position
 3. Insert the element at index position (pos)

Delete Operation:

delete(pos):
 1. Shift left all the existing elements from index 
    position (pos+1) by 1 position
Note: Capacity will be decreased whenever remaining number 
of elements fall below certain value

The space after adding the element can be used for further adding or inserting the elements. However, they should be considered only as reserved space. We cannot directly access that space

def update_mark_list(mark_list, new_element, pos):

mark_list.insert(pos,new_element)

return mark_list

def find_mark(mark_list,pos1,pos2):

index_list =[pos1,pos2]

res_list = [mark_list[i] for i in index_list]

return res_list

#Provide different values for the variables and test your program

mark_list=[89,78,99,76,77,72,88,99]

new_element=69

pos=2

pos1=5

pos2=8

print(update_mark_list(mark_list, new_element, pos))

print(find_mark(mark_list, pos1, pos2))

List Using Linked List

A linked list consists of a group of nodes which together represent a sequence or a list. Each node will have a data part which holds the actual data and an address part which holds the link to the next node. The first node in the list is known as head node and the last node is known as tail node. Unlike array, in linked list, the nodes need not be stored in contiguous memory locations.

Display Operation

display()
1. Call the head node as temp
2. While temp is not None,
   a. Display temp’s data
   b. Make the next node as temp

Add Operation

add(data)
1. Create a new node with the data
2. If the linked list is empty (head node is not referring to any other node), 
   make the head node and the tail node refer to the new node
3. Otherwise,
   a. Make the tail node’s link refer to new node
   b. Call the new node as tail node

Insert Operation

insert(data,data_before)
1. Create a new node with the given data
2. If the data_before is None,
    a. Make the new node's link refer to head node 
    b. Call the new node as head node
    c. If the new node's link is None, make it the tail node
3. Else
    a. Find the node with data_before, once found consider it as node_before
    b. Make the new node’s link refer to node_before’s link.
    c. Make the node_before’s link refer to new node
    d. If new node’s link is None, make it the tail node
4. If node with data_before is not found, display appropriate error message

Delete Operation

delete(data):
1. Find the node with the given data. If found,
   a. If the node to be deleted is head node, make the next node as head node
      1. If it is also the tail node, make the tail node as None
   b. Otherwise,
      1. Traverse till the node before the node to be deleted, call it temp
      2. Make temp’s link refer to node’s link.
      3. If the node to be deleted is the tail node, call the temp as tail node
      4. Make the node's link as None
2. If the node to be deleted is not found, display appropriate error message

Sample code:

class Node:

def __init__(self,data):

self.__data=data

self.__next=None

def get_data(self):

return self.__data

def set_data(self,data):

self.__data=data

def get_next(self):

return self.__next

def set_next(self,next_node):

self.__next=next_node

class LinkedList:

def __init__(self):

self.__head=None

self.__tail=None

def get_head(self):

return self.__head

def get_tail(self):

return self.__tail

#This method is added for this tryout alone

def set_head(self,new_node):

self.__head=new_node

#This method is added for this tryout alone

def set_tail(self,new_node):

self.__tail=new_node

def add(self,data):

new_node=Node(data)

if(self.__head is None):

self.__head=self.__tail=new_node

else:

self.__tail.set_next(new_node)

self.__tail=new_node

def insert(self,data,data_before):

new_node=Node(data)

if(data_before==None):

new_node.set_next(self.__head)

self.__head=new_node

if(new_node.get_next()==None):

self.__tail=new_node

else:

node_before=self.find_node(data_before)

if(node_before is not None):

new_node.set_next(node_before.get_next())

node_before.set_next(new_node)

if(new_node.get_next() is None):

self.__tail=new_node

else:

print(data_before,"is not present in the Linked list")

def display(self):

temp=self.__head

while(temp is not None):

print(temp.get_data())

temp=temp.get_next()

def find_node(self,data):

temp=self.__head

while(temp is not None):

if(temp.get_data()==data):

return temp

temp=temp.get_next()

return None

def delete(self,data):

node=self.find_node(data)

if(node is not None):

if(node==self.__head):

if(self.__head==self.__tail):

self.__tail=None

self.__head=node.get_next()

else:

temp=self.__head

while(temp is not None):

if(temp.get_next()==node):

temp.set_next(node.get_next())

if(node==self.__tail):

self.__tail=temp

node.set_next(None)

break

temp=temp.get_next()

else:

print(data,"is not present in Linked list")

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

temp=self.__head

msg=[]

while(temp is not None):

msg.append(str(temp.get_data()))

temp=temp.get_next()

msg=" ".join(msg)

msg="Linkedlist data(Head to Tail): "+ msg

return msg

def find_total_nodes(mem_block):

temp=mem_block.get_head()

total_nodes=0

while(temp is not None):

total_nodes+=1

temp=temp.get_next()

return total_nodes

def maximum_contiguous_free_blocks(mem_block):

temp=mem_block.get_head()

total_nodes=find_total_nodes(mem_block)

free_list=[]

free_contiguous_nodes=0

if(temp.get_data()=="Free"):

free_contiguous_nodes+=1

prev_data=temp.get_data()

temp=temp.get_next()

while(temp is not None):

if(temp.get_data()=="Free"):

if(prev_data=="Free"):

free_contiguous_nodes+=1

else:

free_list.append(free_contiguous_nodes)

free_contiguous_nodes=1

else:

free_list.append(free_contiguous_nodes)

free_contiguous_nodes=0

prev_data=temp.get_data()

temp=temp.get_next()

free_list.append(free_contiguous_nodes)

max_free_contiguous_nodes=max(free_list)

return((max_free_contiguous_nodes/total_nodes)*100)

def total_free_blocks(mem_block):

temp=mem_block.get_head()

total_blocks=find_total_nodes(mem_block)

total_free_blocks=0

while(temp is not None):

if(temp.get_data()=="Free"):

total_free_blocks+=1

temp=temp.get_next()

return ((total_free_blocks/total_blocks)*100)

def memory_compaction(mem_block):

temp=mem_block.get_head()

prev_occupied=None

prev_free=None

occupied=None

free=None

if(temp.get_data()=="Occupied"):

occupied=temp

prev_occupied=temp

elif(temp.get_data()=="Free"):

free=temp

prev_free=temp

temp=temp.get_next()

while(temp is not None):

if(temp.get_data()=="Occupied"):

if(occupied==None):

occupied=temp

if(prev_occupied==None):

prev_occupied=temp

else:

prev_occupied.set_next(temp)

prev_occupied=temp

elif(temp.get_data()=="Free"):

if(free==None):

free=temp

if(prev_free==None):

prev_free=temp

else:

prev_free.set_next(temp)

prev_free=temp

temp=temp.get_next()

prev_occupied.set_next(free)

prev_free.set_next(None)

mem_block.set_head(occupied)

mem_block.set_tail(prev_free)

mem_block=LinkedList()

mem_block.add("Occupied")

mem_block.add("Free")

mem_block.add("Occupied")

mem_block.add("Free")

mem_block.add("Occupied")

mem_block.add("Free")

print("Before compaction")

print("_________________")

print("Max. contiguous free blocks:", maximum_contiguous_free_blocks(mem_block),"%")

print("Total free blocks:",total_free_blocks(mem_block),"%")

memory_compaction(mem_block)

print()

print("After compaction")

print("________________")

print("Max. contiguous free blocks:", maximum_contiguous_free_blocks(mem_block),"%")

print("Total free blocks:",total_free_blocks(mem_block),"%")

	List using Array	List using Linked List
Insert	Shifting of elements are required	Shifting of elements are not required
Delete	Shifting of elements are required	Shifting of elements are not required
Memory	Elements are stored in contiguous memory locations	Elements need not necessarily be stored in contiguous memory locations
Access	Both random and sequential	Only sequential

Stack: LIFO principle

Operations possible on the stack are:

Push or insert an element to the top of the stack
Pop or remove an element from top of the stack

push(data):
1. Check whether the stack is full. If full, display appropriate message
2. If not,
   a. increment top by one
   b. Add the element at top position in the elements array

pop:
1. Check whether the stack is empty. If empty, display appropriate message
2. If not,
   a. Retrieve data at the top of the stack
   b. Decrement top by 1
   c. Return the retrieved data

Uses : Stack is used to implement bracket matching algorithm for arithmetic expression evaluation and also in implementation of method calls.

class Stack:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__top=-1

def is_full(self):

if(self.__top==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__top==-1):

return True

return False

def push(self,data):

if(self.is_full()):

print("The stack is full!!")

else:

self.__top+=1

self.__elements[self.__top]=data

def pop(self):

if(self.is_empty()):

print("The stack is empty!!")

else:

data= self.__elements[self.__top]

self.__top-=1

return data

def display(self):

if(self.is_empty()):

print("The stack is empty")

else:

index=self.__top

while(index>=0):

print(self.__elements[index])

index-=1

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__top

while(index>=0):

msg.append((str)(self.__elements[index]))

index-=1

msg=" ".join(msg)

msg="Stack data(Top to Bottom): "+msg

return msg

def remove():

global clipboard,undo_stack

data=clipboard[len(clipboard)-1]

clipboard.remove(data)

undo_stack.push(data)

print("Remove:",clipboard)

def undo():

global clipboard,undo_stack,redo_stack

if(undo_stack.is_empty()):

print("There is no data to undo")

else:

data=undo_stack.pop()

clipboard.append(data)

redo_stack.push(data)

print("Undo:",clipboard)

def redo():

global clipboard, undo_stack,redo_stack

if(redo_stack.is_empty()):

print("There is no data to redo")

else:

data=redo_stack.pop()

if(data not in clipboard):

print("There is no data to redo")

redo_stack.push(data)

else:

clipboard.remove(data)

undo_stack.push(data)

print("Redo:",clipboard)

clipboard=["A","B","C","D","E","F"]

undo_stack=Stack(len(clipboard))

redo_stack=Stack(len(clipboard))

remove()

undo()

redo()

#DSA-Exer-6

class Stack:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__top=-1

def get_max_size(self):

return self.__max_size

def is_full(self):

if(self.__top==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__top==-1):

return True

return False

def push(self,data):

if(self.is_full()):

print("The stack is full!!")

else:

self.__top+=1

self.__elements[self.__top]=data

def pop(self):

if(self.is_empty()):

print("The stack is empty!!")

else:

data= self.__elements[self.__top]

self.__top-=1

return data

def display(self):

if(self.is_empty()):

print("The stack is empty")

else:

index=self.__top

while(index>=0):

print(self.__elements[index])

index-=1

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__top

while(index>=0):

msg.append((str)(self.__elements[index]))

index-=1

msg=" ".join(msg)

msg="Stack data(Top to Bottom): "+msg

return msg

def find_average(num_list):

sumofelement = 0

count=1

if(not num_list.is_empty() ):

sumofelement = num_list.pop() + sumofelement

count=1+count

avarage = sumofelement/(count)

return avarage

#Push different values to the stack and test your program

num_list=Stack(7)

num_list.push(78)

num_list.push(65)

num_list.push(92)

num_list.push(46)

num_list.push(89)

num_list.push(71)

new_stack=find_average(num_list)

print(new_stack)

Queue: FIFO principle

Operations possible on the queue are:

En-queue or add an element to the end of the queue
De-queue or remove an element from the front of the queue

enqueue (data):
1. Check whether queue is full. If full, display appropriate message
2. If not,
   a. increment rear by one
   b. Add the element at rear position in the elements array

dequeue()
1. Check whether the queue is empty. If it is empty, display appropriate message
2. If not,
   a. Retrieve data at the front of the queue
   b. Increment front by 1
   c. Return the retrieved data

class Queue:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__rear=-1

self.__front=0

def is_full(self):

if(self.__rear==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__front>self.__rear):

return True

return False

def enqueue(self,data):

if(self.is_full()):

print("Queue is full!!!")

else:

self.__rear+=1

self.__elements[self.__rear]=data

def dequeue(self):

if(self.is_empty()):

print("Queue is empty!!!")

else:

data=self.__elements[self.__front]

self.__front+=1

return data

def display(self):

for index in range(self.__front, self.__rear+1):

print(self.__elements[index])

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__front

while(index<=self.__rear):

msg.append((str)(self.__elements[index]))

index+=1

msg=" ".join(msg)

msg="Queue data(Front to Rear): "+msg

return msg

def send_for_print(doc):

global print_queue

if(print_queue.is_full()):

print("Queue is full")

else:

print_queue.enqueue(doc)

print(doc,"sent for printing")

def start_printing():

global print_queue

while(not print_queue.is_empty()):

doc=print_queue.dequeue()

global pages_in_printer

for i in range(0,len(doc)):

if(doc[i]=="-"):

no_of_pages=int(doc[i+1:])

break

if(no_of_pages<=pages_in_printer):

print(doc,"printed")

pages_in_printer-=no_of_pages

print("Remaining no. of pages in printer:", pages_in_printer)

else:

print("Couldn't print",doc[:i],". Not enough pages in the printer.")

pages_in_printer=12

print_queue=Queue(10)

send_for_print("doc1-5")

send_for_print("doc2-3")

send_for_print("doc3-6")

start_printing()

class Queue:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__rear=-1

self.__front=0

def is_full(self):

if(self.__rear==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__front>self.__rear):

return True

return False

def enqueue(self,data):

if(self.is_full()):

print("Queue is full!!!")

else:

self.__rear+=1

self.__elements[self.__rear]=data

def dequeue(self):

if(self.is_empty()):

print("Queue is empty!!!")

else:

data=self.__elements[self.__front]

self.__front+=1

return data

def display(self):

for index in range(self.__front, self.__rear+1):

print(self.__elements[index])

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__front

while(index<=self.__rear):

msg.append((str)(self.__elements[index]))

index+=1

msg=" ".join(msg)

msg="Queue data(Front to Rear): "+msg

return msg

class Node:

def __init__(self,data):

self.__data=data

self.__next=None

def get_data(self):

return self.__data

def set_data(self,data):

self.__data=data

def get_next(self):

return self.__next

def set_next(self,next_node):

self.__next=next_node

class LinkedList:

def __init__(self):

self.__head=None

self.__tail=None

def get_head(self):

return self.__head

def get_tail(self):

return self.__tail

def add(self,data):

new_node=Node(data)

if(self.__head is None):

self.__head=self.__tail=new_node

else:

self.__tail.set_next(new_node)

self.__tail=new_node

def insert(self,data,data_before):

new_node=Node(data)

if(data_before==None):

new_node.set_next(self.__head)

self.__head=new_node

if(new_node.get_next()==None):

self.__tail=new_node

else:

node_before=self.find_node(data_before)

if(node_before is not None):

new_node.set_next(node_before.get_next())

node_before.set_next(new_node)

if(new_node.get_next() is None):

self.__tail=new_node

else:

print(data_before,"is not present in the Linked list")

def display(self):

temp=self.__head

while(temp is not None):

print(temp.get_data())

temp=temp.get_next()

def find_node(self,data):

temp=self.__head

while(temp is not None):

if(temp.get_data()==data):

return temp

temp=temp.get_next()

return None

def delete(self,data):

node=self.find_node(data)

if(node is not None):

if(node==self.__head):

if(self.__head==self.__tail):

self.__tail=None

self.__head=node.get_next()

else:

temp=self.__head

while(temp is not None):

if(temp.get_next()==node):

temp.set_next(node.get_next())

if(node==self.__tail):

self.__tail=temp

node.set_next(None)

break

temp=temp.get_next()

else:

print(data,"is not present in Linked list")

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

temp=self.__head

msg=[]

while(temp is not None):

msg.append(str(temp.get_data()))

temp=temp.get_next()

msg=" ".join(msg)

msg="Linkedlist data(Head to Tail): "+ msg

return msg

def fun(input_list1,input_list2):

temp1 = input_list1.get_head()

temp2 = input_list2.get_head()

output_queue = Queue(10)

while(temp1 != None and temp2 != None):

if(temp1.get_data() < temp2.get_data()):

output_queue.enqueue(temp1.get_data())

temp1 = temp1.get_next()

elif(temp1.get_data() > temp2.get_data()):

output_queue.enqueue(temp2.get_data())

temp2 = temp2.get_next()

else:

output_queue.enqueue(temp2.get_data())

temp1 = temp1.get_next()

temp2 = temp2.get_next()

while(temp1 != None):

output_queue.enqueue(temp1.get_data())

temp1 = temp1.get_next()

while(temp2 != None):

output_queue.enqueue(temp2.get_data())

temp2 = temp2.get_next()

return output_queue

list1=LinkedList()

list1.add(1)

list1.add(2)

list1.add(5)

list1.add(7)

list1.add(8)

list1.add(10)

list2=LinkedList()

list2.add(3)

list2.add(4)

list2.add(6)

list2.add(9)

res_queue=fun(list1,list2)

res_queue.display()

Graph:

In these scenarios, we understand that we cannot use any of the linear data structures like array, linked list, stack or queue to represent it. Here, we need an arrangement which allows to have a set of vertices and edges between them. Such a data structure is known as graph.

Graph is a non-linear data structure having a set of vertices(or nodes) and edges between vertices. It can have any number of edges and nodes and any node can be connected to any other node by an edge. It can be implemented using arrays or linked lists.

Operation	Description
createGraph()	Creates a graph
addNode(node)	Adds a node/vertex
addEdge(node1, node2)	Adds an edge between two nodes
isEmpty()	Checks whether the graph is empty
isLink(node1, node2)	Checks whether an edge exists between two nodes
deleteNode(node)	Deletes a node
deleteEdge(node1, node2)	Deletes the edge between two nodes
getNodes()	Gets all the vertices
getEdges()	Gets all the edges

Listed below are two common usage scenarios of graphs:

Find the shortest path where path is defined as a sequence of edges which connect a sequence of vertices . Shortest path is used in a weighted graph to find the path that results in the shortest path from a source node to a destination node. It is used to find shortest routes, profitable routes etc.
Detect a cycle in a graph. Cycle consists of a sequence of vertices starting and ending at the same vertex with no repetitions of vertices and edges other than the starting and ending vertex

Hash Table

A bank wants to store and retrieve the details of its 1 million customers. Suppose the key that identifies each customer record is the customer name followed by the 11 digit account number. How many comparisons will be required to identify a customer record given the key?

The search will involve character by character searching of each customer name followed by the 11 digit account number. i.e. 26 possibilities for each character of a variable length string followed by 10 possibilities for each of the 11 digits.
In these kind of situations, hashing can be used to arrive at a fixed length shorter hash value from the key. Searching a fixed length shorter hash value is definitely much faster than searching for the original key value.

Hashing is the process of transforming a set of characters (key) into a shorter fixed length integer value. This shorter fixed length integer value which represents the original set of characters (key) is known as hash value or hash. A hash function will be used to generate the hash value from the original set of characters (key). Various algorithms may be used to arrive at the hash function

Key(Input)	Value	Hash(Output)
ISR	Israel	(ord("I")+ord("S")+ ord("R"))%5	(73+83+82)%5	238%5	3
PER	Peru	(ord("P")+ ord("E") + ord("R"))%5	(80+69+82)%5	231%5	1
IND	India	(ord("I")+ord("N")+ ord("D"))%5	(73+78+68)%5	219%5	4
FJI	Fiji	(ord("F")+ord("J") +ord("I"))%5	(70+74+73)%5	217%5	2
CAN	Canada	(ord("C")+ord("A") +ord("N"))%5	(67+65+78)%5	210%5	0

h(k) = (ord(k[i])) % 5, where n=2 as there are 3 characters in the input key of this example and ord(k[i]) is a python function which returns the ASCII value of character at the ith position in k.

Points to Note:h(k) = (ord(k[i])) % 5, where n=2 as there are 3 characters in the input key of this example

Hash function will always generate the same hash value (output) for a given key (input).
Keys have to be unique.
A given key will have only one value in the key-value pair.

SWE

Sweden

(ord("S")+ord("W") +ord("E"))%5

(83+87+69)%5

239%5

Two keys (IND and SWE) have generated the same hash value. That means hash function may compute same hash value for multiple keys and this is known as collision in hashing. This occurs because the number of possibilities in input (key) is much greater than the number of possibilities in the output (hash value).

Key(Input)	Value	Hash(Output)
ISR	Israel	(ord("I")+ord("S")+ ord("R"))%5	(73+83+82)%5	238%5	3
PER	Peru	(ord("P")+ ord("E") + ord("R"))%5	(80+69+82)%5	231%5	1
IND	India	(ord("I")+ord("N")+ ord("D"))%5	(73+78+68)%5	219%5	4
FJI	Fiji	(ord("F")+ord("J") +ord("I"))%5	(70+74+73)%5	217%5	2
CAN	Canada	(ord("C")+ord("A") +ord("N"))%5	(67+65+78)%5	210%5	0
SWE	Sweden	(ord("S")+ord("W") +ord("E"))%5	(83+87+69)%5	239%5	4

In this example, three letter abbreviation exists for all the countries in the world whereas the hash value can be only between 0 – 4.

Collisions are inevitable, however number of collisions depends on the goodness of the hash function.

Hash table is a data structure that helps to map the keys to its value. It is primarily an array which stores the reference to the actual value based on the hash. In the hash table, hash refers to its index and the number of elements in the hash table is based on the hash function. Thus hash table can be searched very quickly for the actual value based on the hash obtained from its key.

One of the techniques that can be used for handling collision is known as separate chaining. In this case, instead of hash table containing a reference to one value, it will maintain a reference to a linked list. When more than one key maps to the same hash, its values are added as nodes to the corresponding linked list.

we want to find the value corresponding to IND, how will you decide whether it is India or Sweden?

Here the key-value pair forms the data part of the linked list.

put(): This operation is used to put a key-value pair into the hash table based on the key and the hash

Algorithm Steps:

1. Identify the hash by applying the hash function on the given key
2. Locate the hash in the hash table
3. Create a new node with the given key-value  pair to be linked to the hash
4. Traverse through the linked list corresponding to the hash until its end
5. Place the new node as the last node of the linked list

get(): This operation is used to retrieve a value based on its key and hash.

Algorithm Steps:

1. Identify the hash by applying the hash function on the given key
2. Locate the hash in the hash table
3. Search its corresponding linked list for a node with the given key
4. When found, return its corresponding value
5. If a node with key is not found, display "Node not found" and return

class Stack:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__top=-1

def is_full(self):

if(self.__top==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__top==-1):

return True

return False

def push(self,data):

if(self.is_full()):

print("The stack is full!!")

else:

self.__top+=1

self.__elements[self.__top]=data

def pop(self):

if(self.is_empty()):

print("The stack is empty!!")

else:

data= self.__elements[self.__top]

self.__top-=1

return data

def display(self):

if(self.is_empty()):

print("The stack is empty")

else:

index=self.__top

while(index>=0):

print(self.__elements[index])

index-=1

def get_top(self):

return self.__top

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__top

while(index>=0):

msg.append((str)(self.__elements[index]))

index-=1

msg=" ".join(msg)

msg="Stack data(Top to Bottom): "+msg

return msg

class Queue:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__rear=-1

self.__front=0

def is_full(self):

if(self.__rear==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__front>self.__rear):

return True

return False

def enqueue(self,data):

if(self.is_full()):

print("Queue is full!!!")

else:

self.__rear+=1

self.__elements[self.__rear]=data

def dequeue(self):

if(self.is_empty()):

print("Queue is empty!!!")

else:

data=self.__elements[self.__front]

self.__front+=1

return data

def display(self):

for index in range(self.__front, self.__rear+1):

print(self.__elements[index])

def get_front(self):

return self.__front

def get_rear(self):

return self.__rear

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__front

while(index<=self.__rear):

msg.append((str)(self.__elements[index]))

index+=1

msg=" ".join(msg)

msg="Queue data(Front to Rear): "+msg

return msg

def fun(input_stack):

output_queue=Queue(input_stack.get_max_size())

temp_queue=Queue(input_stack.get_max_size())

while(not input_stack.is_empty()):

data=input_stack.pop()

if(data%2==0):

output_queue.enqueue(data)

else:

temp_queue.enqueue(data)

temp_data=0

while(not temp_queue.is_empty()):

temp_data+=temp_queue.dequeue()

output_queue.enqueue(temp_data)

output_queue.display()

sample= Stack(5)

sample.push(3)

sample.push(7)

sample.push(2)

sample.push(5)

sample.push(1)

fun(sample)

class Stack:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__top=-1

def is_full(self):

if(self.__top==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__top==-1):

return True

return False

def push(self,data):

if(self.is_full()):

print("The stack is full!!")

else:

self.__top+=1

self.__elements[self.__top]=data

def pop(self):

if(self.is_empty()):

print("The stack is empty!!")

else:

data= self.__elements[self.__top]

self.__top-=1

return data

def display(self):

if(self.is_empty()):

print("The stack is empty")

else:

index=self.__top

while(index>=0):

print(self.__elements[index])

index-=1

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__top

while(index>=0):

msg.append((str)(self.__elements[index]))

index-=1

msg=" ".join(msg)

msg="Stack data(Top to Bottom): "+msg

return msg

class Queue:

def __init__(self,max_size):

self.__max_size=max_size

self.__elements=[None]*self.__max_size

self.__rear=-1

self.__front=0

def is_full(self):

if(self.__rear==self.__max_size-1):

return True

return False

def is_empty(self):

if(self.__front>self.__rear):

return True

return False

def enqueue(self,data):

if(self.is_full()):

print("Queue is full!!!")

else:

self.__rear+=1

self.__elements[self.__rear]=data

def dequeue(self):

if(self.is_empty()):

print("Queue is empty!!!")

else:

data=self.__elements[self.__front]

self.__front+=1

return data

def display(self):

for index in range(self.__front, self.__rear+1):

print(self.__elements[index])

def get_max_size(self):

return self.__max_size

#You can use the below __str__() to print the elements of the DS object while debugging

def __str__(self):

msg=[]

index=self.__front

while(index<=self.__rear):

msg.append((str)(self.__elements[index]))

index+=1

msg=" ".join(msg)

msg="Queue data(Front to Rear): "+msg

return msg

def fun(input_stack):

num=input_stack.get_max_size()-1

num1=1

while(num>0):

top_element=input_stack.pop()

temp_stack=Stack(input_stack.get_max_size())

num2=1

while(num2<=num1):

element=input_stack.pop()

temp_stack.push(element+top_element)

num2+=1

while(not temp_stack.is_empty()):

input_stack.push(temp_stack.pop())

input_stack.push(top_element)

num1+=1

num-=1

return input_stack

sample= Stack(5)

sample.push(8)

sample.push(2)

sample.push(6)

sample.push(7)

sample.push(10)

result_stack=fun(sample)

result_stack.display()

Author Details

InShortView