Lab on Queues and Testing

Summary

This laboratory reviews some of the main operations of a queue and considers how a proposed queue implementation might be tested.

Introduction

Java's Queue interface specifies several common operations. According to Java's Queue description:

Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Queue implementations; in most implementations, insert operations cannot fail.

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

Java's Java's ArrayDeque provides an expandable-array implementation of this data structure.

For simplicity in this and some subsequent labs, we focus on just a few methods, as prescribed in the Queue207 interface.

Testing

In this and later labs, we will be considering several implementations of queues. For this lab, we need to consider when an implementation of Queue207 is correct.

1. Identify what circumstances should be tested in order to be confident that a Queue207 implementation is correct. That is, specify (in English) a list of cases that should be tested when reviewing a Queue207 implementation; if an implementation passes these tests, we want to be able to conclude that the implementation is completely correct.

2. Write out a list of specific tests (e.g., with specific data) that will cover all situations that you identified in step 1. For example, you might fill in an extended table of the following format:

   Operation	Parameter, if any	Expected Result
   create/constructor of String	(String data type)	Queue object created
   add	"one"	returns true, no exception, string "one" added to object
   add	null	NullPointerException thrown
   ...
   ...

3. Translate your list of test cases into a sequence of tests implemented with JUnit.

   • Use the name Queue207Implementation for the class to be tested.
   • For use later in the semester, label your test class with your last name: Queue207Lastname. Thus, my JUnit test class would be named Queue207Walker.

4. Write an Queue207Implementation, so that your test plan and automated test suite can be tested with JUnit. One simple approach might be to write a class with a field of class ArrayDeque. Then the constructor would initialize the ArrayDeque, and the add, remove, and examine methods would call the relevant ArrayDeque operations for this private field.

   Hint: This can be done VERY simply and quickly.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/207.fa14/labs/lab-queues-testing.shtml

created 1 April 2012 revised 8 April 2013 revised with JUnit 11-12 November 2014
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.