A stack is a last in first out (LIFO) data structure that closely resembles a stack of plates.
Implementation
A stack can be implemented with just a singly linked list with a pointer to the head of the list.
Essential operations for a stack data structure are:
- Push
- Pop
Push adds an element to the top of the stack, pop will depending on the implementation either return the element and remove it or just remove it.
Uses
Stacks are useful by themselves, but are also elements of other more complex ADTs. For example, they are used in the DFS algorithm. The stack ADT also resembles the stack concept for memory management.
Cstd
In the C standard library for C++, the following exist:
- Top (peek at top element)
- Push (insert)
- Pop (remove top element)
- Size
- Swap