Stack Operations

Many beginners picture a collection of items as something you can reach into at any position. A stack does not work that way. It is built around one rule: at any moment, only one item is directly available, and that is the item on top. A stack is a sequence of items piled one on top of the other, and only the top item is accessible at any time. Once you accept that single rule, most of the behavior of a stack follows from it.

The restriction to the top item creates a fixed ordering rule for removal. An item lower in the pile cannot be taken out until every item stacked above it has first been removed. A helpful picture is a one-way doorway: whatever entered most recently is the first thing that can leave. This is why a stack suits any task where the most recent piece of work must be handled before older pieces.

The rule is about position, not about content. The source notes that a stack can hold items of any type; its example uses int values. Whether the items are numbers, names, or other objects, the pile-like behavior is identical, because what matters is where each item sits, not what it contains.

A stack is used through a small set of operations. Each one has a specific job.

The source describes push and pop as operations that can be implemented as instance methods when the stored items are int values. Notice that pop does two things at once: it changes the stack by removing the top item, and it hands that item back. isEmpty does not change the stack at all; it only answers a question about it.

The best way to internalize the stack rule is to trace it. Follow a short sequence and, after each operation, write down the full contents of the stack and identify the item on top. Here the stack is written from bottom to top. Start with an empty stack and apply these operations in order: push 4, push 7, push 2, pop, pop.

The source is clear that popping from an empty stack is an error. There is no top item to remove and return, so a program that calls pop without checking has a bug. The purpose of isEmpty is to let code find out, before popping, whether there is anything to remove. Checking isEmpty before calling pop is the safe pattern.

To 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. Keeping this measure in mind lets us compare the two ways a stack can be built.

Before choosing an implementation, 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? The answer differs between a linked list and an array, and the difference is more subtle than simply fast versus slow.

For a linked list implementation, the worst-case run time of both push and pop is Theta(1). In plain terms, the run time is bounded by some fixed constant that does not depend on how many items the stack holds. 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.

An array has a fixed amount of storage. Most pushes simply place a new item into the next free slot, and for these the run time 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. Copying takes time in proportion to the number of items already on the stack. Because the copying loop touches each of the n items, a push that triggers it has a worst-case run time of Theta(n).

In the diagram, the push that finds no free slot is the only one that triggers the copy. Every ordinary push onto an array with room left writes into the next free slot and does not copy anything. That single costly push is the source of the Theta(n) worst case.

The worst case tells us how bad one operation can be. The average case tells us what to expect over a sequence of operations. For the array implementation these two measures give different pictures. 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, the average run time of push on an array remains Theta(1).

This is why worst-case and average-case claims should always be stated separately. Saying that array push is Theta(1) is true on average, but saying it is Theta(1) in the worst case would be false, because a single full-array push costs Theta(n).

Placing the two implementations side by side makes the contrast clear. 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. Neither implementation is better in every respect; each trades one kind of predictability for another.