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