Implementing a Stack with an Array

Suppose you are told that a stack supports push and pop, and that you may build it in two different ways. One way uses a linked list. The other uses an array. Before you choose, it helps to ask a practical question: when a single stack operation runs, how much work could it end up doing, and does that amount of work depend on how full the stack already is?

This article answers that question for both implementations. The answer is not the same for each, and the difference is more subtle than a simple fast-versus-slow comparison. One implementation keeps every push and pop equally cheap no matter what. The other is cheap almost all of the time but has one situation where a single push must do a great deal of work.

When we analyze how long a stack operation takes, we need a way to measure the size of the problem. For stacks the natural choice is the number of items currently on the stack. Call that number n. The question then becomes how the running time of push or pop grows as n grows.

Run time is described by how it grows with n. Theta(1) means the run time is bounded by some fixed constant that does not depend on n. Theta(n) means the work grows in proportion to the number of items. Keeping n in view is what lets us compare the two implementations fairly, because both are judged by the same measure.

For a linked list implementation, the worst-case run time of both push and pop is Theta(1). Whether the stack has three items or three million, a single push or pop finishes within the same fixed amount of work.

The reason is visible in the structure of the operations. Each one is carried out by a handful of simple assignments that update the links at the top of the stack. Nothing in those steps requires visiting the other items. The total number of items on the stack never enters the calculation, so it cannot make the operation slower. A push links a new node to the front, and a pop unlinks the front node. In both cases the rest of the stack stays exactly where it was.

An array has a fixed amount of storage, and the implementation must keep track of where the top of the stack currently sits. Consider an array with four slots, numbered 0 through 3. Pushing A, B, and C fills slots 0, 1, and 2 in order, and the top is now at slot 2, the most recently written item. Slot 3 is still free.

A pop reverses the movement. Removing C reads slot 2 and moves the top back to slot 1, which now holds B. Each operation touches only the slot at the top. A push writes into the next free slot, and a pop reads the item at the top. Neither needs to move the other items, which is why an ordinary push on an array is Theta(1).

The trouble comes when the array is full and there is no free slot left. At that moment the implementation cannot simply write one more item, so it must make room in a different way. The method is to create a new, larger array and copy every existing stack item into it, after which the new item can be placed.

The worst case of a single push is Theta(n), but the source notes that this worst case occurs only rarely. Because of that rarity, there is a natural sense in which the average run time of push on an array remains Theta(1). It is important not to read this as saying the expensive copy never happens. It does happen. The point is that it happens infrequently enough that, when its cost is spread across the many cheap pushes around it, the average cost per push stays bounded by a constant.

In this run, the expensive push is one event among several cheap ones. The cost of the copy is shared across the pushes that surround it, so the average cost per push stays constant. The source presents this as a natural sense of average behavior rather than a formal calculation, so the same level of detail applies here.

Neither implementation is simply better in every respect. The linked list keeps every push and pop at a fixed cost regardless of stack size. The array keeps ordinary pushes cheap but accepts one expensive case, the push that finds the array full. Each trades a different kind of predictability for the other.