Queue ADT

A QUEUE is a one-way linear list in which insertion is restricted to one end and deletion to the other, eg:


We assume that the name of the queue gives access to the last node as well as the first node.  To refer to the first node we can write:         exqueue.front and to the last node: exqueue.rear

We can  modify the addition and deletion primitives as follows:

add(exqueue) (similar to push(exstack))

QO-addfor an empty queue:


remove(exqueue)       (similar to pop(exstack))

QP-removefor a queue with only one node:

QP-remove one

We assume that we can test for an empty queue: emptyqueue(exqueue) returns true if exqueue is empty, false otherwise.

Other names for a queue are first-in first-out (FIFO) list or last-in last-out (LILO) list.

For example: copy queue old into queue new preserving the order of the nodes and deleting the nodes of old.


while not emptyqueue(old) do
   new.rear = old.front

Normally some processing of attribute values would also be involved.

Other queue primitives are similar to the stack primitives:

accessfirst(exqueue, exav)

accessnext(exqueue, exav)