Question

Give a complete implementation of the queue ADT using a singly linked list that includes a header sentinel (in Python).

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Note: Please maintain proper code spacing (indentation), just copy the code part and paste it in your compiler/IDE directly, no modifications required.

#code

''' a Node class to represent a single node on the linked list '''
class Node:
    def __init__(self, data, next=None):
        self.data=data
        self.next=next

    def set_next(self, next):
        self.next=next

    def get_next(self):
        return self.next

    def get_data(self):
        return self.data

    def set_data(self, data):
        self.data=data

''' Queue class implemented using a linked list using Node class'''
class Queue:
    #constructor
    def __init__(self):
        #initializing a sentinel/dummy head node
        self._head=Node(None)

    #method to add an element to the back of queue
    def enqueue(self, data):
        #creating a node with data
        node=Node(data)
        #taking self._head as prev
        prev=self._head
        #taking first node (if exists) as curr
        curr=self._head.get_next()
        #looping until curr becomes None
        while curr is not None:
            #storing curr in prev
            prev=curr
            #advancing curr
            curr=curr.get_next()
        #simply setting node as next of prev
        prev.set_next(node)

    #removes and returns the front element from queue
    def dequeue(self):
        #if queue is empty, returning None
        if self.isEmpty():
            return None
        #storing data at first node (next of dummy head)
        data=self._head.get_next().get_data()
        #removing the node between head and head.next.next
        self._head.set_next(self._head.get_next().get_next())
        #returning removed item
        return data

    #returns the front element without removing
    def front(self):
        if self.isEmpty():
            #empty
            return None
        #returning data of first node
        return self._head.get_next().get_data()

    #returns True if queue is empty
    def isEmpty(self):
        #checking if head is pointing to None
        return self._head.get_next() is None
#end of Queue class


#code for testing
if __name__ == '__main__':
    #creating a queue, adding numbers from 0 to 9
    q=Queue()
    for i in range(10):
        q.enqueue(i)
    #looping and dequeueing each value, it should be in the order
    #0...9
    while not q.isEmpty():
        print(q.dequeue())

#output