1. Consider a queue at a supermarket. It is rather fair, in that it has a _______________ method.
2. In the Python language, insert() and pop() methods ae used to _____ and _____ elements respectively.
3. The following is a Python representation of a queue using OOP (a class). What is output on execution of this code?
4. A method could be implemented to remove data. Which of the following methods would be the correct implementation?
5. Uses for queues involve anything where you want things to happen in the order that they were called, but where the computer can't keep up to speed. Which of the following are valid examples?
Example 1:
===========
Keyboard Buffer - you want the letters to appear on the
screen in the order you press them
Example 2:
===========
Printer Queue - you want print jobs to complete in the
order you sent them, i.e. page 1, page 2, page 3, page 4 etc
Example 3:
==========
Handling of interrupts in real-time systems. The interrupts are
handled in the same order as they arrive, First come first served
Example 4:
==========
In real life, Call Center phone systems will use Queues, to
hold people calling them in an order, until a service representative
is free
Example 5:
==========
Depth First search in a Graph (specifically backtracking). It is an algorithm for
traversing or searching graph data structures.
All of the examples are valid except Example 5
Example 1, 3, and 5
Example 1 and 3
Only Example 2 is valid
6. A circular queue uses a ___________________________ as it moves through the queue. A linear queue does not reuse memory and can waste memory.
7. These three pointers could be used to implement a:
8. What would the value of the pointers be in the scenario described in the text below?
9. If a circular queue was being used, what would the value of the pointers be in this scenario?
10. What happens in a priority queue when a task of higher priority wants the processor's attention?
11. Unlike linear queues Circular queues DO NOT allow for memory to be re-used:
12. A double-ended queue, or deque, has the feature of adding and removing elements from either end. The Deque module is a part of collections library (Python)
13. The following rather long bit of code is a queue (class) implementation in Python. In this execution, what is the last item in the queue and the tail pointer value?
#Class based OOP implementation of a queue in Python
#Queue is a First in First out FIFO structure
class Queue:
def __init__(self): #this is like the constructor
self.items=[] #the only attribute we need is items, self is put before and we start with an empty queue
def add(self,item): #method to add something
self.items.append(item) #to add something, use append
def remove(self): #delete something, no need to specify what it is
itemToRemove = self.items[0] #the item to remove will be the first item in the list
del self.items[0] #this is to remember the item
return itemToRemove #return the item to Remove
def size(self):
return len(self.items) #this just returns the length of the list
def report(self):
return self.items #return the items of the queue
#think of this as a the pointer (head) - it stores the first element in the queue. In python it is not necessary to use pointers, as a list acts as a queue and you can directly access or reference the index numbers.
def firstitem(self):
return self.items[0] #this just returns the first item (that would be popped) in the queue
#think of this as the pointer (tail)
def lastitem(self):
return self.items[len(self.items)-1] #this just returns the first item (that would be popped) in the queue
def head_pointer(self):
head=0
return head
def tail_pointer(self):
tail=len(self.items)-1
return tail
#Test this works
def testQueue():
questions=Queue()
questions.add("2*3")
questions.add("1+4")
questions.add("3-1")
questions.add("10/2")
questions.add("3+6")
print("Size of Queue:",questions.size()) #=======This should return 5, as we have 5 questions, as per this example, in the queue called 'questions'
print("Printing the whole queue contents:",questions.report())
print()
print()
print("First item in the queue is:",questions.firstitem(),"and head pointer =",questions.head_pointer())
print("Last item in the queue is:", questions.lastitem(),"and tail pointer=",questions.tail_pointer())
print()
print("===============Adding another question 6+1 to the queue=================")
questions.add("6+1")#=====This should add another question to the queue (6+1)
testQueue()
Last item in the queue is: 3+6 and head pointer = 0
Last item in the queue is: 3+6 and tail pointer= 4
Last item in the queue is: 2*3 and head pointer = 0
Last item in the queue is: 2*3 and head pointer = 4
14. In the following class based Python implementation of a queue, what is happening on line 37?
15. A __________ has the first item and last item next to each other in the sense that, when the last allocated element is used up, it goes back to the start and reuses existing space
16. A __________ will have an additional item of data with each element indicating the priority of the element. Data items will be removed in priority order.
17. A ___________ can be viewed as a line of data, much like a list, with a start and end pointer
18. Review the following pseudocode for adding an element to a queue. What is the first question you would ask before moving on to the cases?
19. A circular queue is best known for its efficient use of memory. It is also called a circular buffer
20. If you have studied Big O and time complexity, you should be able to select the right answer for what will go in the blanks.