Data Structures and Algorithms in C++, Second Edition

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