Laboratory Exercise on Queues with Arrays

Goals

This laboratory exercise introduces the concept of the queue abstract data type and provides experience implementing this ADT.

After introductory material on queues as abstract data types, work on queue implementations proceeds in two parts:

1. Implementation of queues with arrays (this lab)
2. Implementation of queues with linked lists (the next scheduled lab)

Queues as ADTs

Today's reading on queues describes a queue as an ADT that can store data and that has the following operations:

• initializeQueue
  Initializes an empty queue object.

• isEmpty
  Determine whether the queue is empty; return true if it is and false if it is not.

• isFull
  Determine whether the queue is full; return true if it is and false if it is not.

• enqueue
  Add a new element at the rear of a queue.

• dequeue
  Remove an element from the front of the queue and return it. (This operation cannot be performed if the queue is empty.)

• front
  Return the element at the front of the queue (without removing it from the queue). (Again, this operation cannot be performed if the queue is empty.)

Implementing Queues with Arrays

Be sure you have read the reading on queues, particularly the reading on the implementation of queues by arrays, before continuing.

In this part of the lab, we will focus on arrays of generic type E. The relevant fields are:

  public class Queue <E> {
    protected first;
    protected last;
    protected count;
    E queueArray [] ;
    ...
    

A constructor would initialize the queueArray to an array of a specified size. (Pragmatically, the size might be a constructor parameter.)

Work Started in Class

Additional implementation notes may be found in today's reading on Queues.

1. Write two implementations of a queue of strings by implementing these operations.

   1. In one implementation, use the following interpretations for the first and last fields (as discussed in the right column).
      • last designates the location of the most recent item inserted into the queue. (lastA in the diagram.)
      • first designations the location where the next item will be removed from the queue.
   2. In the second implementation, use the following interpretations for the first and last fields (as discussed in the right column).
      • last designates the location where the next item will be inserted into the queue. (lastB in the diagram.)
      • first designations the location where the previous item was removed from the queue.

2. Use the queue operations within a main procedure to provide thorough testing of each operation.

Homework

3. Add to the queue ADT an additional procedure print that displays each of the elements of the queue on a separate line (without actually removing any of them from the queue).

4. An alternative approach for the dequeue procedure would add a parameter item to the list of parameters and change the return type to an int type. The idea is that the string would be returned as a parameter char * item and the procedure would return the length of the string item or -1 if the queue was empty. The relevant procedure signature might be:

     int dequeue (stringQueue * queue, char ** item)
   

   and this procedure would be called within the context:

     char * frontItem;
     int returnValue;
     stringQueue myQueue;
     ...
     returnValue = dequeue (&myQueue, &frontItem)
   

   1. The parameter item has type char **, and the call to queue includes &frontItem. Explain why ** and & are needed here.
   2. Write this alternative version of the dequeue operation.