#demonstrates queue
# it's better to reuse the code available by the Python team to create queue using Queue or collections.dequeue,
#but as we have to create a manual Queue data strucutre, thus using list instead
class Queue:
def __init__(self, s): #special method to create objects
#with instances customized to a specific initial state
#since private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._maxSize = s
self._front = 0
self._rear = -1
self._nItems = 0
self._queVect = [None] * self._maxSize
def insert(self, j): #put item at rear of queue
if self._rear == self._maxSize - 1: #deal with wraparound
self._rear = -1
self._rear += 1#increment rear
self._queVect[self._rear] = j #insert
self._nItems += 1#one more item
def remove(self): #take item from front of queue
temp = self._queVect[self._front] #get value
self._front += 1#incr front
if self._front == self._maxSize: #deal with wraparound
self._front = 0
self._nItems -= 1#one less item
return temp
def peekFront(self): #peek at front of queue
return self._queVect[self._front]
def isEmpty(self): #true if queue is empty
return self._nItems == 0
def isFull(self): #true if queue is full
return self._nItems == self._maxSize
def size(): #number of items in queue
return self._nItems
#end class Queue
theQueue = Queue(5) #queue holds 5 items
theQueue.insert(10) #insert 4 items
theQueue.insert(20)
theQueue.insert(30)
theQueue.insert(40)
theQueue.remove() #remove 3 items
theQueue.remove() # (10, 20, 30)
theQueue.remove()
theQueue.insert(50) #insert 4 more items
theQueue.insert(60) # (wraps around)
theQueue.insert(70)
theQueue.insert(80)
while not theQueue.isEmpty(): #remove and display all items
n = theQueue.remove() #(40, 50, 60, 70, 80)
print n,
#end
#it's better to reuse the code available by the Python team to create queue using Queue or collections.dequeue,
#but as we have to create a manual Queue data strucutre, thus using list instead
class Queue:
def __init__(self, s): #special method to create objects
#with instances customized to a specific initial state
#since private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._maxSize = s + 1
self._front = 0
self._rear = -1
self._queVect = [None] * self._maxSize
def insert(self, j): #put item at rear of queue
if self._rear == self._maxSize - 1:
self._rear = -1
self._rear += 1
self._queVect[self._rear] = j
def remove(self): #take item from front of queue
temp = self._queVect[self._front]
self._front += 1
if self._front == self._maxSize:
self._front = 0
return temp
def peek(self): #peek at front of queue
return self._queVect[self._front]
def isEmpty(self): #true if queue is empty
return (self._rear + 1 == self._front) or (self._front + self._maxSize - 1 == self._rear)
def isFull(self): #true if queue is full
return (self._rear + 2 == self._front) or (self._front + self._maxSize - 2 == self._rear)
def size(self): #assumes queue not empty
if self._rear >= self._front: #contiguous sequence
return self._rear - self._front + 1
else: #broken sequence
return (self._maxSize - self._front) + (self._rear + 1)
#end class Queue
#demonstrates priority queue
#it's better to reuse the code available by the Python team to create priority queue using Queue,
#but as we have to create a manual Queue data strucutre, thus using list instead
class PriorityQ:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#since private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
#list in sorted order, from max at 0 to min at size-1
self._queVect = []
def insert(self, item): #insert item
if not self._queVect: #if no items,
self._queVect.append(item) #insert at 0
else: #if items
for j, val in enumerate(self._queVect):
if item < val:
pass
else:
break
else:
j += 1
self._queVect.insert(j, item) #insert it
#end else self._queVect = True
#end insert
def remove(self): #remove minimum item
return self._queVect.pop()
def peekMin(self): #peek at minimum item
return self._queVect[-1]
def isEmpty(self): #true if queue is empty
return not self._queVect
#end class PriorityQ
thePQ = PriorityQ() #priority queue
thePQ.insert(30) #unsorted insertions
thePQ.insert(50)
thePQ.insert(10)
thePQ.insert(40)
thePQ.insert(20)
while not thePQ.isEmpty():
#sorted removals
item = thePQ.remove()
print item, #10, 20, 30 ,40, 50
#end