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
Videos
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
Another approach could be to implement the queue as two stacks:
class Stack():
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if len(self.items) == 0:
raise IndexError("Can't pop from an empty stack!")
return self.items.pop(len(self.items) - 1)
def isEmpty(self):
return len(self.items) == 0
class Queue():
def __init__(self):
self.stack1 = Stack()
self.stack2 = Stack()
def enqueue(self, item):
self.stack1.push(item)
def dequeue(self):
if self.stack2.isEmpty():
while not self.stack1.isEmpty():
self.stack2.push(self.stack1.pop())
return self.stack2.pop()
def isEmpty(self):
return self.stack1.isEmpty() and self.stack2.isEmpty()
But I agree with the other answers that for any serious project, the standard library and its collections module should be preferred.
As Uri Goren astutely noted above, the Python stdlib already implemented an efficient queue on your fortunate behalf: collections.deque.
What Not to Do
Avoid reinventing the wheel by hand-rolling your own:
- Linked list implementation. While doing so reduces the worst-case time complexity of your
dequeue()andenqueue()methods to O(1), thecollections.dequetype already does so. It's also thread-safe and presumably more space and time efficient, given its C-based heritage. - Python list implementation. As I note below, implementing the
enqueue()methods in terms of a Python list increases its worst-case time complexity to O(n). Since removing the last item from a C-based array and hence Python list is a constant-time operation, implementing thedequeue()method in terms of a Python list retains the same worst-case time complexity of O(1). But who cares?enqueue()remains pitifully slow.
To quote the official deque documentation:
Though
listobjects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs forpop(0)andinsert(0, v)operations which change both the size and position of the underlying data representation.
More critically, deque also provides out-of-the-box support for a maximum length via the maxlen parameter passed at initialization time, obviating the need for manual attempts to limit the queue size (which inevitably breaks thread safety due to race conditions implicit in if conditionals).
What to Do
Instead, implement your Queue class in terms of the standard collections.deque type as follows:
from collections import deque
class Queue:
'''
Thread-safe, memory-efficient, maximally-sized queue supporting queueing and
dequeueing in worst-case O(1) time.
'''
def __init__(self, max_size = 10):
'''
Initialize this queue to the empty queue.
Parameters
----------
max_size : int
Maximum number of items contained in this queue. Defaults to 10.
'''
self._queue = deque(maxlen=max_size)
def enqueue(self, item):
'''
Queues the passed item (i.e., pushes this item onto the tail of this
queue).
If this queue is already full, the item at the head of this queue
is silently removed from this queue *before* the passed item is
queued.
'''
self._queue.append(item)
def dequeue(self):
'''
Dequeues (i.e., removes) the item at the head of this queue *and*
returns this item.
Raises
----------
IndexError
If this queue is empty.
'''
return self._queue.pop()
The proof is in the hellish pudding:
>>> queue = Queue()
>>> queue.enqueue('Maiden in Black')
>>> queue.enqueue('Maneater')
>>> queue.enqueue('Maiden Astraea')
>>> queue.enqueue('Flamelurker')
>>> print(queue.dequeue())
Flamelurker
>>> print(queue.dequeue())
Maiden Astraea
>>> print(queue.dequeue())
Maneater
>>> print(queue.dequeue())
Maiden in Black
It Is Dangerous to Go Alone
Actually, don't do that either.
You're better off just using a raw deque object rather than attempting to manually encapsulate that object in a Queue wrapper. The Queue class defined above is given only as a trivial demonstration of the general-purpose utility of the deque API.
The deque class provides significantly more features, including:
...iteration, pickling,
len(d),reversed(d),copy.copy(d),copy.deepcopy(d), membership testing with the in operator, and subscript references such asd[-1].
Just use deque anywhere a single- or double-ended queue is required. That is all.
You can keep head and tail node instead of a queue list in queue class
class Node:
def __init__(self, item = None):
self.item = item
self.next = None
self.previous = None
class Queue:
def __init__(self):
self.length = 0
self.head = None
self.tail = None
def enqueue(self, value):
newNode = Node(value)
if self.head is None:
self.head = self.tail = newNode
else:
self.tail.next = newNode
newNode.previous = self.tail
self.tail = newNode
self.length += 1
def dequeue(self):
item = self.head.item
self.head = self.head.next
self.length -= 1
if self.length == 0:
self.tail = None
return item