Week of
A reminder of some important points of ADT use are:
No matter what the underlying implementation of the ADT, programs should access a ADT only through these methods.
As a corollary to the first point, the ADT can be implemented in any number of ways so long as any given implementation follows the ADT method requirements. The implementation must invisible to the program using the ADT.
An ADT may store any type of data, although all the data it stores should be of the same type.
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.
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.
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.
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.
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.
For the Queue_array
library complete the implementation
of the insert
method.
For the Queue_array
library complete the implementation
of the remove
and peek
methods.
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.
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.
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 ------------------------------------------------------- """
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.
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.