Data Structure & Algorithm: Queues
Tags: dsalgo
Published: 2022-05-24 11:25:08

Queues are something like staying in a line

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8d1m8zwiw8tp032sjv89.png)

here the first person is given most priority [FIFO: First inter first out] . First people gets out first (Dequeue)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/18ba02x5kvtvoc9y97ev.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l63wxvh0ofygnlu0exg1.png)
Also, a person is added at the last (Enqueue)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5u938z1nkqvj6jdxcija.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/11b82rfronle0gpayt1o.png)

Now , lets learn from where we need to Enqueue & Dequeue in a Linked List:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6se5e9ejei434dzph6lw.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/28nw42dsj6oych5a8p51.png)
 
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. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bvett5lrp0fazhagn0v5.png)

But adding it back is just O(1) because , you just appoint None to it

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fq7c1dfn9i4plhwtlt1a.png)

Again, removing from the left side/beginning is O(1) because you just add a node .

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l6p1y59dzghlfi95fh41.png)
Also, adding it back is O(1)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0d0m3rfwql6v4lup9zxy.png)

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).
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sjfbjgtlkwtxqtx8sqs4.png)
So, Enqueue from right end (Last) and Dequeue from left end (beginning) 

Comparing it to Linked List, we will assume our Queue as this

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p5dh3ssbkfgl6cupu16u.png)

**_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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5c2tnks8dyuvs5zm403a.png)
to this

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wu86z7q3pk0xba830e20.png)

Case 1:
When we have nothing in queue.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mqcr3orxs8427ja2893l.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9tdfxydzyvzsykw2ux81.png)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/suoea2srng783om5mvri.png)
  

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bpuvxtmg0evjiqxzc4lc.png)
  
 
Case 2:
Already have items in the list

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y910av0v5b0t268n4nwu.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x9hcl81gtvfa0kt1zpa6.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8s74d81x88d4alxu3knb.png)


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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s4711mv5hjoct4oypo06.png)
to this

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9wgkq7oef38o5ck95vtz.png)

Case 1:
When we have nothing in queue

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3td8szjaesvxphovn4x2.png)

Case 2:
When we have 1 node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/60prtzayy3g9eqtl2m6i.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mmbjtvla0ntjaogfg60w.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a6udbyu7rno6s0qwczpg.png)
Case 3:
When we have many nodes in queue 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b1l2ejok2kjw17uscj26.png)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/07lhv396xb5nix2ovy68.png)

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


<img src="https://c.tenor.com/Tvd3VKwtse0AAAAC/cat-cute.gif">