class Node:
def __init__(self, data):
self.cargo = data
self.next = None
def __str__(self):
return "{}".format(self.cargo)
class Queue:
def __init__(self):
self.length = 0
self.head = None
self.tail = None
def is_empty(self):
return self.length == 0
def insert(self, data):
node = Node(data)
if not self.head: # empty queue
self.head = self.tail = node
else:
# add new node as the last node
self.tail.next = node
self.tail = node
self.length += 1
def remove(self):
data = self.head.cargo
# make the head point to 2nd element
self.head = self.head.next
self.length -= 1
# update tail if the queue becomes empty after removing the first node
if self.length == 0:
self.tail = None
return data
def __len__(self):
return self.length
q = Queue()
q.insert(1)
q.insert(2)
q.insert('a')
assert q.remove() == 1
assert len(q) == 2
q.insert(100)
assert q.remove() == 2
class PriorityQueue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def insert(self, data):
self.items.append(data)
def remove(self):
maxi = 0
for i in range(1, len(self.items)):
if self.items[i] > self.items[maxi]:
maxi = i
item = self.items[maxi]
del self.items[maxi]
return item
def __len__(self):
return len(self.items)
q = PriorityQueue()
for num in [11, 12, 14, 13]:
q.insert(num)
while not q.is_empty():
print(q.remove())
14 13 12 11
class Golfer:
def __init__(self, name, score):
self.name = name
self.score = score
def __str__(self):
return "{0:16}: {1}".format(self.name, self.score)
# lowest score gets highest priority
def __gt__(self, other):
return self.score < other.score # lower score has the higher priority
tiger = Golfer('Tigher Woods', 40)
phil = Golfer('Phil Mickelson', 30)
hal = Golfer('Hal Sutton', 20)
pq = PriorityQueue()
pq.insert(tiger)
pq.insert(phil)
pq.insert(hal)
print(pq.remove())
Hal Sutton : 20
while not pq.is_empty():
print(pq.remove())
Phil Mickelson : 30 Tigher Woods : 40