CPSC 170 Lab 10: Implementing Queues

In this lab you will explore queue implementations much as you explored stack implementations in the last lab.

1. Write a class IntQueue1 that uses an array to implement a queue of integers. In addition to a constructor, provide the following public methods:
   • void enqueue(int val)
   • int dequeue()
   • boolean empty()
   Make the array 5 elements to start; if it fills up, double its size.

2. File QueueTest1.java contains a simple driver to test your queue class. Save it to your directory and study it to see what it does. Then compile it with your IntQueue1 class, run it, and make sure it works.

3. QueueTest1 contained a printQueue method that took an IntQueue1 and printed its contents, restoring the queue before it returned. (You wrote a similar method for stacks that used a similar strategy last week.) But it's a little different here, as the temporary queue actually holds the same information as the original queue -- it hasn't been reversed, as it was for the stack. In fact, if you know the number of elements in the queue, you can write a printQueue method that prints the queue and restores it to its original form without using an auxiliary data structure (stack, queue, etc.). Think about how, then do it! That is:
   • Add a public method int size() to your IntQueue1 class that returns the number of elements in the queue.
   • Modify the printQueue method in QueueTest1 so that behaves exactly as it does now but does not require an auxiliary data structure.

4. Write a class IntQueue2 that implements the same methods as IntQueue1 but uses a linked implementation of a queue.

5. Copy your QueueTest1.java file into a file QueueTest2.java. Change only the names of your queue types, from IntQueue1 to IntQueue2. Compile and run QueueTest2.java; it should work exactly like QueueTest1.java.

HAND IN:

• Hand in hardcopy of your IntQueue1.java, QueueTest1.java, IntQueue2.java, and QueueTest2.java files.
• Tar the files in your lab10 directory and email the .tgz file to me (bloss@cs.roanoke.edu).