• Choose a category
• All
• Classic-Fiction

0if enqueuing the element is successful, or -1 otherwise.

Description

Enqueues an element at the tail of the queue specified by queue. The new element contains a pointer to data, so the memory referenced by data should remain valid as long as the element remains in the queue. It is the responsibility of the caller to manage the storage associated with data.

Complexity

O (1)

Name

queue_dequeue

Synopsis

intqueue_dequeue(Queue *queue, void **data);

Return Value

0if dequeuing the element is successful, or -1 otherwise.

Description

Dequeues an element from the head of the queue specified by queue. Upon return, data points to the data stored in the element that was dequeued. It is the responsibility of the caller to manage the storage associated with the data.

Complexity

O (1)

Name

queue_ peek

Synopsis

void*queue_peek(const Queue *queue);

Return Value

Data stored in the element at the head of the queue, or NULL if the queue is empty.

Description

Macro that evaluates to the data stored in the element at the head of the queue specified by queue.

Complexity

O (1)

Name

queue_size

Synopsis

int queue_size(const Queue *queue);

Return Value

Number of elements in the queue.

Description

Macro that evaluates to the number of elements in the queue specified by queue.

Complexity

O (1)

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

#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