1+ # Queue implementation using Linked List
2+ # Simply adding a new node to linked list as a next node
3+ # when we are adding a new element to the queue
4+ # And for dequeue we remove first node from linked list
5+ # All TC and SC is O(1) - constant
6+
7+ class Node :
8+ def __init__ (self , value = None ):
9+ self .value = value
10+ self .next = None
11+
12+ def __str__ (self ):
13+ return str (self .value )
14+
15+
16+ class LinkedList :
17+ def __init__ (self ):
18+ self .head = None
19+ self .tail = None
20+
21+ def __iter__ (self ):
22+ current_node = self .head
23+ while current_node :
24+ yield current_node
25+ current_node = current_node .next
26+
27+
28+ class Queue :
29+ def __init__ (self ):
30+ self .linked_list = LinkedList ()
31+
32+ def __str__ (self ):
33+ values = [str (l ) for l in self .linked_list ]
34+ return ' ' .join (values )
35+
36+
37+ def enqueue (self , value ):
38+ new_node = Node (value )
39+ # if its first node
40+ if self .linked_list .head == None :
41+ self .linked_list .head = new_node
42+ self .linked_list .tail = new_node
43+ else :
44+ self .linked_list .tail .next = new_node
45+ self .linked_list .tail = new_node
46+
47+
48+ def isEmpty (self ):
49+ # if head is empty it means the linked list is empty
50+ if self .linked_list .head == None :
51+ return True
52+ else :
53+ return False
54+
55+
56+ def dequeue (self ):
57+ if self .isEmpty ():
58+ return "Queue is empty"
59+ else :
60+ temp_node = self .linked_list .head
61+ # if there is only 1 node
62+ if self .linked_list .head == self .linked_list .tail :
63+ self .linked_list .head = None
64+ self .linked_list .tail = None
65+ else :
66+ # assign head to the second node
67+ self .linked_list .head = self .linked_list .head .next
68+ return temp_node
69+
70+
71+ def peek (self ):
72+ if self .isEmpty ():
73+ return "Queue is empty"
74+ else :
75+ return self .linked_list .head
76+
77+
78+ def delete (self ):
79+ # garbage collector removes all nodes
80+ # once the head and tail links are removed
81+ self .linked_list .head = None
82+ self .linked_list .tail = None
0 commit comments