pythonqueuedequeenqueue

Creating a Queue Class


I am trying to implement a queue class using linked implementation that has the functions enqueue, dequeue, and length. To my understand of queues, when first implemented the queue points to head and tail nodes which initially points to None. As items are added to the queue, a node points to the item, the head node remains unchanged, and the tail node points to the new item.

I've tried to implement this with the following code in python but it doesn't seem to be working. I'm not sure if my logic is wrong, or it's the coding that's wrong, or both?

class Queue:
    def __init__(self, data=None):
        # Initialize this queue, and store data if it exists
        self.data = data
        self.head = None
        self.tail = None
        self.node = None
        self.length = 0

    def enqueue(self, data):              
        if self.head == None:
            self.head = Queue(data)
            self.tail = self.head
        else:
            self.node = data
            self.tail = self.node
            data = self.data
        self.length += 1

    def dequeue(self):
        item = self.head.item
        self.head = self.head.next
        self.length -= 1
        return item

    def __len__(self):
        return self.length

Solution

  • I'd avoid declaring an instance of a class inside the definition of a class. Declaring self.head = Queue(data) is asking for trouble, in my mind, because that could lead to declarations of self.head.head, and self.head.head.head... You get the idea. Instead, I would maybe separate things out a bit. Also, notice that you didn't declare self.head.next or self.head.item, even though you called them in your methods.

    Perhaps declare two classes, one for Nodes, and the other for a Queue built out of Nodes? That would simplify things a bit.

    Here's how I would build a Queue in Python, credit my own:

    from typing import Iterable
    
    class Node:
        def __init__(self, data=None):
            self.data = data
            self.next = None
    
        def __call__(self):
            return self.data
    
    class Queue:
        def __init__(self, x=None):
            assert isinstance(x, Node) or (x == None) or isinstance(x, Iterable)
            if isinstance(x, Iterable):
                self.head = Node(x[0])
                self.tail = Node(x[0])
                self.length = 1
                self.to_queue(x[1:])
            else:
                self.head = x
                self.tail = x
                self.length = 1 if x else 0
    
        def enqueue(self, data):
            tmp = self.head
            self.head = Node(data)
            self.head.next = tmp
            self.length += 1
    
        def dequeue(self):
            if self.length <= 0:
                print("empty Queue")
                return
            tmp = self.head
            for i in range(self.length-2):
                tmp = tmp.next
            self.tail = tmp
            self.tail.next = None
            self.length -= 1
            if self.length == 0:
                self.head = None
                self.tail = None
    
        def to_queue(self, vals):
            for i in vals:
                self.enqueue(i)
    
        def __call__(self):
            tmp = self.head
            while (tmp):
                print(tmp.data, end=" ")
                tmp = tmp.next
    
        def __len__(self):
            return self.length
    

    Note that this is all unnecessary for production code, as you could just use a deque, for example, from the collections module