## DEV Community

Shahriyar Al Mustakim Mitul

Posted on

# Data Structure & Algorithm: Queues

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
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())
``````