CS 161 Lab D - Testing the Stack

Due Fri Sep 27 at 9:00am

Overview

When we're programming there are different kinds of bugs. Some are compilation bugs--places where you forget a semicolon or use the wrong Syntax and BlueJ complains. Another kind are logical bugs. These are where your code "runs", but it doesn't "work"-- it doesn't actually do what it is supposed to do. These bugs can often be subtle: a math program may return a number that is slightly wrong!

In this lab, you will be writing code to test whether classes that have been provided to you "work" or not (they all compile, but they may not function properly!) These classes are all different implementations of a Stack, a classic way of organizing information in Computer Science (see below for details).

Are any of the programs correct? Only you can find out!

Remember that this lab should be completed in pairs. You will need to find a different partner than you have worked with before. Be sure to review the pair programming guidelines before you begin; remember to switch off who is driving and who is navigating!

Objectives

To practice writing testers and unit tests.
To practice finding bugs. Remember: when testing, "I found a bug" means that you won--"I didn't find a bug" means that you lost!

Necessary Files

You will need to download and extract the Stacks BlueJ project from the LabD.zip file. This project includes 5 different Stack classes for you to test, as well as the README.txt for you to fill out. Remember to extract the project from the zip file in order to run the program!

Stacks

In computer science, a "stack" is a way of ordering information--in this case numbers. A Stack works like a pop-up stack of trays at a cafeteria (or a Pez dispenser)--each time a number is added to the stack, it is put on the "top" of the other numbers. This is called pushing onto the stack, and we use the method push() to do this. So if I push the numbers 3 and 1 onto the Stack (in that order), then 3 will be n the bottom and 1 will be on the top.

Just like a stack of trays at the cafeteria, you can only get a number from the top of the stack. This is called popping off the stack (because the trays pop up), and we use the method pop() to do this. Note that pop() both removes the number from the stack and returns that number. So if I call "pop" on the stack described above, then it will give me 1.

Note that a Stack is a "Last In, First Out" structure--the first number to get in is the last person to be removed!

Below is an example of using the stack, and a diagram detailing what the stack looks like after each call happens:

stack.push(3);
stack.push(1);
stack.push(4);
value = stack.pop();   // value is 4
stack.push(5);
value = stack.pop();   // value is 5
value = stack.pop();   // value is 1
value = stack.pop();   // value is 3

In addition to the push() and pop() methods, the Stack class has two additional methods for determining the state of the Stack:

isEmpty() returns true if the Stack is empty, false otherwise.
isFull() returns true if the Stack is full, false otherwise.

Note that the Stacks in this lab can hold up to four (4) items. If you try to push() a number onto a full stack, that new number falls off and disappears. If you try to pop() a number off an empty stack, the value 0 will be returned.

The full documentation (in Java API format) for a Stack can be found at the bottom of the lab. If you have any questions about how this class should work, let me know!

Assignment Details

The provided lab files include 5 different stack implementations named StackA, StackB, etc. Your task is to write a tester program (that is, make a "tester class" with a main() method) that instantiates a Stack object and then calls methods on the object to try and find bugs!

For example, here is a (not very thorough) test program:

public static void main(String[] args)
{
   StackA stack = new StackA();

   System.out.print(“isEmpty() should be true is: “);
   System.out.println(stack.isEmpty());
   System.out.print(“isFull() should be false is: “);
   System.out.println(stack.isFull());
}

Notice how each line of output prints both the expected value and the actual value. If the two are different, that indicates that there is a bug in the Stck implementation!

After you are convinced you've thoroughly tested StackA, simply change "StackA" to "StackB" on the first line of code in order to run your tests on another stack! This demonstrates how good code can easily be re-used.

Perhaps you think of another test you want to run--you can add it to your test program, and then go back and re-run everything on StackA very easily.

Your task is to test all 5 of the Stacks. Note that one of the Stacks should pass all your tests (it works correctly), the others should all fail at least one test. Play detective and figure out which Stack is the real Stack!

Note: When testing software, it is not sufficient to verify that the software does what it is supposed to do. You also have to verify that it does not do what it is NOT supposed to do. To test the later, you have to put on an "evil nemesis" hat and try to make the software do all kinds of things that it isn’t supposed to do. Which of those things result in bad behavior?

A good test program should not only be able to find bugs; it should also give you enough data that you can guess about what may be the cause of the problem. What is the (faulty) logic that the broken Stack is obeying that causes it not to work?

Submission

For this lab, you will need to turn in two things:

Your completed StackTester class
A README.txt file which you identify, for each Stack, which test(s) if any failed, and what you think may be wrong with the implementation (if anything). Remember you can open the README.txt file in BlueJ by double-clicking on the icon.

Make sure both your names are on both your class and the README, and upload the entire project directory to the LabD submission folder on hedwig. Only one partner needs to upload the code. Make sure you upload your work to the correct folder! The lab is due at the start of class the morning after lab.

After you have submitted your solution, log onto Moodle and submit the Lab D Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded on approximately the following criteria:

Your tester class provides readable output and includes all your tests [25%]
You identified the correctly working Stack [10%]
Your README details which Stacks passed which tests [40%]
Your README includes a guess at what is wrong with the implementation [15%]
Code is formatted correctly (good indentation, names on the files, reasonable comments, etc). [5%]
Submitted a lab partner evaluation [5%]

Remember that it is very easy to get partial credit, so turn in whatever you have before the lab's due date!

Documentation

Below is the Java API formatted documentation of a Stack class.

Class Stack

public class Stack

Provides a Stack object for storing ints

Method Summary
`boolean`	`isEmpty()` Returns whether the Stack is empty or not.
`boolean`	`isFull()` Returns whether the Stack is full or not.
`int`	`pop()` Pops the top number off the stack.
`void`	`push(int num)` Pushes the given number onto the stack