Chapter 5. Stacks, Queues, and Deques

Stacks, Queues, and Deques

Contents

5.1 Stacks

194

5.1.1 The Stack Abstract Data Type

195

5.1.2 The STL Stack

196

5.1.3 A C++ Stack Interface

196

5.1.4 A Simple Array-Based Stack Implementation

198

5.1.5 Implementing a Stack with a Generic Linked List

202

5.1.6 Reversing a Vector Using a Stack

203

5.1.7 Matching Parentheses and HTML Tags

204

5.2 Queues

208

5.2.1 The Queue Abstract Data Type

208

5.2.2 The STL Queue

209

5.2.3 A C++ Queue Interface

210

5.2.4 A Simple Array-Based Implementation

211

5.2.5 Implementing a Queue with a Circularly Linked List

213

5.3 Double-Ended Queues

217

5.3.1 The Deque Abstract Data Type

217

5.3.2 The STL Deque

218

5.3.3 Implementing a Deque with a Doubly Linked List

218

5.3.4 Adapters and the Adapter Design Pattern

220

5.4 Exercises

223

Stacks

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. Objects can be inserted into a stack at any time, but only the most recently inserted (that is, "last") object can be removed at any time. 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 ...

Get Data Structures and Algorithms in C++, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.