So, inserting the first N items would take time proportional,
if the stack's of size N-1, it's going to take time N, N-2, time N-1.
So first N items would take the sum of the first N integers,
which we know is about N squared over 2.
Quadratic time to insert N items into a stack,
that kind of performance is unacceptable for
large problems, as we've seen, as we will see many times.
So the challenge is to do the resizing, but
somehow ensure that it happens infrequently.
So the well-known technique for doing that,
called repeated doubling, is to, when the array fills up,
create a new array of twice the size and copy all the items over.
Then we don't create new arrays all that often.
So here's an implementation of that.
We start with an array of size 1.
If we have a full stack, which we know by testing N,
which is the number of items in the stack versus the array length, then
we just resize the array into one of twice the length before inserting the item.
And how do we resize to a new capacity?
We create a new array of that capacity and just go ahead and copy our
current stack into the first half of that and then return it.