Queues revision notes

Queue operations

A queue is a data structure on which four important operations must be understood: adding an item, removing an item, testing whether it is empty, and testing whether it is full. Adding an item is commonly called enqueue and removing an item is commonly called dequeue. These operations must follow the rules of the particular queue type.

Linear queues

A linear queue has a logical front, where an item is removed, and a logical rear, where a new item is added. Items are removed in the order in which they were added. To add an item, place it at the rear and update the rear position. To remove an item, take the item at the front and update the front position. An empty test checks whether the queue contains no items. A full test checks whether the next addition would exceed the available linear storage.

A common issue with a linear queue is that positions at the beginning may become unused after removals. If the implementation does not reuse those positions, the queue can reach its linear limit even though some earlier storage positions are empty. This is an important distinction from a circular queue.

Circular queues

A circular queue treats the storage as if the end connects back to the beginning. When the rear reaches the final position, a new item may use an available position at the beginning. This reuses space released by removals. Adding still occurs at the rear and removing still occurs at the front, but position updates wrap around the storage.

The implementation must distinguish an empty circular queue from a full circular queue. For example, it may maintain enough information about the number of stored items or use a clearly defined position rule. The important exam point is that wrapping around does not by itself prove that the queue is empty or full; the selected condition must be tested consistently.

Priority queues

A priority queue does not necessarily remove items in arrival order. Each item has a priority, and removal selects an item according to the queue's priority rule. Adding an item places it into the priority queue in a way that preserves the required priority arrangement, or records it so that the correct item can be selected later. Removing an item selects the item with the appropriate priority and updates the queue. Empty and full tests still apply.

Worked reasoning

Suppose a queue has storage positions 0 to 3. In a linear queue, after items at positions 0 and 1 are removed, later additions may use positions 2 and 3; position 0 is not automatically reused. In a circular queue, if position 0 is available when the rear passes position 3, the next addition can wrap to position 0. In a priority queue, the next removal is decided by priority rather than simply by which remaining item arrived first.

Common errors

• Treating every queue as strictly first-in-first-out, including a priority queue.
• Confusing the front, where removal occurs, with the rear, where addition occurs.
• Assuming that a circular queue is full merely because the rear has reached the final array position.
• Failing to test for empty before removing an item.
• Describing a full test without considering the queue's available storage and its representation.