Mastering Algorithms with C

Implementation and Analysis of Queues

The structure Queue is the queue data structure. It is implemented as a typedef to List (see Example 6.3), just as was described for stacks.

Example 6.3. Header for the Queue Abstract Datatype

/*****************************************************************************
*                                                                            *
*  ------------------------------- queue.h --------------------------------  *
*                                                                            *
*****************************************************************************/

#ifndef QUEUE_H
#define QUEUE_H

#include <stdlib.h>

#include "list.h"

/*****************************************************************************
*                                                                            *
*  Implement queues as linked lists.                                         *
*                                                                            *
*****************************************************************************/

typedef List Queue;

/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/

#define queue_init list_init

#define queue_destroy list_destroy

int queue_enqueue(Queue *queue, const void *data);

int queue_dequeue(Queue *queue, void **data);

#define queue_peek(queue) ((queue)->head == NULL ? NULL : (queue)->head->data)

#define queue_size list_size

#endif

queue_init

The queue_init operation initializes a queue so that it can be used in other operations (see Example 6.3). Since a queue is a linked list and requires the same initialization, queue_init is defined to list_init ...