Chapter 6. Stacks and Queues
Often it is important to store data so that when it is retrieved later, it is automatically presented in some prescribed order. One common way to retrieve data is in the opposite order as it was stored. For example, consider the data blocks a program maintains to keep track of function calls as it runs. These blocks are called activation records. For a set of functions { f 1, f 2, f 3} in which f 1 calls f 2 and f 2 calls f 3, a program allocates one activation record each time one of the functions is called. Each record persists until its function returns. Since functions return in the opposite order as they were called, activation records are retrieved and relinquished in the opposite order as they were allocated. Another common way to retrieve data is in the same order as it was stored. For example, this might be useful with a bunch of things to do; often we want to do the first item first and the last item last. Stacks and queues are simple data structures that help in such common situations.
This chapter covers:
- Stacks
Efficient data structures for storing and retrieving data in a last-in, first-out, or LIFO, order. This allows us to retrieve data in the opposite order as it was stored.
- Queues
Efficient data structures useful for storing and retrieving data in a first-in, first-out, or FIFO, order. This allows us to retrieve data in the same order as it was stored.
Some applications of stacks and queues are:
- Semaphores
Programmatic devices for synchronizing access to shared resources. When a process encounters a semaphore, it performs a test to determine whether someone else is currently accessing the resource the semaphore protects. If so, the process blocks and waits until another process signals that the resource is available. Since many processes may be waiting on a resource, some implementations of semaphores use a queue to determine who is next to go.
- Event handling (illustrated in this chapter)
A critical part of real-time programming. In real-time systems, events frequently occur when the system is not quite ready to handle them. Therefore, a queue keeps track of events so that they can be processed at a later time in the order they were received.
- X Window System
A network-based, graphical window system in which graphics are displayed on servers under the direction of client programs. X is a specific example of a system that does event handling. To manage events, it uses a queue to store events until they can be processed.
- Producer-consumer problem
A generalization for modeling cooperating processes wherein one process, the producer, writes to a queue shared by another process, the consumer, which reads from it. The producer-consumer problem is a classic one to study because many applications can be described in terms of it.
- Function calls in C
An essential part of modular programming. When we call a function in a C program, an activation record containing information about the call is pushed onto a stack called the program stack. When a function terminates, its activation record is popped off the stack. A stack is the perfect model for this because when functions call one another, they return in the opposite order as they were called.
- Abstract stack machines
An abstraction used by compilers and hand-held calculators to evaluate expressions (see the example in Chapter 9).