Tracing the ArrayStack

With all four operations in place, let’s trace a sequence of them and see how the backing array and size change. Throughout the trace, remember that size always points at the next free slot, so the top of the stack is at size - 1.

We start with new ArrayStack<>(): the backing array has ten empty slots, and size is 0.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  ↑
size

push(4) places 4 in slot 0, the slot size was pointing at, then increments size to 1.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
      ↑
    size

push(9) does the same with slot 1. The top is now 9.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ 9 │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
          ↑
        size

push(6) fills slot 2, and size becomes 3.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ 9 │ 6 │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
              ↑
            size

Now top() returns 6. It does not change the array or size.

Next, pop(): size drops to 2, and slot 2 is cleared.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ 9 │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
          ↑
        size

A second pop() does the same: size drops to 1, and slot 1 is cleared. The top is 4 again, just as it was after the first push.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
      ↑
    size

Then push(2) writes into slot 1, the same slot the second pop just cleared. This is why pop does not have to clear the slot. A new push will overwrite it anyway.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ 2 │ _ │ _ │ _ │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
          ↑
        size

A final top() returns 2.

The array’s capacity stayed at ten throughout the trace since grow never ran.