Tracing the Two Queues

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

queue.enqueue(17);
queue.enqueue(42);
queue.enqueue(28);
queue.dequeue();
queue.dequeue();
queue.enqueue(65);
queue.enqueue(31);
queue.enqueue(53);

Solution

enqueue(17)

          ┌────┐
head ───▶ │ 17 │ ──▶ null
          └────┘
             ▲
             │
           tail

enqueue(42)

          ┌────┐      ┌────┐
head ───▶ │ 17 │ ──▶  │ 42 │ ──▶ null
          └────┘      └────┘
                         ▲
                         │
                       tail

enqueue(28)

          ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 17 │ ──▶  │ 42 │ ──▶  │ 28 │ ──▶ null
          └────┘      └────┘      └────┘
                                     ▲
                                     │
                                   tail

dequeue()

          ┌────┐      ┌────┐
head ───▶ │ 42 │ ──▶  │ 28 │ ──▶ null
          └────┘      └────┘
                         ▲
                         │
                       tail

dequeue()

          ┌────┐
head ───▶ │ 28 │ ──▶ null
          └────┘
             ▲
             │
           tail

enqueue(65)

          ┌────┐      ┌────┐
head ───▶ │ 28 │ ──▶  │ 65 │ ──▶ null
          └────┘      └────┘
                         ▲
                         │
                       tail

enqueue(31)

          ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 28 │ ──▶  │ 65 │ ──▶  │ 31 │ ──▶ null
          └────┘      └────┘      └────┘
                                     ▲
                                     │
                                   tail

enqueue(53)

          ┌────┐      ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 28 │ ──▶  │ 65 │ ──▶  │ 31 │ ──▶  │ 53 │ ──▶ null
          └────┘      └────┘      └────┘      └────┘
                                                 ▲
                                                 │
                                               tail

Solution

enqueue(17): front = 0, size = 1

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

enqueue(42): front = 0, size = 2

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

enqueue(28): front = 0, size = 3

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

dequeue(): front = 1, size = 2

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

dequeue(): front = 2, size = 1

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

enqueue(65): front = 2, size = 2

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

enqueue(31): front = 2, size = 3

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

enqueue(53): front = 2, size = 4

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

Solution

enqueue(19): front = 2, size = 5

┌────┬────┬────┬────┬────┐
│ 53 │ 19 │ 28 │ 65 │ 31 │
└────┴────┴────┴────┴────┘
             ↑
           front

The array is now full, so enqueue(76) calls grow first. grow copies the items in queue order into indices 0 to 4 of a capacity-10 array and sets front to 0. Then 76 goes to index (0 + 5) % 10, which is 5. After enqueue(76), front = 0 and size = 6:

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