The Queue that we created in class was based on the built-in List module in Pyth

ID: 3703209 • Letter: T

Question

The Queue that we created in class was based on the built-in List module in Python. The Queue class

can also be based on the Linked List structure discussed in class. For this assignment, implement a

queue using linked lists. Use the methods created for the list based queue as a guide. You will need to

decide which end to set up as front and which end to set up as back. Be sure to include all the methods

that are in the list based queue.

Also, write a test program to test your new queue. Be sure to include enough code to test all the

methods and write the code in such a way that whoever is looking at the output (me) will be able to

understand what the program is doing.

Here is the previous code based on based on the built-in List module. Now queue needs to be implemented using linked lists

from random import randint

class Customer:
def __init__(self,n):
self.numberOfItems=n

def __str__(self):
return str(self.numberOfItems)

def getNumberOfItems(self):
return self.numberOfItems

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 getInnerList(self):
return self.items

#Returns random checkout time, based on number of items
def checkOut(customer):

    items = customer.getNumberOfItems()
    if items <= 10:
        return randint(1, 5)

if items <= 20:
return randint(6, 10)

return randint(11, 15)

customersQueue = Queue()
totalCustomers = 30 #Change number of customers here

#Customers shopping..
for i in range(totalCustomers):
    #Each putting Between 1 to 25 items
    randomItemsQty = randint(1, 25)
    customer = Customer(randomItemsQty)

#Getting into queue for checkout
customersQueue.enqueue(customer)

#====Now all Customers having random qty of items are in Queue======

#CheckOut==========================
totalTime=0
totalCustomers = customersQueue.size()

while not(customersQueue.isEmpty()):

#A customer gets to the checkout every 1 – 5 minutes
totalTime+=randint(1,5)

#Picking a customer
customer = customersQueue.dequeue()

#Processing the customer
timeTaken = checkOut(customer)

totalTime+=timeTaken
#====================================

#Result=============================
averageWaitTime = totalTime/totalCustomers
print("Average wait time is "+str(averageWaitTime)+" minutes")
print("The number of customers left in the queue is ", customer)

Explanation / Answer

# class Node to represnet the node in the queue

class Node:

def __init__(self, initData):

# constructs a new node and initializes it to contain

# the given object (initData) and links to the given next

# and previous nodes.

self.data = initData

self.next = None

def getData(self):

# returns the data of the node

return self.data

def getNext(self):

# return the location of the next element, if present else None

return self.next

def setData(self, newData):

# sets the data of the node

self.data = newData

def setNext(self, newNext):

# sets the next pointer for the node

self.next= newNext

# class Queue to implement Queue as a linked list

class Queue:

# initialize the queue , set front and back pointers to None

# initially queue is empty

def __init__(self):

self.front = None

self.back = None

# checks if queue is empty

def isEmpty(self):

if(self.front == None):

return True

return False

# insert the element into the queue

# elements are inserted at the end of the queue

def enqueue(self,item):

newNode = Node(item) # creates a new node

# if queue is empty then make front and back point to this node

if(self.front == None):

self.front = newNode

self.back = newNode

else: # else make next of back point to this node and make newback point to this node

self.back.setNext(newNode)

self.back = newNode

# delete the element from the queue

# elements are deleted at the front of the queue

def dequeue(self):

# if queue is empty then return None

if(self.front == None):

return None

# get the data of front element of the queue

item = self.front.getData()

# if there is only one element in the queue, set front and back to None

if(self.front == self.back):

self.front = None

self.back = None

else: # set front to the next node of front

self.front = self.front.getNext()

return item

# returns the size of the queue

def size(self):

# if queue is empty then return 0

if self.front == None:

return 0

current = self.front

count = 0

# while loop to count the number of nodes in the queue

while(current.getNext() != None):

count = count + 1

current = current.getNext()

return count

# return the string representation of the queue

def __str__(self):

if(self.front == None):

return "Empty list"

current = self.front

nodeList = ""

while(current.getNext() != None):

nodeList = nodeList + str(current.getData())+" "

current = current.getNext()

nodeList = nodeList + str(current.getData())

return nodeList

# test the queue class

queue = Queue()

print("Empty queue : "+str(queue.isEmpty()))

print("Initial Queue :"+str(queue))

queue.enqueue(2)

queue.enqueue(1)

queue.enqueue(17)

queue.enqueue(4)

print("Queue after inserting element: : "+str(queue))

print("Size of queue : "+str(queue.size()))

print("Deleted element : "+str(queue.dequeue()))

print("Size of queue : "+str(queue.size()))

print("Empty queue : "+str(queue.isEmpty()))

print("Queue: "+str(queue))

# end of program

Navigate

The Queue is a special memory structure with accesses limited to PUSH and POP op

The Queue that we created in class was based on the built-in List module in Pyth

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

The Queue that we created in class was based on the built-in List module in Pyth

Question

Explanation / Answer

Related Questions

Navigate