Queue ADT

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

Queue

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:

QP-add-empty

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.


createqueue(new)

while not emptyqueue(old) do
{
   add(new)
   new.rear = old.front
   remove(old)
}

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)

createqueue(exqueue)

 destroyqueue(exqueue)

 Next: