Python Program to Implement Queue using Linked List

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

Problem Description

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

Problem Solution

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.

Program/Source Code

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
Program Explanation

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.

advertisement
advertisement
Runtime Test Cases
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 – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.