COMP 139 - Lab 3 - Stacks, Queues, and Generics

Learning Outcomes and Introduction

In this lab assignment you will be creating implementations of Stack and Queue data structures. In the process, you will get experience in:

• writing code to implement an interface
• using generics
• creating container classes that manage other objects
• writing "library" classes without a pre-determined use case
• working with circular arrays bonus!

The Java standard library includes implementations of these abstract data types, but creating your own is a useful experience that will give you a better understanding of the considerations that go into designing concrete data structures. Note that the interfaces provided here differ substantially from those defined in the standard library in order to simplify your work for the assignment. We will look closer at the standard library classes later on in the course.

Do not use any classes from the Java Collections Framework in your solutions for this assignment, except for java.util.NoSuchElementException.

Make sure you test your code as you progress through the tasks. There is no "main program" in this assignment, so good unit tests will be essential to ensure that your code is correct. Use a single main-method class to test your code from all tasks, and submit it along with the rest of your work.

Task 1: Stack

Create an implementation of the Stack interface using arrays.

Make sure that your implementation does not retain references to items that have been removed from the stack.

You may find it easier to start with a non-generic solution that only handles one kind of data. You can do this by passing a concrete type parameter in the implements clause, eg:

			public class ArrayStack implements examples.Stack<Integer> { }
		

However, your completed code should be a generic implementation, such as:

			public class ArrayStack<T> implements examples.Stack<T> { }
		

Task 2: Queue

Create an implementation of the Queue interface using arrays.

Make sure that your implementation does not retain references to items that have been removed from the queue.

Your implementation may use a simple array approach for storage, where the capacity of the queue decreases as items are added and is not restored when items are dequeued. In this case, your queue will eventually become unusable, but the reset() method should restore it to full capacity again. For bonus marks, use a "circular array" implementation instead so that your queue does not have this limitation.

Submission

Completing all tasks in this lab should result in 3 separate Java files (one for each task, plus a main-method testing class) within a single package named like LastnameFirstname_lab3. You should not include the Stack or Queue interface files. Compress the package directory into a ZIP archive and upload it to the D2L assignment.

The marks for this lab are heavily weighted towards good coding practice and style. Pay attention to your code formatting, make sure you have documented all public members using JavaDoc, and make sure you are using constants, arrays, loops, and methods effectively.

NOTE: This assignment is to be done individually. You can help one another with problems and questions, but in the end everyone must do their own work.