Beginning Algorithms

Chapter 5. Stacks

Now that you are familiar with lists and queues, it's time to move on to describing stacks. You are probably familiar with some real-world examples of stacks: Plates are usually stacked—you place the first one on the shelf and add to the top. If you need a plate, you remove the top one first. The newspapers at your local convenience store are stacked, as are the books on your desk that you've been meaning to read.

Stacks can also be used to implement a simple Most-Recently-Used (MRU) cache and are often used for parsing programming languages.

This "everything stacks" chapter will familiarize you with the following topics:

• What stacks are

• What stacks look like

• How you use stacks

• How stacks are implemented

We start by introducing the basic operations of a stack. We then cover the tests required to validate the correctness of any stack implementation. Finally, you'll look at the most common form of stack, based on a list.

Stacks

A stack is like a list with access restricted to one end. Figure 5-1 shows a graphical representation of a stack.

Figure 5.1. A stack is pictured vertically.

You'll notice that whereas lists and queues are usually thought of as running from left to right, stacks are pictured vertically—hence, the term "top" to refer to the first and only directly accessible element of a stack. A stack both inserts (pushes) and deletes (pops) from the top.

A stack is also ...