Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

Section 3.15 Deques

A deque, (pronounced “deck”), also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a head and a tail, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the head or the tail. Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure. Figure 3.15.1 shows a deque of Java String objects.
It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you to make consistent use of the addition and removal operations.
Figure 3.15.1. A Deque of Java Strings
You have attempted of activities on this page.