CSC 207 Grinnell College Fall, 2014
 
Algorithms and Object-Oriented Design
 

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.

  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
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.