Data Structures Demystified (Demystified)

2017-07-07 02:10:07

The term stack is one of the magical and sometimes imposing terms used in computer programming that seems to imply an abstract concept that only a Ph.D. from MIT ”whoops, we should say Columbia University ”can understand. Yet you actually know all about stacks because you use a stack when playing cards, making pancakes, and storing laundry. A stack is the way you groups things together by placing one thing on top of another and then removing things one at a time from the top of the stack. It is amazing that something this simple is a critical component of nearly every program that is written. In this chapter, you ll learn how to create and use a stack in your programs.

A Stack

When you hear the term stack used outside the context of computer programming, you might envision a stack of dishes on your kitchen counter. This organization is structured in a particular way: the newest dish is on top and the oldest is on the bottom of the stack.

Each dish in a stack is accessed using fifo: first in, first out. The only way to access each dish is from the top of the stack. If you want the third dish (the third oldest on the stack), then you must remove the first two dishes from the top of the stack. This places the third dish at the top of the stack making it available to be removed.

There s no way to access a dish unless the dish is at the top of the stack. You might be thinking stacks are inefficient, and you d be correct if the objective was to randomly access things on the stack. There are other data structures that are ideal for random access, which you ll learn about throughout this book.

However, if the object is to access things in the order in which they were placed on the stack, such as computer instructions, stacks are efficient. In these situations, using a stack makes a lot of sense.

Note

Stacks and arrays are often bantered about in the same discussion, which can easily lead to confusion, but they are really two separate things (see Figure 4-1). An array stores values in memory; a stack tracks which array element is at the top of the stack. When a value is popped off the stack, the value remains in memory because the value is still assigned to an array element. Popping it only changes the array element that is at the top of the stack.

Figure 4-1: A stack and an array are two different things: an array stores values in memory; a stack tracks which of the array elements is at the top of the stack.

A Stack

Категории