Stack Data Structure
A stack is a data structure that stores items in a last in first out (LIFO) order.
A stack has 2 main functions:
- Push - Add data to the stack
- Pop - Access and remove (or pop) the last inserted item in the stack, also referred to as the top of the stack.
The operation known as peek returns the item at the top of the stack without removing it from the stack.
Stack Big O Overview
Stack Implementation in Python
Under the hood, a stack is represented by a linked list.
The stack's push operation simply adds a node to the end of the linked list.
The stack's pop operation retrieves and removes the tail of the linked list.
Since items can be added and popped from the stack in constant time, Python's dynamic array can be used to represent a stack.
- Push on to the stack takes constant time.
- Similarly, pop from the stack takes constant time.
- Good for use cases such as tracking history, such as browser history or the function call stack itself.
The main con with stack is that it's not useful for iterating through items in the stack. It's better to just use a regular array, or dynamic array.