Home Page

Chapter 4: Stacks, Queues, and Recursion

Cell

Stacks and queues are among the simplest of all data structures, but they are also among the most important. Stacks and queues are used in a host of different applications that include many more sophisticated data structures. In addition, stacks and queues are among the few kinds of data structures that are often implemented in the hardware microinstructions inside a CPU. In fact, there are some CPUs that have their entire assembly language based on the concept of performing operations on registers that are stored in a stack. Also, as we discuss in this chapter, the stack structure is used in the C++ run-time system, and the queue structure is used in most operating systems. Thus, the stack and queue structures are central to many important features of modern computing environments.

In this chapter, we define stack and queue abstract data types in a general way and we give two alternative implementations for them: arrays and linked lists. To illustrate the usefulness of stacks and queues, we present examples of their application to realizations of the C++ run-time system. We also present a generalization of stacks and queues, called the double-ended queue, and show how it can be implemented using a doubly linked list.

In addition, this chapter includes discussions of several programming concepts, including recursion, interfaces, casting, sentinels, and the adapter pattern. Indeed, we begin this chapter with a general discussion of how to use recursion and we explain in the subsequent section how recursion can be implemented with the stack data structure. We discuss linear recursion, higher-order recursion, and how to analyze recursive algorithms using recursion traces.