CPSC 170 Spring 2003
Program 4: Standing in Line


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:

  • Write a class TestGrocery that does the following:

    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