CPSC 170 Spring 2003
Program 4: Standing in Line

Overview

At GoodFood grocery store, people really pour in around 5:00pm -- everyone is stopping on the way home from work for milk, bread, etc. The store's policy is that if more than 4 people are in any one line (that is, when the 5th person arrives), they will open a new register. They have observed that when they do this, the last 3 people in that line will leave to go to the new register, leaving only 2 people in the original line. They are wondering how it would affect the number of registers required if they increased or decreased the point at which they open a new register. In this program you will simulate the way the lines grow using this model -- and assuming that nobody ever leaves!.

Program Structure

Organize your program as follows:

Modify the QueueADT class to add a method QueueADT split(). This method should split the queue in half, with the front N/2 elements remaining on the original queue and the back N/2 elements leaving to join a new queue, which should be returned. If N is odd, the extra element should go on the new queue. The elements in the new queue should be in the same order as in the old queue, and the order of the elements that remain in the old queue should be unchanged.

Choose a queue implementation (linked or array) and add the split method to that implementation.

Write a class Grocery that maintains a collection of queues representing the lines in the store. (You choose what collection to use.) Grocery should provide the following public methods:

Grocery(int maxInLine) -- a constructor for a grocery store where there are never more than maxInLine people in line.
void arrive() -- add a new person to the shortest queue. Represent a person as an integer; this makes it easy to generate the next person (just add 1). Note that since your Queue class holds objects, you will have to wrap the integer into an Integer object.
void toString() -- returns a string with the contents of each queue, one queue per line.

Write a class TestGrocery that does the following:

Reads an integer N and a maximum line length from the user
Creates a Grocery object with that maximum line length
Has N customers arrive on that Grocery object.
Prints the final grocery object.

For example, if your maximum line length was 5, the first 5 arrivals would all go in the first line, so the output at that point would be

Line 1: 0 1 2 3 4

But when the next user arrived, this line would split so you would have the following:

Line 1: 0 1 2 
Line 2: 3 4 5

The next user would joint the shortest line, which could be either, and so on. When a line exceeded 5, it would again split. So after a few more arrivals you might have this:

Line 1: 0 1 2 6 8
Line 2: 3 4 5 7 9

The next arrival will cause Line 1 to split (if that's where it's added):

Line 1: 0 1 2 
Line 2: 3 4 5 7 9
Line 3: 6 8 10

And so on. Note that the numbering of the lines does not matter; my Line 1 could be your Line 3

CPSC 170 Spring 2003 Program 4: Standing in Line

Overview

Program Structure

CPSC 170 Spring 2003
Program 4: Standing in Line