O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required