Queues in COBOL

Queues

A queue is a linear structure which is accessible at both ends: you add items to one end and remove them from the other.

Imagine yourself lining up at the checkout counter in the supermarket. Add yourself to one end of the line and wait patiently. Finally, after paying for your groceries, remove yourself from the other end of the line. That's a queue.

The end where you add a new item is called the tail of the queue. The end where you remove an item is called the head.

We will ignore the irregularities that may occur in real life: you switch to a faster line; you go back to pick up some olives; you let someone wearing a black leather Harley-Davidson jacket butt in front of you. A true queue follows the first-in-first-out principle.

Queue Operations

Classically a queue allows only two operations:

Enqueue -- add an item to the tail.

Dequeue -- remove an item from the head.

You can also provide a head operation to examine the item at the head without removing it.

You may want to dequeue an item and then, possibly after modifying it, to put it back at the head of the queue. That's cheating, and you're not supposed to do it, because then you don't really have a queue any more. But if it's useful to provide a requeue operation, then do it.

Implementing a Queue

There are three main ways to implement a queue:

Simple arrays. Keep the head at position 1, and maintain an index or subscript to keep track of the tail. Make sure you don't overflow the array. Whenever you dequeue an item, shift the entire array down by one position.
Alternatively you can keep the tail at position 1, and use an index or subscript to keep track of the head. Whenever you enqueue an item, shift the entire array up by one position.

Circular arrays. Use one index or subscript to keep track of the head, and another to keep track of the tail. When you enqueue, increment the tail index; when you dequeue, decrement the head index (or vice versa). Whenever you hit either end of the array, wrap around to the other end.
This approach is more efficient than a simple array because you don't have to shift the contents around. On the other hand it is more complicated. It's a little tricky to handle the wrap-around, or to recognize an empty queue, or a full one.

Linked lists. Maintain a singly-linked list with a pointer to the head and a pointer to the tail. The item at the head points to the next item; the item at the tail points to NULL.

The linked list is simplest to code. If you use a free list to minimize the overhead of allocation and deallocation, its performance will be acceptable for all but the most demanding applications. If performance is critical, a circular array will probably be the best choice.

Uses for Queues

A queue channels items from one or more sources to one or more sinks. A source is anything which provides something to be further processed. A sink is whatever does the further processing. For example, a source might read and select records from a file; a sink might write them to a report.

We don't usually need a queue to connect a source and a sink. We just process each item as we get it; they don't have to wait in line.

Queues are useful mainly when there is some sort of mismatch between the source and the sink. For example, the source may provide a variable number of items each time we invoke it. There may be multiple sources or multiple sinks, or both.

Sometimes (though not in mainframe COBOL), the source is asynchronous. That is, the source may provide input at any time, even when the sink is in the middle of doing something else.

For example, a PC keyboard may report keystrokes at any time. The operating system pauses briefly to enqueue each keystroke, and then returns control to whatever application is running. Eventually, in its own good time, the application dequeues the next keystroke (if any) and attends to it. Other events are enqueued from the mouse, the disk drive controller, and other devices, and from various elements of software.

COBOL Home

Data Structures