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.
/***************************************************************************** * * * ------------------------------- 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.
The runtime complexity of queue_init is the same as list_init, or O (1).
queue_destroy
The queue_destroy operation destroys a queue (see Example 6.3). Since a queue is a linked list and requires being destroyed in the same manner, queue_destroy is defined to list_destroy.
The runtime complexity of queue_destroy is the same as list_destroy, or O (n), where n is the number of elements in the queue.
queue_enqueue
The queue_enqueue operation
enqueues an element at the tail of a queue by calling
list_ins_next to insert an element pointing to
data at the tail of the list (see Example 6.4).
The runtime complexity of queue_enqueue is the same as list_ins_next, or O (1).
queue_dequeue
The queue_dequeue operation
dequeues an element from the head of a queue by calling
list_rem_next to remove the element at the head of the list (see
Example 6.4). The
list_rem_next operation sets
data to point to the data from the
element removed.
The runtime complexity of queue_dequeue is the same as list_rem_next, or O (1).
queue_ peek, queue_size
These macros implement two simple queue operations
(see Example 6.3). The
queue_ peek macro provides a way to inspect the
element at the head of a queue without actually dequeuing it, and
queue_size evaluates to the size of a queue.
Both of these operations work by accessing members of the
Queue structure.
The runtime complexity of these operations is O (1) because accessing members of a structure is a simple task that runs in a constant amount of time.
/*****************************************************************************
* *
* ------------------------------- queue.c -------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include "list.h"
#include "queue.h"
/*****************************************************************************
* *
* ----------------------------- queue_enqueue ---------------------------- *
* *
*****************************************************************************/
int queue_enqueue(Queue *queue, const void *data) {
/*****************************************************************************
* *
* Enqueue the data. *
* *
*****************************************************************************/
return list_ins_next(queue, list_tail(queue), data);
}
/*****************************************************************************
* *
* ----------------------------- queue_dequeue ---------------------------- *
* *
*****************************************************************************/
int queue_dequeue(Queue *queue, void **data) {
/*****************************************************************************
* *
* Dequeue the data. *
* *
*****************************************************************************/
return list_rem_next(queue, NULL, data);
}