Chapter 5. Stacks, Queues, and Deques
![Stacks, Queues, and Deques](/api/v2/epubs/9780470383278/files/figs/U0501.png)
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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.