Implementing a Stack
Explore how to implement stack data structures in C# using two common approaches: arrays and linked lists. Learn the concepts of fixed-size versus dynamic sizing, how to manage the top element, and trade-offs between performance and memory efficiency. Understand push and pop operations and practical implementations for beginner programmers.
We'll cover the following...
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 to store stack elements, with all elements stored in a contiguous block of memory. If we want a dynamic array in C#, we would typically use List<T>, but here we will use a fixed-size array to make the structure clear. Since 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 value 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 such as List<T> is used, the capacity can grow when needed, 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, making the implementation straightforward and efficient.