Laboratory: Using Stacks and Queues
 CSC 207 Algorithms and Object Oriented Design Spring 2009

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/2010S/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).
4. # 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

One 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 3

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.
Jerod Weinman
Created: 12 January 2009
Exercises 1 and 2 adapted from W.H. Ford and W.R. Topp, Data Structures with Java, Exercise 12.
Exercises 3 and 4 adapted from S. Venugopal, Data Structures Outside In with JJava, Exercise E6.9 and E6.10.