Summary: This reading introduces the concept of the queue abstract data type and provides experience with an array implementation and a stack implementation of this ADT.


The Queue Abstract Data Type

The stack abstract data type, described in the reading on stacks, introduced the concept of an abstract data type and discussed the stack as an example that stored and retrieved data in a first-in, last-out (FILO) manner. This lab describes a queue ADT that stores and retrieves data in a first-in, first-out (FIFO) manner.

This queue ADT models the checkout counter of a store. A clerk works with one customer at a time, until the customer's bill has been computed and paid. Then the clerk goes on to the next customer. In this situation, while the customer is being served by the clerk, other customers may get into the checkout line to wait for their turn. Normally, customers do not get into line until they have selected all items they wish to buy, and once a customer gets into line, the customer waits until the clerk finishes with those ahead. When we consider this processing at the cash register, we can identify these characteristics.

  1. Customers wait in a line to be served.
  2. Customers leave the line at one end (the front), when they have been served by the clerk.
  3. Customers enter the line at the other end (the rear).
  4. Occasionally, a line may be empty.

In addition, if a line becomes too long, customers may decide to purchase their items at another time rather than wait in line. In this situation, we might want to specify a maximum size for the queue, and we might want to test whether the queue is full.

Unlike stacks where the operational names Push and Pop are standard, the operations for queues are commonly called by several names. For example, the addition of a customer to a queue may be called Enter, Insert, or Enqueue; the leaving of a customer after being served may be called Delete, Remove, or Dequeue. For parallelism in terminology, we use Enqueue and Dequeue here.

More formally, a queue is defined as the abstract data type that has data of a specified type, and operations described as follows:

Determine whether the queue is empty; return true if it is and false if it is not.
Add a new element at the rear of a queue.
Remove an element from the front of the queue and return it. (This operation cannot be performed if the queue is empty.)
Return the element at the front of the queue (without removing it from the queue). (Again, this operation cannot be performed if the queue is empty.)

Normally, queue operations do not allow access to the last or middle items on the queue, only the first. As with stacks, you can only look at an item at one end of the collection.

With these operations, queues provide a rather different pattern of data storage and retrieval than we find with stacks. In particular, once an item is placed on a queue, the item is not retrieved until all items ahead of it have already been removed. Here, the first item placed into a queue is the first one processed, and subsequent items must wait for their turn. We say queues provide first-in, first-out (FIFO) storage or Last-in, Last-out (LILO) storage, in contrast to the FILO storage of stacks.

Array-based Queue Implementation

As with stacks, one common implementation of a queue involves the use of an array. Although this implementation is reasonably straightforward, a few details require some care.

Our basic approach is fairly simple. We can think of an array as extending to the right indefinitely, and we store our data items in order in this array. We use variables first and last to mark where our first element was added and where the last or most recent element was added. The following figure shows this setup, where we have placed four items on the queue. In the figure, item 0 was inserted first, followed by item 1, item 2, and item 3 in that order. The first item is marked by the variable first and the final item added is marked by last.

Conceptual Queue Implementation
Conceptual Array-based Queue Implementation

From this figure, we can trace what happens in our enqueue and dequeue operations. For the enqueue operation, we must add 1 to last to mark a new end for the queue, and insert the specified item at this new location. Similarly, to dequeue, we must return the first item specified, and add 1 to first to to mark the new head of the queue. With this basic picture, assuming we start with last equal to -1, we can tell whether a queue is empty by checking that first > last. Further, in this figure, the queue has enough space, so it is never full.

In practice, this basic algorithm is complicated by the limitation that an array has a finite size; the array does not extend indefinitely to the right. With this limitation, we have two choices.

  1. When we delete an item from the queue, we could move all of the other items to the left to fill in the extra space. In this way, data in our queue would always start at the left end of our array, and we could keep inserting new items until the array was full. No space would be wasted.
  2. We could think of the element at position 0 of the array as following the last element. When last gets to the end of the array, we reuse any space that has been left at the beginning of the array when items have been removed. This approach is shown in the figure below. Here items 1 through n are waiting in an array, and some room is available at the start of the array. When a new item is added, there is no room at the right end of the array, so we reset last to 0 and add the new item in the vacant space at the start.
queue with last item at the end of the array
Queue with the last item at the end of the array
queue after insert wrapped to front of the array
Queue after insert wrapped to the front the array

Of these two alternatives, the first approach involves much shifting of data and thus is rather inefficient. The second approach allows our code to run much more quickly; however, we need to ensure that we do not store new items on top of old ones, before the old ones are deleted from the queue. This check can be handled in several ways. One of the easiest is to keep a count of the number of items waiting in the queue. When this number reaches the maximum size of the array, the array is full, and further insertions are impossible. This count also allows us to check whether the queue is empty.

Queues in C

As with the implementation of stacks, our implementation of queues in C uses a struct to package together the various variables needed:

#define MAX_QUEUE_SIZE 50
/* size of all queue arrays */

typedef struct {
  int first;
  int last;
  int count;
  char * queueArray[MAX_QUEUE_SIZE];
} stringQueue;

Also, in this code, we need to be able to increment first and last by 1 easily, with the first element of the array following the last array element. Using MAX_QUEUE_SIZE as the size of the array, then this incrementing can be done using modular arithmetic. For example, if myQueue has type stringQueue, then incrementing first would use the statement:

myQueue.first = (myQueue.first + 1) % MAX_QUEUE_SIZE;

List-based Queue Implementation

The second approach for implementing queues resolves some of these queue size problems by using the dynamic storage allocation that is available through the use of pointers. As with the discussion of stacks, we want to retain the same operations and calling formats defined earlier when queues were implemented by arrays. In particular, the queue operations should include the following functions:

initialize (stringQueue * queue);

isEmpty (const stringQueue * queue);

isFull (const stringQueue * queue);

enqueue (stringQueue * queue, char * item);
/* returns whether item was successfully enqueued */

char *
dequeue (stringQueue * queue)
/* returns string removed from queue */

In this structure, we must work with both ends of the queue, inserting items at the tail and deleting them from the head. Here, we view the queue as ordering items from the head to the tail; the head is the first item we will remove, and the tail is the last item. The following figure shows how this might work.

A List/Pointer Implementation of a Queue
A list/pointer implementation of a queue.

In this picture, the queue consists of a list of records, where each record contains an item of data and each record points to the record that comes after it. In addition, for the overall queue, the items at the front and back of the queue must be specified. The appropriate declarations are as follows.

typedef struct node {
  char * data;
  struct node * next;
} queueNode;

typedef struct {
  queueNode * head;
  queueNode * tail;
} stringQueue;

With these declarations, initialization sets head and tail to NULL at the start of the program, and the boolean expression (queue.head == NULL) tests whether the queue is empty. The enqueue operation then proceeds by adding an element at the tail end of the list. Also, the dequeue operation proceeds by returning the data at the head of the list, moving the head pointer to the next element, and disposing of the old record. Each of these operations also requires some care for processing the special cases when the queue is empty and when it contains only one item.