Python Program to Implement Queue using Linked List

This is a Python program to implement a queue using a linked list.

The program creates a queue and allows the user to perform enqueue and dequeue operations on it.

1. Create a class Node with instance variables data and next.
2. Create a class Queue with instance variables head and last.
3. The variable head points to the first element in the linked list while last points to the last element.
4. Define methods enqueue and dequeue inside the class Queue.
5. The method enqueue adds a node at the end of the linked list.
6. The method dequeue returns the data of the node at the front of the linked list and removes the node. It returns None if there are no nodes.
7. Create an instance of Queue and present a menu to the user to perform operations on the queue.

Here is the source code of a Python program to implement a queue using a linked list. The program output is shown below.

class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
 
class Queue:
    def __init__(self):
        self.head = None
        self.last = None
 
    def enqueue(self, data):
        if self.last is None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.next = Node(data)
            self.last = self.last.next
 
    def dequeue(self):
        if self.head is None:
            return None
        else:
            to_return = self.head.data
            self.head = self.head.next
            return to_return
 
a_queue = Queue()
while True:
    print('enqueue <value>')
    print('dequeue')
    print('quit')
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
    if operation == 'enqueue':
        a_queue.enqueue(int(do[1]))
    elif operation == 'dequeue':
        dequeued = a_queue.dequeue()
        if dequeued is None:
            print('Queue is empty.')
        else:
            print('Dequeued element: ', int(dequeued))
    elif operation == 'quit':
        break

1. An instance of Queue is created.
2. The user is presented with a menu to perform enqueue and dequeue operations on the queue.
3. The chosen operation is performed by calling the corresponding method.

Case 1:
enqueue <value>
dequeue
quit
What would you like to do? enqueue 3
enqueue <value>
dequeue
quit
What would you like to do? enqueue 4
enqueue <value>
dequeue
quit
What would you like to do? dequeue
Dequeued element:  3
enqueue <value>
dequeue
quit
What would you like to do? dequeue
Dequeued element:  4
enqueue <value>
dequeue
quit
What would you like to do? dequeue
Queue is empty.
enqueue <value>
dequeue
quit
What would you like to do? quit
 
Case 2:
enqueue <value>
dequeue
quit
What would you like to do? dequeue
Queue is empty.
enqueue <value>
dequeue
quit
What would you like to do? enqueue 5
enqueue <value>
dequeue
quit
What would you like to do? dequeue
Dequeued element:  5
enqueue <value>
dequeue
quit
What would you like to do? quit

Sanfoundry Global Education & Learning Series – 1000 Python Programs.

If you wish to look at all Python Programming examples, go to 1000 Python Programs.