Python Stack Data Structure

Python Stack Data Structure

A stack holds a collection of items in the order in which they were added. You can only add items to and remove items from the top of a stack. If you think of a stack as a stack of pancakes, you can only add to the top of the pancake stack and remove it from the top of the pancake stack. This is a last-in-first-out system because the most recent item you add is the one that’s going to get removed next. This is also referred to as LIFO.


Python List As Stack

In order to implement a Stack, we need a mutable data type that holds an ordered collection of items. It turns out that a Python list data type fits this requirement perfectly. What we are going to do now in this Python Stack Data Structure tutorial is to implement a class in Python that leverages a list as the datastore for our stack. When we code our stack class, we’re going to use the right side of a list to represent the top of a stack. You can also think about this location as the end of the list.

python list as stack

Basic Stack Operations

  • Add to the stack.
  • Remove from the stack.
  • Is the stack empty?
  • How many items are in the stack?
  • What is the next item to be removed?

Stack Data Considerations

  • Any data type that can be stored in a list can be stored in a stack
  • Limited access because we can only access the data from one place

Create A Stack Class

Now that we’ve covered the stack abstract data type, we know what we want the stack to do, and we can start to stub out a stack class and its methods. First, we need to define the class itself. So let’s call it Stack. We can also create an init method that uses a list to hold the items in the stack. Lastly, we’ll create a variable called self.items, and initialize that to our empty list.

class Stack:
    def __init__(self):
        self.items = []

push()

The first thing that we want to be able to do is add an item to the stack. The word we use for that is push. We’ll also need to pass into push the item that we want to add to the stack. The push() method accepts an item as a parameter, appends it to the end of our list, and returns nothing. The code for this is highlighted below.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

Let’s check to see if this code works. We can test this out in the terminal by running the Python file interactively. This code is in a file named stacks.py. So to run this code we can use python -i stacks.py. Once we are in the terminal we can create a new instance of a stack with the stack = Stack() code. Then we test the push() method by running stack.push(‘Orange’). Finally, we simply call stack.items and we can see that ‘Orange’ is now in the stack.

stack interactive python shell

Let’s try to use push() a couple of more times to make sure it is working great. We’ll add two new items and then inspect the items to confirm that we now have three items in the stack.

python stack push method

Notice that ‘Yogurt’ appears to the right of ‘Orange’, and ‘Ham’ appears to the right of ‘Yogurt’. This is correct and the reason this is the case is because we always consider the right side of the list to be the top of the stack and we can only add to and remove from the top so every time we add something else it’s always going to show up on the rightmost side of that list.

pop()

Just like we added, we also need to be able to remove an item from the stack and we use the word pop for that. Now, because the list’s built-in pop method always returns the last item of the list anyway, we don’t need to specify an index or an item that we want to remove. That will take care of that automatically for us. This method returns the last item. We should say, it removes and returns the last item from the list, which is also the top item of the stack. Now you’ll notice that we have a small if condition inside of the pop() method. This is needed so that we can check if the stack has items in it before trying to pop one off and return it. If the stack has items, then the topmost item is removed and returned, otherwise, the method returns a None value.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.items:
            return self.items.pop()
        else:
            return None

We can again test this out in the interactive python shell. Recall we have three items in the stack. When we call the pop() method, the topmost or last in the list item is removed and returned.

python stack pop method

Now we can check the items in the stack, and we see that there are now only two items. If we run the pop() method again, we get the topmost or last item in the stack back which is now ‘Yogurt’.

how to pop python stack

Finally, we run the pop() method one more time and we can see that the stack is now empty.

python empty stack

size()

Building on top of these two basic things, we may want to know how many items are in the stack, and the word we use for that is size. We can find the size by simply returning the length of items like the code displays.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.items:
            return self.items.pop()
        else:
            return None

    def size(self):
        return len(self.items)

Once again we can test this out in the terminal. We know from our last example that the stack is currently empty. So when we call the size() method we should get 0 back, and that is what happens.

stack in python size

Let’s test out the size() method just a bit more. We can use the push() method to add ‘Python’, ‘Django’, and ‘Htmx’ to the stack. Now when we call the size() method we get the correct value of 3. Great! It seems that our stack and size() method are working correctly.

stack size python

is_empty()

Another functionality that we would like of our stack class is the ability to check if the stack is empty or not. The way to check this is to see if items is equal to an empty list. When that expression is evaluated it will be either True or False, and that gets returned via the return keyword. This code here does just that for us.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.items:
            return self.items.pop()
        else:
            return None

    def size(self):
        return len(self.items)

    def is_empty(self):
        return self.items == []

Now we can test out the is_empty() method of our stack class. We’ll start a new interactive python session with the stacks.py file. Then we initialize a new stack. At this point, the stack should be empty. When we then run the is_empty() method, we see a return value of True. This is good and seems correct. Next, we push a new item onto the stack and then run the is_empty() method one more time. This time the is_empty() method returns False. This is also good and means that the is_empty() method is correctly determining if the stack is empty or not.

python stack is empty method

peek()

We now have the basic functionality for our stack class because we have coded the push(), pop(), size(), and is_empty() methods. Another method that you might find in a stack implementation is the peek() method. What the peek() method is going to do is show us what the next value is that’s ready to be popped. In other words, this should show us the item that’s on the top of the stack. We want to return that item as well. To provide this functionality we need to return whatever value or whatever item is in the last index of the list. The powerful indexing syntax in Python makes it easy to accomplish this by indexing into the negative first position. The seek() method makes use of an if statement just like the is_empty() method does. We first need to check if the items variable has any items. If it does, we return the topmost item in the stack. If there are no items, we simply return None. That new method is highlighted here.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.items:
            return self.items.pop()
        else:
            return None

    def size(self):
        return len(self.items)

    def is_empty(self):
        return self.items == []

    def peek(self):
        if self.items:
            return self.items[-1]
        else:
            return None

Let’s test out the peek() method in the interactive terminal now. Once again we initialize a stack and then push a few items onto the stack. First, we push ‘Canada’, and then we push ‘United States’. That means ‘United States’ is on the top of the stack. So when we run the peek() method that is the item that should be returned, and it is. The peek() method is working correctly. It may seem that peek() and pop() do the same thing, and they kind of do except for one key difference. Both methods return the topmost item in the stack, but the peek() method does not remove the topmost item in the stack whereas the pop() method does. We can see that is the case by looking at the items variable after running peek() when it returned ‘United States’. That item is still on the stack.

python stack peek method

Learn More About Stacks In Python

Python Stack Data Structure Summary

A stack is a linear data structure that stores items in a Last-In and First-Out (LIFO) manner. as we saw in this stack tutorial implemented in Python, a new element is added at one end and an element is removed from that end only. The stack implementation typically has the following methods to make the stack work.

  • is_empty() – Returns whether the stack is empty
  • size() – Returns the size of the stack
  • peek() – Returns a reference to the topmost element of the stack
  • push(item) – Inserts the element ‘item’ at the top of the stack
  • pop() – Deletes the topmost element of the stack