Queue Implementation

Objectives

  • Create a first-in-first-out (FIFO) data structure using an array and a singly-linked list.

  • Extend the array implementation so that the capacity of the array will resize depending on a set of constraints.

  • Explore generative testing. We will provide you the framework during this recitation, this is an incredibly powerful concept that can find difficult bugs…​ it’s really cool, ya’ll.

Getting Started

Create a new Java project called W8 and import Queue-starter.jar.

Your directory should look like this:

W8/
└── src
    ├── AQueue.java
    ├── ArrayQueue
    ├── IQueue
    ├── LinkedQueue
    ├── QueueTestProgram.java
    └── ResizingArrayQueue.java

This recitation is an optional partner recitation. I encourage you guys to discuss implementation details and to actively discuss the different topics that the next two recitations approach. You don’t need to have the same partners for each recitation and if you want to work alone, that’s fine too.

If you choose to work with a partner and do not complete the required work, it is your responsibility to finish the lab on your own. Each person should type their own code. I recommend coming back to this recitation on your own time and seeing how fast you can implement it without help from other students or TAs. This is something you can be asked to implement in a technical interview.

Here is the UML representation of the classes you will be implementing:

UML diagram
Description

Queues are a first-in-first-out data structure. Here is some additional information about what this implies.

Directions
The Bronze Level: the ArrayQueue class and AQueue class

The upcoming assignment and recitations can and should utilize method chaining. Think about how you can use other methods (efficiently) to promote code reuse. This will greatly decrease the amount of time you spend debugging after you’re finished. In the spirit of this idea and because we are trying to closely mirror the Java API, we pulled several methods into an abstract class.

Complete the AQueue class

Take a minute to read about the AQueue class here and then implement the methods specified in the javadoc. Hints have been provided above each method in the source file.

Complete the ArrayQueue class

Implement the methods specified in the javadoc. Read about generics before you begin and don’t forget to develop incrementally.

Testing

Once you have completed and tested your methods, you will use the QueueTestProgram static methods from your main to perform additional testing on your implementation. Here is documentation on what this program does and how you can use it to debug your code. If you can run a million test cases without finding any bugs, you can feel reasonably confident that your code is correct.

Great! You’ve done wonderfully, now let’s take this a step further.

The Silver Level: The LinkedQueue class

LinkedLists are the most intuitive data structure for queues. You remove elements from the head of the list and you add elements to the tail.

Let’s implement a queue using a singly linked list.

Use the javadoc to complete the LinkedQueue class.

Wow! You’re really starting to get a hang of this whole queue thing. Go for gold!

The Gold Level: The ResizingArrayQueue class

Use the javadoc to implement the ResizingArrayQueue class.

Submission

To receive credit for this recitation show your TA or helper that you have completed the code for the Bronze level, tested each method individually, and then sanity checked your program by running it through one million test cases using QueueTestProgram.