Queues study guide

A reliable method

First identify the queue type. Do not decide how an operation works until you know whether the queue is linear, circular or priority-based. Then identify the front and rear, or the equivalent information used by the representation. Finally apply the requested operation and state the resulting condition: the item added, the item removed, or whether the queue is empty or full.

For a linear queue, track the front and rear as positions that move through the storage. An addition uses the rear position, while a removal uses the front position. After each operation, reconsider the empty and full tests. If removed positions are not reused, explain that the queue may become unable to accept a further item even though positions before the front are no longer occupied.

For a circular queue, track movement modulo the storage arrangement: after the final position, the next possible position is the first position. A worked answer should show the wrap-around rather than merely saying that the queue is circular. It should also explain how the implementation knows whether the queue is empty or full. A full test must not be confused with the rear simply being at the final position, because an available position may exist at the beginning.

For a priority queue, record both the item and its priority. When adding, preserve or establish the arrangement needed by the priority rule. When removing, select the item with the appropriate priority, not automatically the earliest-added item. If the question gives equal priorities but does not define a tie rule, do not invent one; state that the specified priority rule is needed to determine the result.

Exam application example

Consider the sequence: add A, add B, remove one item, add C. In a linear or circular queue, the first removal is the earliest item still present, so A is removed if no earlier removal has occurred. The later addition of C is placed at the rear, with circular wrapping possible in a circular queue. In a priority queue, the removed item is instead determined by the priorities of A and B. A strong answer therefore identifies the queue type before giving the result.

Self-check questions

1. Where is an item added, and where is an item removed?
2. What condition represents an empty queue?
3. What condition represents a full queue for the given storage arrangement?
4. Can a linear queue reuse positions before its front? If not, what consequence follows?
5. Why can a circular queue reuse an earlier position?
6. Why might a priority queue remove a later-added item before an earlier-added item?

When checking an answer, look for four things: the correct queue type, the correct add and remove behaviour, a valid empty test, and a valid full test. For a sequence question, show the state after each operation rather than jumping directly to the final answer. This exposes errors involving front and rear positions, wrap-around, or priority order.