CP164 Lab 3 : Queues

Week of

ADTs (Abstract Data Type)

A reminder of some important points of ADT use are:

Example: The following code imports a queue library and a Movie library then initializes a queue for storing movie data:

from Queue_array import Queue
from Movie import Movie

q = Queue()
...

We use this approach for the same reason we used it in the Stacks lab.


The Queue ADT

A queue is a data structure that follows FIFO (First In, First Out) rules. Data is added to the rear of a queue and removed from the front of a queue. The queue ADT provides methods for manipulating data in a queue. The queue ADT is discussed in The Queue ADT.


Array-based queues

The file Queue_array.py contains the array implementation of the Queue ADT. The Lab Instructor will walk you through the library and discuss its inner workings. Add the contents of this file to your login_data_structures project in Eclipse.


The Priority Queue ADT

A priority queue is a data structure in which data is added to and removed from a queue on the basis of priority. That priority is determined by the contents of the data. Should two pieces of data have the same priority their removal from the priority queue is determined as it would be in a regular queue - i.e. first in, first out. An example of a priority queue is the waiting area in an emergency room at a hospital. The emergency room staff rank incoming patients through a process called triage, giving them priority according to the immediacy of their medical requirements. People with the same medical requirements (e.g. three people with simple fevers) are admitted in the order in which they arrived at the emergency ward. The priority queue ADT provides functions for manipulating data in a priority queue. The priority queue is discussed in The Priority Queue ADT.


Array-based Priority Queues

The file Priority_Queue_array.py contains the array implementation of the Priority Queue ADT. The Lab Instructor will walk you through the library and discuss its inner workings. Add the contents of this file to your login_data_structures project in Eclipse.

Hint: although the Stack ADT is a LIFO (Last In, First Out) data structure, and the Queue ADT is a FIFO data structure, they share many similarities in their implementations. Use the Stack ADT implementations as a guideline for implementing your queues.

  1. For the Queue_array library complete the implementation of the insert method.

    Test Queue_array.py:


  2. For the Queue_array library complete the implementation of the remove and peek methods.

    Test Queue_array.py:


  3. For the Priority_Queue_array library complete the implementation of the insert and peek methods.

    Hint: The array-based priority queue definition contains an attribute named _first . This attribute keeps track of the index of the highest priority item currently in the priority queue. (Its value is None when the priority queue is empty.) When a new item is added to the end of the priority queue, the value of _first may need to be updated.

    Hint: the peek method is very simple as it uses the _first attribute to determine which item currently has the highest priority in the priority queue.

    Test Priority_Queue_array.py:


  4. For the Priority_Queue_array library complete the implementation of the remove method. (Note that you may not simply sort the queue using any built in Python list functions - you must find the value in the array with the highest priority and remove it from the array.)

    The remove method must update the value of _first after removing the current highest priority item - it is the most complex of the priority queue methods.

    Hint: the sample code contains an uncompleted private helper method named _set_first whose job is to find the index of the highest priority value in the priority queue. It it not needed for insert , but could be very useful for remove and other methods yet to be written.

    Test Priority_Queue_array.py:


  5. Add the following functions to the PyDev module named utilities in your login_data_structures project.

    def array_to_queue(queue, source):
        """
        -------------------------------------------------------
        Inserts contents of source into queue. At finish, source is empty.
        Last value in source is at rear of queue,
        first value in source is at front of queue.
        Use: array_to_queue(queue, source)
        -------------------------------------------------------
        Parameters:
            queue - a Queue object (Queue)
            source - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    
    def queue_to_array(queue, target):
        """
        -------------------------------------------------------
        Removes contents of queue into target. At finish, queue is empty.
        Front value of queue is at front of target,
        rear value of queue is at end of target.
        Use: queue_to_array(queue, target)
        -------------------------------------------------------
        Parameters:
            queue - a Queue object (Queue)
            target - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    
    def array_to_pq(pq, source):
        """
        -------------------------------------------------------
        Inserts contents of source into pq. At finish, source is empty.
        Last value in source is at rear of pq,
        first value in source is at front of pq.
        Use: array_to_pq(pq, source)
        -------------------------------------------------------
        Parameters:
            pq - a Priority_Queue object (Priority_Queue)
            source - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    
    def pq_to_array(pq, target):
        """
        -------------------------------------------------------
        Removes contents of pq into target. At finish, pq is empty.
        Highest priority value in pq is at front of target,
        lowest priority value in pq is at end of target.
        Use: pq_to_array(pq, target)
        -------------------------------------------------------
        Parameters:
            pq - a Priority_Queue object (Priority_Queue)
            target - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    

    Test utilities.py:


  6. Add the following function to the PyDev module named utilities in your login_data_structures project.

    def queue_test(a):
        """
        -------------------------------------------------------
        Tests queue implementation.
        Use: queue_test(a)
        -------------------------------------------------------
        Parameters:
            a - list of data (list of ?)
        Returns:
            the methods of Queue are tested for both empty and
            non-empty queues using the data in a:
            is_empty, insert, remove, peek, len
        -------------------------------------------------------
        """
        q = Queue()
    
        # tests for the queue methods go here
        # print the results of the method calls and verify by hand
    
        return
    

    Use Movie data from movies.txt to test your queue code.

    Test utilities.py:


  7. Add the following function to a PyDev module named utilities in your login_data_structures project.

    def priority_queue_test(a):
        """
        -------------------------------------------------------
        Tests priority queue implementation.
        Use: pq_test(a)
        -------------------------------------------------------
        Parameters:
            a - list of data (list of ?)
        Returns:
            the methods of Priority_Queue are tested for both empty and
            non-empty priority queues using the data in a:
            is_empty, insert, remove, peek
        -------------------------------------------------------
        """
        pq = Priority_Queue()
    
        # tests for the priority queue methods go here
        # print the results of the method calls and verify by hand
    
        return
    

    Use Movie data from movies.txt to test your priority queue code.

    Test utilities.py: