A Concise Introduction to Data Structures using Java

Chapter 5

Queues

5.1 Interface and Linked Implementation

The close counterpart of a stack is a queue. In (primarily) British usage, a queue is a waiting line. In computer science, a queue is a data structure that acts like a waiting line, in which items are removed from the front of the line, and new items are added to the rear of the line. A queue is a first-in, first-out (FIFO) data structure, because the first element in will be the first one out.

Adding to the rear of a queue is called enqueuing, and removing from the front of a queue is called dequeuing (pronounced “DQ-ing”). The front is drawn on the left here to match the linked lists ...