|
Stacks and queues are among the simplest of all data structures, but 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 micro-instructions inside a CPU. They are central to some important features of modern computing environments, like the Java run-time environment called the Java Virtual Machine. 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 Java Virtual Machine. 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 interfaces, casting, sentinels, and the adapter pattern. We conclude this chapter with a case study that uses the stack data structure to build a simple stock analysis application. |