Java Reference
In-Depth Information
9.
Repeat Exercise 8, but instead use the following random events:
Customer 1 enters the line at time 0 with a transaction time of 4.
Customer 2 enters the line at time 1 with a transaction time of 4.
Customer 3 enters the line at time 3 with a transaction time of 1.
Customer 4 enters the line at time 4 with a transaction time of 4.
Customer 5 enters the line at time 9 with a transaction time of 3.
Customer 6 enters the line at time 12 with a transaction time of 2.
Customer 7 enters the line at time 13 with a transaction time of 1.
10.
When using a queue to compute capital gains, we observed in Segment 10.12 that the queue's entries could repre-
sent more than one share of stock if they have set methods. Revise the class StockPurchase so that each of its
instances has set methods and represents the purchase of multiple shares of one company's stock. Then revise the
class StockLedger , using a queue to contain the StockPurchase objects.
11.
Stacks, queues, and deques are similar in operation in many ways. Suppose that we wanted to create an abstract
base class QueueBase and then use it and inheritance to implement each of the three ADTs. Design the class
QueueBase . Indicate whether each field and method should be public, protected, or private, and explain why.
12.
Segment 9.21 in Chapter 9 provided the pseudocode for a radix sort of an array. Each bucket in that algorithm is
actually a queue. Describe why you can use a queue but not a stack for a radix sort.
13.
Exercise 11 of Chapter 5 describes a palindrome. Can you use one of the ADTs described in this chapter instead of
a stack to see whether a string is a palindrome? If so, develop an algorithm to do so for each applicable ADT.
14.
Consider a special kind of stack that has a finite size but allows an unlimited number of push operations. If the
stack is full when a push occurs, the stack makes room for the new entry by deleting the entry at its bottom. A
browser that maintains a limited history could use this kind of stack. Implement this stack by using a deque.
P ROJECTS
1.
Project 3 of Chapter 9 used a vector in the implementation of an iterative merge sort. In that project, the vector
was used as if it were a queue. Repeat the project, but use a queue instead of a vector.
2.
Implement the radix sort, as given in Segment 9.21 of Chapter 9, by using a queue for each bucket.
3.
Expand the capital gains example described in this chapter to allow more than one type of stock in the portfolio.
Identify different stocks by using a string for the stock's symbol. Record the shares of each company in a separate
queue, deque, or priority queue. Maintain the collection of these ADTs in a bag or stack.
4.
Simulate a small airport with one runway. Airplanes waiting to take off join a queue on the ground. Planes waiting
to land join a queue in the air. Only one plane can use the runway at any given time. All planes in the air must land
before any plane can take off.
5.
Repeat Project 4, but use a priority queue for the planes waiting to land. Develop a priority schedule for situations
such as low fuel or mechanical problems.
6.
When each object in a collection has a priority, how should you organize several objects that have the same priority?
One way is to order the objects with the same priority in chronological order. Thus, you can create a priority queue of
queues. Design such an ADT.
7.
Write a program to simulate a train route. A train route consists of a number of stations, starting and ending with a
terminal station. The time that the train needs to travel between a pair of consecutive stations on the route is given.
Associated with each station is a queue of passengers. Passengers are generated at random times, assigned to entry
stations randomly, and given random destination stations. Trains leave a terminal at regular intervals and visit the
stations on the route. When a train stops at a station, all passengers for that station exit first. Then any passengers
waiting in the queue at the station board the train until either the queue is empty or the train is full.
Search WWH ::




Custom Search