• Choose a category
• All
• Classic-Fiction

By Root 1542 0

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.

Example 6.4. Implementation of the Queue Abstract Datatype

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

* *

* ------------------------------- queue.c -------------------------------- *

* *

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

#include

#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);

}

Queue Example: Event Handling

One popular application of queues is handling events in event-driven applications. Event-driven applications execute largely under the direction of real-time occurrences called events. In a graphical user interface developed in Java, X, or Windows, for example, the behavior of an application depends a great deal on key presses, mouse movements, and other events triggered by the user. Other examples of event-driven applications occur frequently in control systems such as those found in aircraft or factory equipment.

In nearly all event-driven applications, events can occur at any moment, so queues play an important role in storing events until an application is ready to deal with them. A queue works well for this because applications handle events more or less in the same order as they occur.

Example 6.5 presents two functions for handling events: receive_event and process_event . Both functions operate on a queue containing events of type Event. Event is defined in event.h, which is not shown. An application calls receive_event to enqueue an event it has been notified about. Exactly how an application is notified of an event varies, but notification often begins with a hardware interrupt. When the application decides it is time to process an event, it calls process_event. Inside of process_event, an event is dequeued from the event queue and is passed to an application-specific dispatch function. The dispatch function is passed to process_event as the parameter dispatch. The purpose of the dispatch function is to take the appropriate action to handle the event. There are two approaches dispatch can take to do this: it can process the event synchronously, so that no other processing is performed until handling the event is completed; or it can process the event asynchronously, in which case it starts a separate process to handle the event while the main process moves on. Asynchronous event handling usually is more efficient, but it requires particularly careful coordination between the main and subordinate processes.

The runtime complexity of receive_event is O (1) because it simply calls the O (1) queue operation queue_enqueue. The runtime complexity of process_event depends on the dispatch