Queue implemented with a simply linked list

Prerequisites

Read about linked lists, stacks, and sentinels first.

Introduction

A queue is an abstract data type only slightly more complicated than a stack. In this section, we use a linked list with a sentinel to implement a queue.

What is a queue

A queue is also known as a FIFO, which stands for first in first out. It is a container with only three operations: enqueue, dequeue, first and empty.

Conceptually, a queue contains elements that are inserted by the enqueue operation and deleted by the dequeue operation in the same order that they were inserted. In other words, the first element to be deleted is the first one inserted. The first operation returns the first element that was inserted without affecting the contents of the queue. Finally, the empty operation is a predicate to test whether the queue has zero elements.

Here, we shall actually use only three operations, enqueue, dequeue, and empty. We will have the dequeue also do the work of first by returning the object about to be deleted.

By now, the reader should be used to using header objects in order to obtain uniform reference semantics. We will therefore go directly to a version of the queue with a separate header file and implementation file.

The header file

Without further comments, here is the header file:
  #ifndef QUEUE_H
  #define QUEUE_H

  struct queue;
  typedef struct queue *queue;

  /* create an empty queue */
  extern queue queue_create(void);

  /* insert an element at the end of the queue */
  extern void queue_enq(queue q, void *element);

  /* delete the front element on the queue and return it */
  extern void *queue_deq(queue q);

  /* return a true value if and only if the queue is empty */
  extern int queue_empty(queue q);

  #endif

The implementation file

First, let us study an implementation without any particular tricks. Here is a possibility:
  #include "queue.h"
  #include "list.h"
  #include < stdlib.h>

  struct queue
  {
    list head;
    list tail;
  };

  queue
  queue_create(void)
  {
    queue q = malloc(sizeof(struct queue));
    q -> head = q -> tail = NULL;
    return q;
  }

  int
  queue_empty(queue q)
  {
    return q -> head == NULL;
  }

  void
  queue_enq(queue q, void *element)
  {
    if(queue_empty(q))
      q -> head = q -> tail = cons(element, NULL);
    else
      {
        q -> tail -> next = cons(element, NULL);
        q -> tail = q -> tail -> next;
      }
  }

  void *
  queue_deq(queue q)
  {
    assert(!empty(q));
    {
      void *temp = q -> head -> element;
      q -> head = cdr_and_free(q -> head);
      return temp;
    }
  }
In the createoperation, we use the fact that in C, the assignment operation is an expression (and thus has a value) in order to shorted the code by one line. The value of q -> tail = NULL is itself NULL, which can be used as a value to assign to q -> head. A similar trick is used in the enq operation.

The head field in the queue structure points to the first cell of the list, which corresponds to the head of the queue (from where elements are dequeued), and the tail field points to the last cell of the list, which corresponds to the tail of the queue (where elements are enqueued). Notice the special case necessary when the queue is empty before an enqueue operation. After a dequeue operation resulting in an empty queue, the tail field will point to a list cell that is no longer allocated. This might be a problem if a garbage collector is used, as it might keep that cell (and worse, its contents) alive even though it will never be used again. In that case, another special case must be introduced in the dequeue operation, like this:

  void *
  queue_deq(queue q)
  {
    assert(!empty(q));
    {
      void *temp = q -> head -> element;
      q -> head = cdr_and_free(q -> head);
      if(empty(q))
        q -> tail = NULL;
      return temp;
    }
  }

Using a sentinel in the implementation

Now, let us see how we can use a sentinel to simplify the implementation. The sentinel will be located at the end of the list and will never be deleted. When a new element is inserted, a new cell is inserted after the sentinel. The new element to be inserted is then placed in the cell of the old sentinel, and the newly allocated cell (which is last on the list) becomes the sentinel. Here is the code:
  #include "queue.h"
  #include "list.h"
  #include < stdlib.h>

  struct queue
  {
    list head;
    list tail;
  };

  queue
  queue_create(void)
  {
    queue q = malloc(sizeof(struct queue));
    q -> head = q -> tail = cons(NULL, NULL);
    return q;
  }

  int
  queue_empty(queue q)
  {
    return q -> head == q -> tail;
  }

  void
  queue_enq(queue q, void *element)
  {
    q -> tail -> next = cons(NULL, NULL);
    q -> tail -> element = element;
    q -> tail = q -> tail -> next;
  }

  void *
  queue_deq(queue q)
  {
    assert(!empty(q));
    {
      void *temp = q -> head -> element;
      q -> head = cdr_and_free(q -> head);
      return temp;
    }
  }
With this version no special case is needed, neither in the enqueue operation nor in the dequeue operation. And the dequeue operation works fine with a garbage collector as well. The code for the enqueue operation is now 7 lines instead of 11.