• Choose a category
• All
• Classic-Fiction

stack_ peek, stack_size

These macros implement two simple stack operations (see Example 6.1). The stack_ peek macro provides a way to inspect the element at the top of a stack without actually popping it, and stack_size evaluates to the size of a stack. Both of these operations work by accessing members of the Stack 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.

Example 6.2. Implementation of the Stack Abstract Datatype

/*****************************************************************************

* *

* ------------------------------- stack.c -------------------------------- *

* *

*****************************************************************************/

#include

#include "list.h"

#include "stack.h"

/*****************************************************************************

* *

* ------------------------------ stack_push ------------------------------ *

* *

*****************************************************************************/

int stack_push(Stack *stack, const void *data) {

/*****************************************************************************

* *

* Push the data onto the stack. *

* *

*****************************************************************************/

return list_ins_next(stack, NULL, data);

}

/*****************************************************************************

* *

* ------------------------------ stack_pop ------------------------------- *

* *

*****************************************************************************/

int stack_pop(Stack *stack, void **data) {

/*****************************************************************************

* *

* Pop the data off the stack. *

* *

*****************************************************************************/

return list_rem_next(stack, NULL, data);

}

Description of Queues

The distinguishing characteristic of a queue is that it stores and retrieves data in a first-in, first-out, or FIFO , manner. This means that the first element placed in the queue is the first to be removed. A convenient way to think of a queue is as a line at the post office. In fact, anyone who has been to England knows that to form a line there is known colloquially as "queuing up." As the line grows, newcomers join in at the tail. When a clerk becomes available, the person at the head of the line goes next. In computing, to place an element at the tail of a queue, we enqueue it; to remove an element from the head, we dequeue it (see Figure 6.2). Sometimes it is useful to inspect the element at the head of a queue without actually removing it, in which case we peek at it.

Figure 6.2. A queue (1) with some elements already enqueued; (2) after enqueuing 8, 9, and 2; and (3) after dequeuing 5 and 3

Interface for Queues

Name

queue_init

Synopsis

void queue_init(Queue *queue, void (*destroy)(void *data));

Return Value

None.

Description

Initializes the queue specified by queue. This operation must be called for a queue before the queue can be used with any other operation. The destroy argument provides a way to free dynamically allocated data when queue_destroy is called. It works in a manner similar to that described for stack_destroy. For a queue containing data that should not be freed, destroy should be set to NULL.

Complexity

O (1)

Name

queue_destroy

Synopsis

void queue_destroy(Queue *queue);

Return Value

None.

Description

Destroys the queue specified by queue. No other operations are permitted after calling queue_destroy unless queue_init is called again. The queue_destroy operation removes all elements from a queue and calls the function passed as destroy to queue_init once for each element as it is removed, provided destroy was not set to NULL.

Complexity

O (n), where n is the number of elements in the queue.

Name

queue_enqueue

Synopsis

intqueue_enqueue(Queue *queue, const void *data);

Return Value