The Queue that we created in class was based on the built-in List module in Pyth
ID: 3704724 • 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.
#################################
Code discussed in previous class
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
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 = 20
for i in range(totalCustomers):
randomItemsQty = randint(1, 25)
customer = Customer(randomItemsQty)
customersQueue.enqueue(customer)
#Checkout
totalTime=0
totalCustomers = customersQueue.size()
while not(customersQueue.isEmpty()):
totalTime+=randint(1,5)
customer = customersQueue.dequeue()
timeTaken = checkOut(customer)
totalTime+=timeTaken
#results
averageWaitTime = totalTime/totalCustomers
print("Average wait time is "+str(averageWaitTime)+" minutes")
###############################
I need code other than this code..
Python program to create a class implementing a Queue using linked list
'''
# 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
##############################
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.