Understand the queue abstract data type, FIFO behaviour, linear, circular and priority queues, and the enqueue and dequeue operations using front and rear pointers.

What this dot point is asking

AQA wants you to describe a queue as an abstract data type with first-in first-out behaviour, distinguish linear, circular and priority queues, and trace the enqueue and dequeue operations using front and rear pointers.

The queue abstract data type

The main operations are enqueue (add an item at the rear), dequeue (remove and return the item at the front), isEmpty and isFull. Two pointers track the front and rear positions. The contrast with a stack is the key idea: a stack works at one end (LIFO) while a queue works at both ends (FIFO), which is why the two structures suit completely different jobs.

Linear and circular queues

ENQUEUE(item):
  IF NOT isFull THEN
    rear = (rear + 1) MOD size
    queue[rear] = item

DEQUEUE():
  IF NOT isEmpty THEN
    item = queue[front]
    front = (front + 1) MOD size
    RETURN item

A subtle point with circular queues is telling apart a full queue from an empty one, because in both the front and rear pointers can coincide. This is usually handled by keeping a separate count of items, or by leaving one slot unused as a sentinel. Examiners reward awareness that the wrap-around creates this ambiguity.

Priority queues

A priority queue removes items in order of priority rather than arrival order. Each item has a priority, and dequeue returns the highest-priority item; items of equal priority are served in FIFO order. Priority queues are used in process scheduling, where urgent tasks must run first, and in algorithms such as Dijkstra's shortest path, where the next vertex to process is always the one with the smallest tentative distance. They can be implemented by keeping the list sorted on insertion, or with a heap for efficiency.

Like a stack, a queue is an abstract data type, so the array implementation shown here is only one option; a queue can equally be built from a linked list, where enqueue adds a node at the tail and dequeue removes one from the head, growing dynamically rather than being bounded by a fixed array. The abstract behaviour (FIFO, with enqueue, dequeue, isEmpty and isFull) is what defines it, and a programmer picks the implementation to suit the situation.

Queues are everywhere in systems software because they buffer between a producer and a consumer that work at different rates. A keyboard buffer holds keystrokes until the program is ready to read them; a print spooler queues documents so they print in the order submitted; and network equipment queues packets waiting to be forwarded. In each case the FIFO discipline is what guarantees fairness, processing requests in the order they arrived, which is the conceptual reason the queue is the right structure rather than a stack.