# Queue Implemented as Single Linked List

Note: I do know that Python libraries provide a Linked list and Stack. This implementation has been done to practice Python and some of the data structures and algorithms.

I have implemented Queue as a Single linked list. Feel free to make suggestions. Note: The code works.

Targeted Big O:

Search: O(n), EnQueue and DeQueue: O(1)

Methods:

en_queue(value): insert values
de_queue(): remove values
is_empty(): check to see if Queue is empty
peek_front(): look at what head points to without removing
peek_back(): look at what tail points to without removing
search(value): check to see if a value is in the Queue
length(): return size


Classes:

class Node:
def __init__(self, value):
self.data = value
self.front = None

class Queue:
def __init__(self):
self.tail = None
self.count = 0

def en_queue(self, value):
new_node = Node(value)

if self.tail is not None:
# make the front attribute of old node point to new node
self.tail.front = new_node

else:
# if first ever node in Queue both front and tail will point to it

self.tail = new_node
self.count += 1

def de_queue(self):
if not self.is_empty():
# point head to next node
print("sucess")
self.count -= 1
else:
print("Empty QUEUE")

def __iter__(self):
while node:
yield node
node = node.front

def is_empty(self):
if self.head is None and self.tail is None:
return True
else:
return False

def peek_front(self):

def peek_back(self):
return self.tail.data

def queue_search(self, value):
while p is not None:
# make p reference to next node
if p.front is not None:
if p.data == value:
print("Found value")
return p.data
p = p.front
else:
print("fail")
return 0

def length(self):
return self.count


Test:

from stack_Queue import Queue

def main():

print("-------Test Queue---------")
print("-------Test En Queue------")
my_queue = Queue()
test_list = [1, 2, 3, 4, -2000000, 'a', 500000, 50]

for i in test_list:
my_queue.en_queue(i)
print("-------En Queue Done-------")
for i in my_queue:
print(i.data)
print("------Queue Print Done-----")
print("------Queue Print Done-----")
print(my_queue.peek_back())
print(my_queue.peek_front())
print("----------De Queue---------")
my_queue.de_queue()
print("--------De Queue Done------")
for i in my_queue:
print(i.data)
print("-----Queue Print Done------")
print("-----Test search-------")
x = my_queue.queue_search('a')
print(x)
print("-------Full De Queue-------")
while my_queue.length() != 0:
my_queue.de_queue()
print("--------De Queue Done------")
for i in my_queue:
print(i.data)
print("-----Queue Print Done------")

if __name__ == "__main__":
main()


Result:

-------Test Queue---------
-------Test En Queue------
-------En Queue Done-------
1
2
3
4
-2000000
a
500000
50
------Queue Print Done-----
------Queue Print Done-----
50
1
----------De Queue---------
sucess
--------De Queue Done------
2
3
4
-2000000
a
500000
50
-----Queue Print Done------
-----Test search-------
Found value
a
-------Full De Queue-------
sucess
sucess
sucess
sucess
sucess
sucess
sucess
--------De Queue Done------
-----Queue Print Done------

Process finished with exit code 0

• My points from my other answer will be applicable to this as well. I am not sure about posting it here again. – Ashwini Chaudhary Aug 25 '17 at 4:33
• yes yes indeed and i will implement them to this as well, i just did not want to create clutter, and taught since they are a bit different to post them separate – BlooB Aug 25 '17 at 4:47

In addition to the points I had mentioned in my previous answer to your Stack implementation.

Your Queue is not introspectable right now as it lacks __repr__ method. Due to this you won't be able to view its items easily. Hence you could add __repr__ to both Node and Queue class(same applicable to your Stack class in other question).

class Node:
def __init__(self, value):
self.data = value
self.front = None

def __repr__(self):
return repr(self.data)

class EmptyQueueException(Exception):
pass

class Queue:
def __init__(self):
self.tail = None
self.count = 0

def en_queue(self, value):
new_node = Node(value)

if self.tail is not None:
# make the front attribute of old node point to new node
self.tail.front = new_node
else:
# if first ever node in Queue both front and tail will point to it

self.tail = new_node
self.count += 1

def de_queue(self):
if self:
# point head to next node
self.count -= 1
else:
raise EmptyQueueException()

def peek_front(self):
if self:
raise EmptyQueueException()

def peek_back(self):
if self:
return self.tail.data
raise EmptyQueueException()

def __iter__(self):
while node is not None:
yield node
node = node.front

def __bool__(self):
return not (self.head is None and self.tail is None)

def __contains__(self, value):
return value in (node.data for node in self)

def __len__(self):
return self.count

def __repr__(self):
return 'Queue<{nodes}>'.format(nodes=', '.join(repr(node) for node in self))


Demo:

>>> my_queue
Queue<1, 2, 3, 4, -2000000, 'a', 500000, 50>
>>> my_queue.de_queue()  # Probably want to return the value as well?
>>> my_queue
Queue<2, 3, 4, -2000000, 'a', 500000, 50>
>>> my_queue.peek_back()
50
>>> 'a' in my_queue
True
>>> 'spam' in my_queue
False
>>> bool(my_queue)
True
>>> len(my_queue)
7
>>> len(Queue())
0
>>> bool(Queue())
False
>>> Queue().peek_back()
---------------------------------------------------------------------------
EmptyQueueException                       Traceback (most recent call last)
...


In en_queue(), the pythonic way to express if self.tail is not None: is if self.tail:

• If the intention is to explicitly check against None then is not None is fine. – Ashwini Chaudhary Aug 25 '17 at 4:31