Data Structures and Algorithms in Java, 6th Edition

Chapter 6

Stacks, Queues, and Deques

Contents

6.1 Stacks

6.1.1 The Stack Abstract Data Type

6.1.2 A Simple Array-Based Stack Implementation

6.1.3 Implementing a Stack with a Singly Linked List

6.1.4 Reversing an Array Using a Stack

6.1.5 Matching Parentheses and HTML Tags

6.2 Queues

6.2.1 The Queue Abstract Data Type

6.2.2 Array-Based Queue Implementation

6.2.3 Implementing a Queue with a Singly Linked List

6.2.4 A Circular Queue

6.3 Double-Ended Queues

6.3.1 The Deque Abstract Data Type

6.3.2 Implementing a Deque

6.3.3 Deques in the Java Collections Framework

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