Preview

07 - Queues

 1. Consider a queue at a supermarket. It is rather fair, in that it has a _______________ method.
Note: A queue is an important abstract data type/structure used heavily in computing

  first in, last out

  last in, first out

  first in, first out

  last in, first in

 2. In the Python language, insert() and pop() methods ae used to _____ and _____ elements respectively.

  add / remove

  duplicate / remove

  add / edit

  remove / delete

 3. The following is a Python representation of a queue using OOP (a class). What is output on execution of this code?
#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



#Test this works

def testQueue():
    myQ=Queue()
    myQ.add("Adam")
    myQ.add("Eve")
    myQ.add("Abel")
    myQ.add("Cain")
    myQ.add("Seth")
    print(myQ.size()) #=======This should return 5, as I have five very ancient people in my queue


testQueue()

    

  5

  Matthew, Mark, Luke, John, Acts

  Acts

  3

 4. A method could be implemented to remove data. Which of the following methods would be the correct implementation?
Method 1
=========

def removefromq(self):
      if len(self.queue)<0:
          return self.queue.push()
      return ("No elements in Queue!")


Method 2
=========
def removefromq(self):
      if len(self.queue)>0:
          return self.queue.pop()
      return ("No elements in Queue!")



Method 3
=========
def removefromq(self):
      if len(self.queue)<0:
          return self.queue.pop()
      return ("No elements in Queue!")

  All of the mentioned methods are valid/correct

  Method 2

  Method 3

  Method 1

 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. 

  Only Example 2 is valid

  All of the examples are valid except Example 5

  Example 1, 3, and 5

  Example 1 and 3

 6. A circular queue uses a ___________________________ as it moves through the queue. A linear queue does not reuse memory and can waste memory.

  variable amount of memory and so cannot reuse memory

  fixed amount of memory and it duplicates memory

  binary formatted sequence of memory and it duplicates memory

  fixed amount of memory and reuses memory

 7. These three pointers could be used to implement a:
one to the actual buffer in memory
one to point to the start of valid data (StartPtr)
one to point to the end of valid data (EndPtr)

  buffering validation structure

  circular queue

  print queue specifically

  stack data structure, using a queue

 8. What would the value of the pointers be in the scenario described in the text below?
In a linear queue, what would be the value of the pointers 
when:
>>the animals Monkey and Snake are added, 
>>the first item removed,
>> and then Bear added to the following queue:


1	     2	     3	       4	 5
============================================
	
Badger	   Ferret    Weasel		

  It would not work- as there is no more space left in the queue

  Bear would be added in position 5, StartPtr = 1 EndPtr = 5

  Bear would be added in position 1: StartPtr = 2; EndPtr = 1

  Bear would be added in position 4, StartPtr = 4 EndPtr = 5

 9. If a circular queue was being used, what would the value of the pointers be in this scenario?
In a linear queue, what would be the value of the pointers 
when:
>>the animals Monkey and Snake are added, 
>>the first item removed,
>> and then Bear added to the following queue:


1	     2	     3	       4	 5
============================================
	
Badger	   Ferret    Weasel		

  Bear would be added in position 1: StartPtr = 2; EndPtr = 1

  Bear would be added in position 4, StartPtr = 4 EndPtr = 5

  It would not work- as there is no more space left in the queue

  Bear would be added in position 5, StartPtr = 1 EndPtr = 5

 10. What happens in a priority queue when a task of higher priority wants the processor's attention?
In a computer we use priority queues to handle the 
execution of processes. Each process will have a
 priority attached to it, with the more important processes
 jumping ahead of the less important for the processor's
 attention when they require it. For example:

Process	Priority
==========================
Web Browser	Normal
Media Player	Below Normal
OS Security	High
Scheduled Virus Scanner	Low
Printer Queue	Low
Word Processor	Normal

  The lower priority task is queued and the higher priority task is given the processors attention

  All the items are popped out of the queue so that none of them are given an unfair advantage

  The higher priority task is queued and the lower priority task is queued

  All items are queued and assigned equal priority

 11. Unlike linear queues Circular queues DO NOT allow for memory to be re-used:

  TRUE

  FALSE

 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)

  TRUE

  FALSE

 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: 2*3 and head pointer = 0

  Last item in the queue is: 2*3 and head pointer = 4

  Last item in the queue is: 3+6 and tail pointer= 4

 14. In the following class based Python implementation of a queue, what is happening on line 37?
#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

    def firstitem(self):
        return self.items[0] #this just returns the first item (that would be popped) in the queue

    def lastitem(self):
        return self.items[len(self.items)-1] #this just returns the first item (that would be popped) in the queue

def testQueue():
    myQ=Queue()
    myQ.add("Adam")
    myQ.add("Eve")
    myQ.add("Abel")
    myQ.add("Cain")
    myQ.add("Seth")
    myQ.add("Enoch")
    print(myQ.size()) #=======This should return 5, as I have five very ancient people in my queue
    print(myQ.report())
    print(myQ.remove()) 
    print(myQ.report())
    print(myQ.firstitem())
    print(myQ.lastitem())
    
testQueue()

  it removes the first person in the queue ('Adam') and places it in the last index position (over writing 'Enoch')

  it removes the first person in the queue (in this case 'Adam')

  it removes the last person in the queue (in this case 'Enoch')

  it adds or duplicates the first person in the queue (in this case 'Adam')

 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

  double queue

  linear queue

  priority queue

  circular queue

 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.

  linear queue

  double queue

  priority queue

  circular queue

 17. A ___________ can be viewed as a line of data, much like a list, with a start and end pointer

  linear queue

  circular queue

  double queue

  priority queue

 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?
Adding an element to a queue
==============================
_______________________________??

Case 1: Queue is full
Return an error message to the calling function
End of task
Case 1: Queue is not full
Allocate memory to the new node
Adjust the rear pointer to locate the new node

  Is the queue holding numeric values?

  Is the queue full?

  Is the queue linear?

  Is the queue a circular queue?

 19. A circular queue is best known for its efficient use of memory. It is also called a circular buffer

  False

  True

 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.
Source: https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
bigocomplexityofaqueue.png

  O(n2)

  O(2)

  O(1)

  O(n)