//Useful for background tasks, uploading resources, print/task //Can be impleneted with array (use push/shift or unshift/pop) or queue class //Again any time you use shift/unshift, you have O(N) //FIFO class Node: def __init__(self, value, next=None): self.value = value self.next = next class Queue: def __init__(self, first=None, last=None, size=0): self.first = first self.last = last self.size = size #add to end of queue (similar to append or push) and returns size def enqueue(self, value): new_node = Node(value) if self.first == None: self.first = new_node self.last = new_node else: self.last.next = new_node self.last = new_node self.size += 1 return self.size #remove from beginning of queue def dequeue(self): if self.first == None: return None temp = self.first if self.first == self.last: self.last = None #set 1st property to be original first's next self.first = self.first.next self.size -= 1 return temp.value #useful to visualize any other function works def print_queue_to_list(self): result = [] current = self.first while current: result.append(current.value) current = current.next print(result) s = Queue() s.enqueue(1) s.enqueue(2) s.enqueue(3) s.print_queue_to_list() >> [1, 2, 3] s.dequeue() s.print_queue_to_list() >> [2, 3] // Big O: // Insertion and Removal: O(1) **this is mainly what stacks are good for // Access and Search: O(N) //Recall with array implenetation, insertion and removal is not constant
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter