CS102 Spring 2007

Lab # 6

Resizable, Circular Array-Based Implementation of a Queue ADT

In this laboratory exercise you will write a program that implements and tests a resizable, circular array-based implementation of the Queue ADT. You may use your implementation of the Queue ADT in a future assignment.

Download starter project and launch NetBeans

  1. Download the lab 6 starter project and unzip it in your cs102 directory.
  2. Launch NetBeans and open the project named lab6Queue.  
  3. The project includes the following Java source files: Main.java, QueueException.java, and QueueInterface.java. 
  4. You will add a new class, QueueArrayBased, that implements QueueInterface.
    In our implementation, we used the following fields, which you might also find helpful implementing your solution:
      // fields
      private final int DEFAULT_SIZE = 10;
      private Object[] array;    // circular array (queue)
      private int front;         // front of queue
      private int back;          // rear of queue
      private int size;          // #elements in queue
      private int capacity;      // current queue's capacity

  5. Here are the five (5) methods of QueueInterface you must implement in class QueueArrayBased:

  public boolean isEmpty();
  // Determines whether a queue is empty.
  // Precondition: None.
  // Postcondition: Returns true if the queue is empty;
  // otherwise returns false.
  
  public void enqueue(Object newItem) throws QueueException;
  // Adds an item at the back of a queue.
  // Precondition: newItem is the item to be inserted.
  // Postcondition: If the operation was successful, newItem
  // is at the back of the queue. Some implementations may
  // throw QueueException if newItem cannot be added to the
  // queue.

  public Object dequeue() throws QueueException;
  // Retrieves and removes the front of a queue.
  // Precondition: None.
  // Postcondition: If the queue is not empty, the item
  // that was added to the queue earliest is returned and
  // the item is removed. If the queue is empty, the
  // operation is impossible and QueueException is thrown.

  public void dequeueAll();
  // Removes all items of a queue.
  // Precondition: None.
  // Postcondition: The queue is empty.

  public Object peek() throws QueueException;
  // Retrieves the item at the front of a queue.
  // Precondition: None.
  // Postcondition: If the queue is not empty, the item
  // that was added to the queue earliest is returned.
  // If the queue is empty, the operation is impossible
  // and QueueException is thrown.

  1. Yours will be a circular array-based implementation, and furthermore, in the case where the queue is full and another element needs to be enqueued, your implementation will resize(*) the array (a good rule of thumb is to double the size) rather than throw an exception.

    (*) arrays cannot be resized in Java, technically, so you must allocate a new array, copy the contents of the original array to the new array, and update the array field to reference the newly allocated array.
    Warning: resizing the array is the trickiest part of this lab. Since the array is treated as circular, you must think carefully about how to copy the elements from the old array to the new array, and how to reinitialize the front and back indexes.

  2. Save and run your project. When it successfully produces the correct output (shown below), submit your lab.  Here is the sample output:

init:
deps-jar:
compile:
run:
queue initially empty?: true

        adding more elements to queue than its initial capacity of 10...
        ...elements added to queue

queue no longer empty?: true

        dequeue first 10 elements in queue and print them:
                0 2 4 6 8 10 12 14 16 18

Next element = 20?: true

        removing one at a time the rest of the enqueued elements from the queue...

queue once more empty?: true

        peeking at the front of the queue now should result in an exception...

Error encountered peeking at front of queue: Queue exception on peek: Queue empty

        adding more elements to queue--testing the circular array buffer...
        ...elements added to queue

queue no longer empty?: true

        removing at once all elements from queue...

queue once more empty?: true

BUILD SUCCESSFUL (total time: 1 second)

Submitting your work

Submitting your work may involve two parts: electronic and printouts.

First, the electronic (required). From a terminal window, type the following commands: 

        cd
        cd cs102
        submit102 lab6Queue

Second, if you didn't finish the lab (checked by your instructor or one of the coaches) during the lab period, print out your source code listing and hand in to your instructor. For this lab, print file QueueArrayBased.java. If your instructor is not around, leave your printout in his mail bin, which is located outside the Computer Science Department office.

Log out

When you are done, close NetBeans, and then locate the logout button on the menu bar. Click on the logout button (red arrow pointing through an open door).  Choose "Logout..." and then click "Yes" when prompted.  Always remember to log out when you are done using the system, to ensure that no one else uses your account.