Stack data storage order

Question

When talking about a stack in either computing or "real" life we usually assume a "first on, last off" type of functionality.

Because the idea of a stack is based around something in the physical world, does it matter how the data in the stack is stored?

I notice in a lot of examples that the storage of the stack data is quite often done using an array and the newest item added to the stack is placed at the bottom of the array. (like adding a new plate to an existing stack of plates except putting it underneath the other plates rather than on top).

As a paradigm, does it matter in what order the data is stored within the stack as long as the operation of the stack acts as expected?

Answer 1

Not really. However, since there's no computational advantage (generally) to move pushed items to any other position, a linear structure (that can provide fast access to the current "top" of the stack) works as well as anything. An array meets the needs of a stack structure in terms of performance and compactness so it is usually the best/obvious choice.

Answer 2

It doesn't matter how your store your data in memory as long as the functionality and performance are as expected.

Often stacks are implemented as an array with a size and capacity where the size is the number of elements currently in the stack and the capacity is the maximum number that can be stored without requiring a relatively expensive memory reallocation.

The capacity typically doubles when required to give amortized O(1) performance for insertion. It is generally easier to implement the stack with the empty space at the high index end of the array, so this is what is typically done.

To give a specific example, the current top of the stack can be stored as the index into the array of the top element. If the items were added to the highest index of the array downwards then when the array is increased to make room for more elements the index of the top of the array would also change. When filling from the bottom the index of the top element does not change when the array needs to be resized.

If you wanted to implement your stack differently, you could do that, just make sure that the functionality and performance of your implementation are documented.

Answer 3

As a paradigm, no, not really. As a low-level implementation detail, a stack which grows downwards has the slight advantage that the items already on the stack can be addressed from the current stack pointer using a positive offset (e.g. this may be useful for some CPU architectures).