Data Structure/ Ch03:BasicDataStructure(2)

📚 The Start of Recording TIL Summer ‘24 : Why Did I Start This Project? 🚀

🔔 Don't Miss: Continous Records of TIL '25 (Still On-Going!) 🌟

✨ A New Chapter in TIL '25: Reflecting, Growing, and Moving Forward 📖

Basic Data Structure - 2. Queue

A Queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commly called the “front.” The most recently added item in the queue will be at the end of the collection, and the longest is at the front.

• FIFO principle : First-In, First-Out

Simulation : Hot Potato Game

class Queue:
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return self.items == []
    
    def enqueue(self, item):
        self.items.insert(0,item)
        
    def dequeue(self):
        return self.items.pop()
    
    def size(self):
        return len(self.items)

def hotPotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)
        
    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())
            
        simqueue.dequeue()
    
    return simqueue.dequeue()
            

# Testing code
hotPotato(["Bill", "David", "Susan", "Jane", "Kane", "Brad"], 7)

# Output
'Susan'

Simulation : Printing Tasks

1. Create a quueue of print tasks. Each task will be given a timestamp upon its arrival. The queue is empty to start.
2. For each second (currentSecond):
   • Does a new print task get created? If so, add it to the queue with the currentSecond as the timestamp.
   • If the printer is not busy and if a task is waiting,
     • Remove the next task from the print queue and assign it to the printer.
     • Subtract the timestamp from the currentSecond to compute the waiting time for that task.
     • Append the waiting time for that task to a list for later processing.
     • Based on the number of pages in the print task, figure out how much time will be required.
   • The printer now does one second of printing if necessary. It also subtracts one second from the time required for that task.
   • If the task has been completed, in other words the time required has reached zero, the printer is no longer busy.
3. After the simulation is complete, compute the average waiting time from the list of waiting times generated.

# Listing 3.11: Printer Queue Simulation - The Printer Class

class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0
        
    def tick(self):
        if self.currentTask != None:
            self.timeRemaining = self.timeRemaining - 1
            if self.timeRemaining <= 0:
                self.currentTask = None
                
    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False
    
    def startNext(self, newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages() * 60/self.pagerate

# Listing 3.12 : Printer Queue Simulation - The Task Class

import random
class Task:
    def __init__(self, time):
        self.timestamp = time
        self.pages = random.randrange(1,21)
    
    def getStamp(self):
        return self.timestamp
    
    def getPages(self):
        return self.pages
    
    def waitTime(self, currenttime):
        return currenttime - self.timestamp

# Listing 3.13 : Printer Queue Simulation - The Main Simulation

def simulation(numSeconds, pagesPerMinute):
    
    labprinter = Printer(pagesPerMinute)
    printQueue = Queue()
    waitingtimes = []
    
    for currentSecond in range(numSeconds):
        
        if newPrintTask():
            task = Task(currentSecond)
            printQueue.enqueue(task)
            
        if (not labprinter.busy()) and (not printQueue.isEmpty()):
            nexttask = printQueue.dequeue()
            waitingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startNext(nexttask)
            
        labprinter.tick()
        
    averageWait = sum(waitingtimes)/len(waitingtimes)
    print("Average Wait %6.2f secs %3d tasks remaining." %(averageWait, printQueue.size()))
    
    
def newPrintTask():
    num = random.randrange(1,181)
    if num == 180:
        return True
    else:
        return False

# Testing code..
for i in range(10):
    simulation(3600,10)

Average Wait  22.13 secs   0 tasks remaining.
Average Wait  12.67 secs   0 tasks remaining.
Average Wait   9.07 secs   0 tasks remaining.
Average Wait  44.12 secs   0 tasks remaining.
Average Wait  53.00 secs   0 tasks remaining.
Average Wait  28.91 secs   0 tasks remaining.
Average Wait  14.13 secs   0 tasks remaining.
Average Wait   7.33 secs   0 tasks remaining.
Average Wait  34.06 secs   0 tasks remaining.
Average Wait  14.39 secs   0 tasks remaining.