Data Structures and Algorithms in Python

Chapter 6

Stacks, Queues, and Deques

Contents

6.1 Stacks

6.1.1 The Stack Abstract Data Type

6.1.2 Simple Array-Based Stack Implementation

6.1.3 Reversing Data Using a Stack

6.1.4 Matching Parentheses and HTML Tags

6.2 Queues

6.2.1 The Queue Abstract Data Type

6.2.2 Array-Based Queue Implementation

6.3 Double-Ended Queues

6.3.1 The Deque Abstract Data Type

6.3.2 Implementing a Deque with a Circular Array

6.3.3 Deques in the Python Collections Module

6.4 Exercises

6.1 Stacks

A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle. A user may insert objects into a stack at any time, but may only access or remove the most recently inserted object that remains (at the so-called “top” of the stack). The name “stack” is derived from the metaphor of a stack of plates in a spring-loaded, cafeteria plate dispenser. In this case, the fundamental operations involve the “pushing” and “popping” of plates on the stack. When we need a new plate from the dispenser, we “pop” the top plate off the stack, and when we add a plate, we “push” it down on the stack to become the new top plate. Perhaps an even more amusing example is a PEZ^® candy dispenser, which stores mint candies in a spring-loaded container that “pops” out the topmost candy in the stack when the top of the dispenser is lifted (see Figure 6.1). Stacks are a fundamental ...