# Implementing Queue using Linked List

ðŸ”—

The core property of a Queue data structure is that it allows adding new elements only from one end and allows removal of elements only from the other end. The endpoint at which new elements are added is the tail/rear end of queue and the endpoint from which the elements are removed is the front end of queue.

A Linked list can be used to create a queue abstract data structure by restricting addition of new elements only after the last node or tail node While removing an element, we remove the head node and set the next node as head node of the linked list. For retrieving the front element, we just return the head node. Below illustrations showcase this behavior:

• Initialize an empty queue using an empty linked list
• `None`
• Push element `4` into the queue
• `[4]->None`
• Now the front of the queue is `4`
• Push element `6` into the queue
• `[4]->[6]->None`
• Now the front of the queue still `4`
• Think of element `6` as behind element `4`
• Pop front/first element from the queue
• `[6]->None`
• Now the front element becomes `6`
• Add elements `8` and `9` to the queue
• `[6]->[8]->[9]->None`
• Element `6` is still the front of queue
• Let’s pop front/first element from the queue
• `[8]->[9]->None`
• Now element `8` is the front element of queue

Below is the implementation of Queue using a Linked List:

``````
class Node:
def __init__(self, value):
self.value = value
self.next = None

class Queue:
def __init__(self):
self.tail = None  # Initialize tail node

def is_empty(self):
# Queue is empty if head is None

def push(self, value):
new_node = Node(value)

if self.is_empty():
# If this is the first node,
# it becomes the head and tail node
self.tail = new_node
else:
# Make this node as the tail node
self.tail.next = new_node
self.tail = new_node

def pop(self):
if self.is_empty():
print("Queue is empty. Cannot pop.")
return None

# If the only element is removed,
# Make the head and node tail as None
self.tail = None
else:
# Set head to the next node

return popped_value

def front(self):
if self.is_empty():
print("Queue is empty.")
return None

# Let's now test the Queue Implementation:
queue = Queue()

print("Is queue empty?", queue.is_empty())

queue.push(1)
queue.push(2)
queue.push(3)

print("Is queue empty?", queue.is_empty())
print("Front element:", queue.front())

print("Popped element:", queue.pop())
print("Popped element:", queue.pop())
print("Popped element:", queue.pop())

print("Is queue empty?", queue.is_empty())

``````