7.2 Queues

A queue is a list of records in which records are inserted at one end of the list (the tail or rear of the list), and records are extracted and deleted from the other end (the head or front of the list). A queue has the First-In-First-Out (FIFO) property: records are removed from the list in the same order as they arrive. An insertion of a record is said to enqueue it; similarly, deletion dequeues a record.

For example, assume that the names Alice, Bobby, Cindy, and David are enqueued in this order onto an initially empty queue:

If a dequeue operation were performed, then Alice would be deleted; if Ellen were then enqueued, the queue would become:

If implemented as a linear array, a queue would crawl through memory as records were added and deleted. Even if the queue never held more than two records at any time, the queue might exhaust all the memory allocated for it!

The circular queue offers a simple solution to this problem. A circular queue is simply a queue consisting of a finite number of memory locations together with pointers, Rear and Front, that point to the last character enqueued and dequeued and "wrap around" from the last to the first memory location assigned to the queue.

For example, suppose the message CIRCULAR QUEUES! has been enqueued onto a queue of length QLen = 20 bytes that was initially empty, and that the first 3 characters have been dequeued. The 20 memory locations assigned to the queue would then contain:

At this point, additional characters may be dequeued until the queue is empty, and additional characters may be enqueued until the queue is full. The empty/full conditions may be deduced from the relative positions of the Front and Rear pointers: since Front=Rear may mean either empty or full, Rear is usually allowed to advance only to just before Front; then Front=Rear means empty, Rear=Front-1 (mod QLen) means full. The maximum usable queue length is QLen-1 when this method is used. Alternately, the number of characters currently in the queue can be monitored - as in the example below.

If several identical queues are used, the queue parameters can be specified conveniently in a STRUCture:

QLen    equ     512     ; queue length

STRUC   QSpec
.Front  resw    1       ; index to last char. dequeued
.Rear   resw    1       ; index to last char. enqueued
.QBeg   resw    1       ; pointer to first byte of queue
.Count  resw    1       ; # of bytes currently in queue
.NMsgs  resw    1       ; # of messages pending
....
ENDSTRUC

Two queues (e.g., a Transmit Queue TQ and a Receive Queue RQ) are then specified as follows:

TQBeg   resb    QLen    ; TQ Space
RQBeg   resb    QLen    ; RQ Space
TQ      istruc QSpec
        at .Front, dw -1
        at .Rear, dw -1
        at .QBeg, dw TQBeg
        at .Count, dw 0
        at .NMsgs, dw 0
        ....
        iend
RQ      istruc QSpec
        at .Front, dw -1
        at .Rear, dw -1
        at .QBeg, dw RQBeg
        at .Count, dw 0
        at .NMsgs, dw 0
        ....
        iend

The use of the QSpec structure simplifies references to the queue parameters: e.g., TQ+QSpec.Front refers to the front pointer of the Transmit Queue, and RQ+QSpec.NMsgs refers to the number of messages pending in the Receive Queue.

Outlines of subroutines to enqueue and dequeue a character, using QLen and the QSpec defined above, are shown below: