Beginning Programming ALL-IN-ONE DESK REFERENCE FOR DUMMIES®

Chapter III.4. Stacks, Queues, and Deques

Collections and dictionaries are best suited for storing and organizing data, but they aren't as useful for retrieving data in an orderly fashion. Trying to keep track of data stored by index numbers or by keys can get cumbersome. As a simpler alternative, computer scientists have created three other data structures:

• Stacks

• Queues

• Deques

Unlike collections or dictionaries, these three data structures are designed for storing and removing data in a predictable order.

Using a Stack

The stack data structure gets its name because it resembles a stack of clean dishes, typically found in a cafeteria. When you put the first plate on the counter, that plate appears at the bottom of the stack. Each time you add a new plate to the stack, the first plate gets buried farther underneath. Add another plate to the stack, and the newest plate appears on top. To remove a plate, you have to take the top plate off.

That's the same way the stack data structure works, as shown in Figure 4-1. With a stack, you don't keep track of the data's location. Instead, you can keep adding new data to store, and the stack expands automatically.

Figure III.4-1. Stacks store the oldest data on the bottom and the newest data on top.

The only way to remove data from a stack is from its top. Each time you remove data, the stack shrinks automatically. Because a stack only lets you remove ...