| A Queue Implementation |
10 points
Recall that a queue is like a line, for example a line of people waiting to buy tickets or to vote. The people who arrive first in the queue are the first to leave the queue, so a queue is a first-in first-out (FIFO) data structure. (In a sense, then, a queue is the "opposite" of a stack.) Queues have many real-world applications; for example, when a printer receives more print requests that it can handle, the requests that it can't handle immediately go into a print queue. A printer's print queue works just like the queue you are writing here: the first job that arrives in the queue is the first one to get completed.
A standard array or ArrayList is not a good choice for implementing a queue. This is because commands like:
array[0] = "new data"
arraylist.remove(0) or
arraylist.add(0, "new data")
are inefficient, because they require all the other elements to shift 1 space (either to the left or the right), which takes computational time. One way of avoiding this problem is to use a circular array. Here is some information from the textbook on how a circular array works:
We will use a circular array to implement a queue. A circular array is implemented with a standard array, which is a concrete data structure. A circular array is an abstract data structure, because it implements an idea in the programmer's mind as to how information should be organized. A queue is also an abstract data structure.
You can download Queue.java and CircularArrayQueue.java to use as starting points in writing this program. Queue.java is an interface that CircularArrayQueue implements. Instructions for completing CircularArrayQueue.java are in the file. We will then use the CircularArrayQueue class to write a simulation of a hospital emergency room dispatching ambulances to 911 calls.