Let’s cover a basic coding data structure: stacks. Stacks are a basic data structure that are like lists and arrays, but have a last in, first out (LIFO) property when adding and removing elements. Elements in a stack can either be “pushed” onto the stack to be added, or “popped” from the stack to be removed. A classic example is a heavy stack of dishes where plates can only be added and removed from the top.

Stack Big-O Complexity
Time Complexity
Access/Search: O(n) – Linear time. Stacks must be looped/iterated through to locate elements.
Insertion/Deletion: O(1) – Constant time. Elements can be added or removed by pushing onto the stack or popping from the stack.
Space Complexity
All Cases: O(n) – Linear space. Stacks contain a linear amount of data. As the stack increases in size, so does the space used.
Stack Use Cases
- Program Function Calling – Programming interpreters and compilers keep track of function call execution in a stack. If function
a()
calls functionb()
, functiona()
will be pushed onto the stack with functionb()
on top of it. When functionb()
finishes execution to return to functiona()
, it will be popped from the stack. - Undo
(CTRL+Z)
– Undo operations in applications like Microsoft Word use a stack to undo or “pop” the last edit made from the stack.
Stack Python Implementation
The regular Python list data type has pop()
and append()
functions that can make it work as a stack. However, Python lists are dynamic arrays and fully reassign memory locations whenever they grow past their originally assigned size in memory. This can make Python lists very inefficient to use for stacks, so the recommended approach is to use deque
from the Python standard collections
library which resolves this issue.
My full stack Python implementation can be found on myย GitHub. Iโve broken it out into the components of the data structure below.
Stack Definition
We import deque from the collections library and define our stack as a new deque object.
from collections import deque
class Stack:
def __init__(self):
self.container = deque()
Push Function
Within our Stack class we define a push()
function that takes an element to be appended onto the stack.
class Stack:
def push(self,val):
self.container.append(val)
Pop Function
Within our Stack class we define a pop()
function that removes the top element from the stack.
class Stack:
def pop(self):
return self.container.pop()
Peek Function
Within our Stack class we define a peek()
function that returns the top element on the stack.
class Stack:
def peek(self):
return self.container[-1]
Empty Checking Function
Within our Stack class we define a is_empty()
function that checks if the length of the stack is zero and returns a boolean (True/False).
class Stack:
def is_empty(self):
return len(self.container)==0
Size Function
Within our Stack class we define a size()
function that returns the length of the stack.
class Stack:
def size(self):
return len(self.container)
Even More
- Queues are often considered the counterpart to the Stack data structure because they have a first in, first out (FIFO) property instead of stacks’ LIFO property. I will cover the queue data structure in a future post.
- Remember that stacks are often implemented on top of a singly linked list data structure which manages the elements of a stack as nodes in a linked list. Linked lists are useful for stacks because only the end element needs to be accessed for both data structures. Check out my blog post about Linked lists here.
That’s stacks! Be sure to check out all of my posts about coding and other algorithms and data structures.