The Stack in Python

Sharing is caring

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.

python stack
Pushing and Popping on a Stack

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.

stack in python using deque

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.


Sharing is caring

Leave a Reply

*Your email address will not be published. Required fields are marked

*

https://www.amazon.com/Mathematics-Machine-Learning-Peter-Deisenroth/dp/110845514X?crid=ZZP7728JKVNG&keywords=Mathematics+for+Machine+Learning&qid=1639808509&s=books&sprefix=mathematics+for+machine+learning%2Cstripbooks-intl-ship%2C253&sr=1-1&linkCode=ll1&tag=programmathic-20&linkId=881a3837e71deebac74e3a5568fd8f27&language=en_US&ref_=as_li_ss_tl