Stack
A stack is a simple data structure based on the Last In, First Out (LIFO) principle, where only the Top element is accessible.
Think of a stack of plates - you can only add or retrieve from the top.
When we add an item to a stack, we call that operation push. When you take an item off the stack, we call it pop.
A stack S can be implemented easily with a fixed-length array. We can track which element is at the top with S.top. The size of the array is the maximum size of the stack.
Example of array-based stack implementation - From Introduction to Algorithms, Third Edition
If we attempt to add to a stack beyond its max size, Stack Overflow error. If we try to pop from an empty stack, we get the Stack Underflow error.
Programming languages use a stack called a Call Stack to keep track of functions running.
A stack supports the following operations in its typical form:
| Operation | Pseudocode | Description |
|---|---|---|
| push | PUSH(o, s) |
Place o on top of stack. |
| top | TOP(s) |
Show the element at the top of the stack. |
| pop | POP(s) |
Remove and return the element at the top of the stack. |
| isEmpty? | EMPTY(s) |
Return True or False if empty. |
| new empty stack | new STACK s |
Create a new, empty stack. |
Recommended Reading
Introduction to Algorithms, Third Edition
Chapter 10 covers Elementary Data Structures like a Stack or Queue.