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