Implementing a Stack

With the concept of a stack established, the next step is to examine its implementation. A stack is an abstract data type. It defines a set of operations but does not specify how data is stored or managed in memory. A stack can be implemented using different underlying structures, such as an array or a linked list.

Using an array

In an array-based stack implementation, we use an array (or a dynamic array) to store stack elements, with all elements stored in a contiguous block of memory. As a stack only ever adds and removes elements from the top, we can simply treat one end of the array as the top. The first element added sits at index 0, and each new element is placed at the next available position. The most recently added element always sits at the last index.

Think of it like a stack of plates, with the tray as a row of numbered slots. The first plate goes into slot 0, the second into slot 1, and so on. The top plate is always the one in the last occupied slot.

In an array, an index called the top is used to track the position of the most recently added element. The size tells us how many elements are currently in the stack. Additionally, a capacity element defines the maximum number of elements the stack can hold; this is the total size of the underlying array.

If the array has a fixed size, then the stack has a maximum capacity that cannot be exceeded without resizing. If a dynamic array is used, the capacity can grow when needed (typically doubling when full), although the top position is still managed explicitly to maintain LIFO order.

Here's how an array-based stack works:

As elements are pushed onto the stack, the top index increments. When elements are popped, the top index decrements. The stack only grows and shrinks from one end, ...