Queues are something like staying in a line
here the first person is given most priority [FIFO: First inter first out] . First people gets out first (Dequeue)
Also, a person is added at the last (Enqueue)
Now , lets learn from where we need to Enqueue & Dequeue in a Linked List:
Removing from the right side causes O(n) because
Deleting the last node of the Linked List involves checking the head for empty. If it is not empty, then check the head next for empty. If the head next is empty, then release the head, else traverse to the second last node of the list. Then, link the next of second last node to NULL and delete the last node.
But adding it back is just O(1) because , you just appoint None to it
Again, removing from the left side/beginning is O(1) because you just add a node .
Also, adding it back is O(1)
Therefore, we don't want to remove a node from last because it takes O(n) [Dequeue] but we can add one because it is O(1) [Enqueue]
again,
for the beginning of list, we can remove and add both because it takes O(1) .
As, we are going to add from the last in list O(1) , now we will remove from first O(1).
So, Enqueue from right end (Last) and Dequeue from left end (beginning)
Comparing it to Linked List, we will assume our Queue as this
Constructor
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
def __init__(self, value):
new_node = Node(value) #creating a node
#pointing the first & last to the new node
self.first = new_node
self.last = new_node
self.length = 1
#Prints the queue untill it finds None
def print_queue(self):
temp = self.first
while temp is not None:
print(temp.value)
temp = temp.next
the whole code would be:
#Creating a node
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
def __init__(self, value):
new_node = Node(value) #creating a node
#pointing the first & last to the new node
self.first = new_node
self.last = new_node
self.length = 1
#Prints the queue untill it finds None
def print_queue(self):
temp = self.first
while temp is not None:
print(temp.value)
temp = temp.next
#Creates a queue with node 4
my_queue = Queue(4)
my_queue.print_queue()
Enqueue
Adding a node at last
this
to this
Case 1:
When we have nothing in queue.
Case 2:
Already have items in the list
So, the code for this
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
def __init__(self, value):
new_node = Node(value)
self.first = new_node
self.last = new_node
self.length = 1
def print_queue(self):
temp = self.first
while temp is not None:
print(temp.value)
temp = temp.next
#Adding a node at last of queue
def enqueue(self, value):
new_node = Node(value)
#If there are no nodes in the queue
if self.first is None:
self.first = new_node
self.last = new_node
#If there are nodes in the queue
else:
self.last.next = new_node
self.last = new_node
self.length += 1
#Creating a queue with node 1
my_queue = Queue(1)
#Adding a node 2 at the last of queue
my_queue.enqueue(2)
my_queue.print_queue()
Dequeue
Removing from the beginning of the Linked List
to this
Case 1:
When we have nothing in queue
Case 2:
When we have 1 node
Case 3:
When we have many nodes in queue
So the total code is
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
def __init__(self, value):
new_node = Node(value)
self.first = new_node
self.last = new_node
self.length = 1
def print_queue(self):
temp = self.first
while temp is not None:
print(temp.value)
temp = temp.next
def enqueue(self, value):
new_node = Node(value)
if self.first is None:
self.first = new_node
self.last = new_node
else:
self.last.next = new_node
self.last = new_node
self.length += 1
return True
def dequeue(self):
#When we have no nodes in the queue
if self.length == 0:
return None
temp = self.first
#When we have only one node in the queue
if self.length == 1:
self.first = None
self.last = None
#When we have more than one node in the queue
else:
self.first = self.first.next
temp.next = None
self.length -= 1
return temp
my_queue = Queue(1)
my_queue.enqueue(2)
# (2) Items - Returns 2 Node
print(my_queue.dequeue())
# (1) Item - Returns 1 Node
print(my_queue.dequeue())
# (0) Items - Returns None
print(my_queue.dequeue())
Top comments (0)