Summary: In this lab, you will practice using stacks to solve some data organization and manipulation problems.

Preparation

1. Create a directory for this lab:

     mkdir somewhere/stacksqueues

2. Copy the following class for this lab:

   cp ~weinman/public_html/courses/CSC207/2011S/labs/code/stacksqueues/Stacks.java .

3. In an earlier lab, you should have already downloaded the code from the book and configured Ant/JDE to use it. If you have not already done so, do it now or use your lab partner's account (assuming they have done it).

Exercises

Exercise 1

A college radio station keeps a pile of the music director's top 30 albums close to the DJ so that they have fast access to the music that gets played most often. (Here is an example image. I would probably listen to that radio station.) However, the music director wants to keep it current, so every two weeks she goes through and removes any CDs that are more than one month old.

To do this, she takes the CDs off the pile one by one and starts a new pile. Any CDs that meet her criterion she pulls off and puts into a different pile. When she is finished, she puts back the CDs she had taken off the pile and returns them to the original pile, in the original order.

1. Design an algorithm using only stack methods that simulates the music director's behavior. By design, we mean write it out on paper.
2. Implement the method removeAll in Stacks.java, using your algorithm to remove all instances of item from stack (you should use the equals method). You may create only Stack(s) or an AnyType for temporary storage.
3. Use the main routine to test your method.

Exercise 2

Sometimes, there are assistant music directors that get overeager and also add CDs to the collection. Often, these are duplicates that get sent to the radio station by record companies to be sure their music is being promoted.

1. Add the following function to Stacks.java

   public static <AnyType> void removeDuplicates( Stack<AnyType> stack)

   removeDuplicates should use only an extra stack (for storage) and calls to your removeAll method to eliminate the duplicates from stack but otherwise preserve the elements in the same order.

   For example, the code

   Stack<Integer> stack = new Stack<Integer>();
   
   stack.push(5);
   stack.push(3);
   stack.push(1);
   stack.push(2);
   stack.push(3);
   stack.push(5);
   stack.push(3);
   
   System.out.println (stack);
   removeDuplicates (stack);
   System.out.println (stack);

   Should produce the output:

   3532135
   3521

2. Modify main to test your method.
3. What is the complexity of your algorithm?

Exercise 3

On the first day of the semester, the bookstore failed to remember how busy it would be with everyone buying books and therefore only had one register open. They quickly remedied this by opening another register. Wanting to ensure fairness among everyone waiting in line, every other person is directed to wait in line at the newly opened register.

1. Design an algorithm using only queues (and their methods) to simulate this splitting of the line (queue) into two queues.
2. In a new class called Queues write a function

   public static <AnyType> Queue<AnyType> split(Queue<AnyType> queue)

   that implements your algorithm. The original queue should have roughly half-as many entries in it (order preserved), and the returned object should be a new queue with the other half.

   Note that java.util.LinkedList implements java.util.Queue, which is the data structure you should use in your algorithm. You will need to import both, but the static type of all your collections variables should be Queue.

3. Write a driver to test your program.

Exercise 4

On the second day of the semester, the bookstore ran into the opposite problem. They had extensive lines on both of their registers, but one register worker's shift ended, leaving them with only one register open. This time, the two queues must be merged. However, to ensure fairness, no one should be put in line behind someone else who arrived in their line later.

1. Assume we have a record of the time each person arrived in line. Write an algorithm that performs a fair merging of two queues.
2. Implement the following function.

   /** Merges two queues based on their arrival time. item1 (from either
    *  queue) is considered to have arrived before item2 (from the other
    *  queue) if item1.compareTo(item2)<0.
    *
    *  Postconditions: queue1.size() == 0 and queue2.size() == 0.
    *
    *  @returns A new Queue containing all elements from both queues
    */
   public static <AnyType extends Comparable<? super AnyType>> Queue<AnyType> merge 
    ( Queue<AnyType> queue1,
      Queue<AnyType> queue2 )
   

   Again, note that java.util.LinkedList implements java.util.Queue. The static type of all your collections variables should be Queue.
3. Write a driver to test your function.