The Stack in Python
In this post, we will discuss how to implement the stack, a common data structure, in Python. To build the stack we are going to rely on Python’s built-in list data structure and the collections package.
What is a Stack in Python?
A stack is a data structure that is based on the last-in, first-out principle when adding and removing data. Elements are added on top of the stack and removed from the top of the stack. The process of adding items is referred to as push, whereas the process of removing items is called pop. In Python, a stack is usually implemented using a list or deque from the collections module.
A stack supports the following operations:
- Push: Adds a new element to the top of the stack
- Pop: Removes the item on top from the stack
- Size: Returns the total number of elements from the stack
- Top: Gives you a reference to the element on top of the stack
- Empty: Returns a Boolean to tell you whether the stack contains elements or not
How to Create a Stack in Python?
Python does not offer a native stack implementation. Instead, you can use a list. The Python list has native support for the pop method. Instead of push, you can use append.
To pop elements from a stack, you use the pop method.
stack = [1,2,3] print(stack.pop()) #3 print(stack) #[1, 2]
For adding elements you can use append.
stack = [1,2,3] stack.append(4) print(stack) # [1, 2, 3, 4]
To check the size and whether a stack is empty, you could use Python’s in-built length function.
stack = [1,2,3] print(len(stack)) #3 #empty stack stack = [] print(len(stack) == 0) #True
To retrieve the item on top without popping it off the stack as in the top method, you can use the -1 index.
stack = [1,2,3] print(stack[-1]) #3 print(stack) #[1, 2, 3]
But this approach of using external methods isn’t a very convenient one. Instead, you can implement a wrapper class around the list which implements the stack operations as methods. This allows us to implement the methods that are expected on a stack and name them as we please.
class Stack:
def __init__(self, elements = None):
if(elements == None):
self.elements = list()
elif type(elements) == list:
self.elements = elements
def push(self, item):
self.elements.append(item)
def pop(self):
if(len(self.elements) > 0):
return self.elements.pop()
def getTop(self):
if(len(self.elements) > 0):
return self.elements[-1]
def getSize(self):
return len(self.elements)
def isEmpty(self):
return len(self.elements) == 0
def __str__(self):
return str(self.elements)
In the constructor, we have an if statement to determine whether the caller has passed initial values to the function call. If not, it just creates an empty list. If the caller has passed some initial values, we check whether they have been passed as a list to avoid errors in the future.
The last method tells Python how to print the object as a string. Here we just say that if the caller tries to print the stack object, it should print the current list
#creating an empty stack stack = Stack() print(stack) #creating a stack with initial values stack = Stack([1,2]) print(stack)
Now, you can call the methods directly on your wrapper class. We don’t have to worry about running into an index out of bounds error because the appropriate methods have an internal if statement to check if the stack is empty. If it is and we call pop, it will simply return None.
stack = Stack([]) stack.push(1) print(stack.pop()) # 1 print(stack.pop()) # None
We can also retrieve the size, the item on top; and check whether the stack is empty.
stack = Stack([0,1,2]) print(stack) #[0, 1, 2, 5] stack.push(5) print(stack.getSize()) #4 print(stack.getTop()) #5 print(stack.isEmpty()) #False stack.pop() #5
Note that a list is not the most memory-efficient way to implement a stack because a list makes use of contiguous memory. This means that under the hood Python stores items in the same memory block adjacent to each other until the block is full. Once the block is full, Python starts to fill another block. Storing items across these blocks can take significantly longer. This becomes a problem once the list is sufficiently large. An alternative would be to use deque from the collections module.
Python Stack using Dequeue
Deque may be faster for large lists where you need to retrieve items from the beginning and the end of the queue. The reason behind the speed improvement is that deque is built on a doubly-linked list. Each entry is stored in a separate memory block and contains a reference to the next and the previous entries along with their locations in memory. This way, Python can locate the elements immediately without having to search for them in another block as is the case with the list.
The operations you can perform on the deque are the same as with the list since the interfaces are identical.
from collections import deque #initialize stack stack = deque([1,2,3]) #push items stack.append(4) print(stack) #pop items print(stack.pop())
In addition to being faster for large stacks, the push and pop operations of the deque data structure are thread-safe. This is not true for the list. If you are implementing a stack using a list in a multithreaded program, you are likely to run into race conditions. One thread might manipulate the list. The next thread doesn’t know this and encounters the stack in an unexpected state.
Still, not all methods in the deque class are guaranteed to be atomic (isolated from other operations that are happening at the same time).
Python Stack using LIFO Queue
If you want to be on the safe side thread-wise, your best option is the Last-in First-Out (Lifo) Queue from Python’s Queue module. Again, the interface is similar to that of the list. Instead of append and pop you have to use put and get.
from queue import LifoQueue stack = LifoQueue() stack.put(1) print(stack.get())
So generally, the deque implementation is preferable in production systems if your code is running on one thread, while the LIFO queue is your best bet in multithreaded systems.
About Author
