A stack is a data structure that behaves like a black box in which all insertions/retrievals/deletions are performed on TAIL. This kind of access is called Last-In-First-Out (LIFO) and structurally makes stack a natural Container implementation. C++ class prototype using Dynamic Array:
template<typename T>
class Stack {
...
private:
T* contents;
std::size_t capacity;
std::size_t size;
};
How values are added/deleted to/from stack using Dynamic Array:
For a complete implementation example, check Stack class documentation or its GitHub code.
All stacks use a List implementation as storage, which can be:
Conclusion: since none of Dynamic Array disadvantages occur when growing/contracting on TAIL and latter is by far the fastest and most memory efficient solution at disposal, it must be solution of choice!
Let us take its Container implementation as Dynamic Array to better understand how it works:
| Operation | Description |
| clear | Frees memory block from RAM, reallocates it for same CAPACITY, resets SIZE to zero. |
| size | Gets SIZE value |
| isEmpty | Checks if SIZE equals zero |
| push | Adds entry at SIZE position then increments SIZE If CAPACITY is reached, memory block grows by doubling its size. |
| peek | Gets value at SIZE-1 position (TAIL). |
| pop | Gets value at SIZE-1 position (TAIL) then removes it from stack. |