DualArrayDeque: Building a Deque from Two Stacks

Learn how to implement the DualArrayDeque data structure.

Next, we present a data structure, the DualArrayDeque that achieves the same performance bounds as an ArrayDeque by using two ArrayStacks. Although the asymptotic performance of the DualArrayDeque is no better than that of the ArrayDeque, it is still worth studying, since it offers a good example of how to make a sophisticated data structure by combining two simpler data structures.

Two ends of a DualArrayDeque

A DualArrayDeque represents a list using two ArrayStacks. Recall that an ArrayStack is fast when the operations on it modify elements near the end. A DualArrayDeque places two ArrayStacks, called front and back, back-to-back so that operations are fast at either end.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy