The TAO of Java

Laboratory: Stacks

Summary: In this laboratory, you will have an opportunity to ground your understanding of the linked implementation of queues. The focus of this lab will be on correcting a partial implementation.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Code Reading
  • Exercise 2: Adding to Empty Queues
  • Exercise 3: Deleting To Empty Queues
  • Exercise 4: Removing Values

Required Code Files:

• Queue.java
• QueueNode.java
• LinkedQueue.java
• TestLinkedQueue.java

Exercises

Exercise 0: Preparation

a. Start Eclipse.

b. Verify that you already have a package named username.linear and that the package contains copies of

• Queue.java,
• QueueNode.java,
• LinkedQueue.java, and
• TestLinkedQueue.java.

If you lack any of those files, add them to the package.

Exercise 1: Code Reading

Make sure to do this exercise with at least one colleague!

a. Read through LinkedQueue.java and QueueNode.java.

b. There is a significant bug in the put method for empty lists. What is that bug?

c. There is a significant bug in the get method for one-element lists. What is that bug?

Exercise 2: Adding to Empty Queues

a. Compile and execute TestLinkedQueue. It should crash almost immediately, because of the bug you may have figured out in the put method.

b. In case you haven't figured it out, the problem is that it's difficult to refer to back.next when back is null. The solution is to check whether or not back is null, and, if so, do something other than put the new node after the back. Figure out what you should do in the special case and implement it.

c. Recompile LinkedQueue and execute TestLinkedQueue. If you solved part b correctly, you should be able to put an element and get it back, but it is unlikely the rest of your program will work correctly. (Depending on how you solved part b, your code may still work correctly.)

Exercise 3: Deleting To Empty Queues

a. One solution to exercise 2 is as follows

  if (this.back == null) {
    this.back = new QueueNode(val);
    this.front = this.back;
  }
  else {
    // Old code
  }

Update your code to use my solution (sorry), recompile LinkedQueue, and then execute TestLinkedQueue. Your program should put and get the first element successfully, but fail afterwards.

b. Summarize, as best you can, what seems to be wrong now. (Describe the problem with the output, you need not analyze the underlying problem.)

c. Think about the problem again and see if you can determine the error.

d. Fix the error.

Exercise 4: Removing Values

In many applications, it turns out to be helpful to remove values from queues. For example, if I have a queue of email messages from students to respond to and a student suddenly drops my class, I should remove all email from that student from the class.

While it is possible to add a remove method to LinkedQueue, it is also possible to write such a method using only the basic queue operations (and, in fact, the basic stack operations).

a. Create a class, QueueHelper, that provides one method, remove(Object val, Queue q). This method should remove all instances of val from the queue.

b. Test your method.

c. What do you expect to have happen if you use the same strategy to remove values from a stack?

d. Confirm your answer to c experimentally. (You'll need to change the parameter type to use remove.)

History

Monday, 7 March 2005 [Samuel A. Rebelsky]

• Created.

Wednesday, 8 March 2006 [Samuel A. Rebelsky]

• Minor updates.