Data Structures: Stacks

What is a stack?

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.

How can a stack be implemented?

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!

How does it work?

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.

Share