Tracing the Two Deques

Here is a sequence of operations on a deque of integers that starts out empty:

deque.addFirst(17);
deque.addLast(42);
deque.addFirst(28);
deque.removeLast();
deque.addLast(65);
deque.removeFirst();
deque.addFirst(31);
deque.addLast(53);

Solution

addFirst(17)

          ┌─────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 17 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └─────┘

addLast(42)

          ┌─────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 17 │ ◀──▶ │ 42 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └─────┘

addFirst(28)

          ┌─────┐      ┌────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 28 │ ◀──▶ │ 17 │ ◀──▶ │ 42 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └────┘      └─────┘

removeLast()

          ┌─────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 28 │ ◀──▶ │ 17 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └─────┘

addLast(65)

          ┌─────┐      ┌────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 28 │ ◀──▶ │ 17 │ ◀──▶ │ 65 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └────┘      └─────┘

removeFirst()

          ┌─────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 17 │ ◀──▶ │ 65 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └─────┘

addFirst(31)

          ┌─────┐      ┌────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 31 │ ◀──▶ │ 17 │ ◀──▶ │ 65 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └────┘      └─────┘

addLast(53)

          ┌─────┐      ┌────┐      ┌────┐      ┌────┐      ┌────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 31 │ ◀──▶ │ 17 │ ◀──▶ │ 65 │ ◀──▶ │ 53 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └────┘      └────┘      └────┘      └────┘      └─────┘

Solution

addFirst(17): front = 4, size = 1

┌────┬────┬────┬────┬────┐
│  _ │  _ │  _ │  _ │ 17 │
└────┴────┴────┴────┴────┘
                      ↑
                    front

addLast(42): front = 4, size = 2

┌────┬────┬────┬────┬────┐
│ 42 │  _ │  _ │  _ │ 17 │
└────┴────┴────┴────┴────┘
                      ↑
                    front

addFirst(28): front = 3, size = 3

┌────┬────┬────┬────┬────┐
│ 42 │  _ │  _ │ 28 │ 17 │
└────┴────┴────┴────┴────┘
                 ↑
               front

removeLast(): front = 3, size = 2

┌────┬────┬────┬────┬────┐
│  _ │  _ │  _ │ 28 │ 17 │
└────┴────┴────┴────┴────┘
                 ↑
               front

addLast(65): front = 3, size = 3

┌────┬────┬────┬────┬────┐
│ 65 │  _ │  _ │ 28 │ 17 │
└────┴────┴────┴────┴────┘
                 ↑
               front

removeFirst(): front = 4, size = 2

┌────┬────┬────┬────┬────┐
│ 65 │  _ │  _ │  _ │ 17 │
└────┴────┴────┴────┴────┘
                      ↑
                    front

addFirst(31): front = 3, size = 3

┌────┬────┬────┬────┬────┐
│ 65 │  _ │  _ │ 31 │ 17 │
└────┴────┴────┴────┴────┘
                 ↑
               front

addLast(53): front = 3, size = 4

┌────┬────┬────┬────┬────┐
│ 65 │ 53 │  _ │ 31 │ 17 │
└────┴────┴────┴────┴────┘
                 ↑
               front

Solution

addFirst(76): front = 2, size = 5

┌────┬────┬────┬────┬────┐
│ 65 │ 53 │ 76 │ 31 │ 17 │
└────┴────┴────┴────┴────┘
            ↑
          front

The array is now full, so addLast(19) calls grow first. grow copies the items in deque order, 76, 31, 17, 65, 53, into indices 0 to 4 of a new array of capacity 10 and sets front to 0. Then addLast writes 19 at index (0 + 5) % 10, which is 5. After addLast(19), front = 0 and size = 6:

┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ 76 │ 31 │ 17 │ 65 │ 53 │ 19 │  _ │  _ │  _ │  _ │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
   ↑
 front