Laboratory: Using Stacks and Queues
||Algorithms and Object Oriented Design
Summary: In this lab, you will practice using stacks to solve
some data organization and manipulation problems.
Create a directory for this lab:
Copy the following class for this lab:
cp ~weinman/public_html/courses/CSC207/2010S/labs/code/stacksqueues/Stacks.java .
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).
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
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
Design an algorithm using only stack methods that simulates the
music director's behavior. By design, we mean write it out on paper.
Implement the method
Stacks.java, using your algorithm to remove all
stack (you should
equals method). You may create only Stack(s)
AnyType for temporary storage.
main routine to test your method.
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.
Add the following function to
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
Should produce the output:
Stack<Integer> stack = new Stack<Integer>();
main to test your method.
What is the complexity of your algorithm?
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
Design an algorithm using only queues (and their methods) to simulate this splitting of the line (queue) into two queues.
In a new class called
Queues write a function
that implements your algorithm. The original
public static <AnyType> Queue<AnyType> split(Queue<AnyType> queue)
have roughly half-as many entries in it (order preserved), and the
returned object should be a new queue with the other half.
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
Write a driver to test your program.
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.
Assume we have a record of the time each person arrived in
line. Write an algorithm that performs a fair merging of two queues.
Implement the following function.
Again, note that
/** 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 )
java.util.Queue. The static type of all your collections variables should be
Write a driver to test your function.