Which python data type class is the most suitable for implementing stacks

Constructing and using a Stack Data Structure in Python

A Stack is an Abstract Data Type that stores the order in which items were added to the structure but only allows additions and deletions to the top of the Stack. This follows a Last-In-First-Out (LIFO) principle which does as it says in the name. You can imagine this as the way in which you would eat a Stack of Pancakes (unless you like to eat parts of all the Stack at Once) or the way in which you would use Plates after you washed them after dinner and then were going to reuse them (unless for some reason you wanted to risk breaking them all!). Take for example the Stack of Pancakes that Jimmy Fallon is throwing out in the Gif below.

These can be used when we want to store outputs in a structure that retains their order but we only want the user to be able to access the last thing they added to that structure. Common examples of this include the back button in your browser which goes to the last item added into the stack or the undo button on your word processor to undo the last addition you made.

This of course is an Abstraction, focusing on what we want the Data Structure to contain and how we want to interact with it. We can then begin to think of how to implement this in an actual Data Structure in Python.

When thinking about this we need to be able to define the key methods associated with this data structure. Common operations can include:

• push(item): Push an item to the top of the stack
• pop(): Remove the top item of the stack and return it
• peek(): Return the top item of the stack without removing it
• is_empty(): Return True if the Stack is empty
• size(): Return how many items are in the Stack

What this means is that we need to build this using a Python Data Type that is mutable and can be used to store an ordered collection of items. The first thing we can ask ourselves is whether there is a Data Type already implemented in Python that can do this for us?

A list! We can use a List!

We know that a list is mutable, it can be changed, and we can easily and simply add and remove items from the beginning and end using the already inbuilt functionality of the list to implement a Stack.

In using a list we have to define a class that uses this but only has specific functionality that allows the user to interact with it in the way that we want. For this, we can use Python’s class structure to be able to define the information that the data structure will contain and also the methods that we want to use.

The first thing to do then is to name the class as Stack and create the constructor for this new class. For this, what we want is once a new instance of the object is created is to create an empty list that could be accessed using the .items attribute. We can instantiate the class as follows:

This means that when an instance of the Stack class is created then the item attribute will represent an empty list.

We can then start to add the main functionality to our Stack class. The first thing we want to be able to do is to add an item to the end of our stack. The good thing about lists is that there is an inbuilt method for this in the .append() method. The benefit of this is that it has a constant time complexity O(1) meaning that the time it takes to run will not change with the number of items already in the list because it only adds the item to the end. We can thus take advantage of this to push an item to the end of our Stack as follows:

Nice and simple right! In this instance we don’t care about what exactly we are adding to the end of the stack, just that we can add it. You can add more functionality to this but for now this is fine.

What about removing items from the Stack? For this, we first of all need to check that the Stack isn’t empty as you can’t remove items from an empty Stack right? If the stack is empty then we can simply return none so that we do actually return something, but if it is not empty then we can remove the final item and return it. Since we are using Python’s inbuilt list class, we can use the .pop() method which in Python 3.6+ removes the last item from a list and returns it. This also runs in constant time O(1) because we are only removing the last item and not affecting any other index. We can implement this as:

The benefit of checking whether a list exists first before popping ensures that an error isn’t thrown which could otherwise stop your code from running if it is not handled. Putting this in the actual implementation of the Data Structure just ensures that if you didn’t think of it when running the code using this Data Structure then the code keeps running to some degree.

We now have our main methods associated with a stack but we can also add some additional functionality just to make it more useful for our end-user.

The first thing we can add is a method to peek at the final value in a stack, allowing the user to look at the value before we decide to remove it or not. This can follow a similar implementation tothe pop() method but instead of using .pop()we access the item with the last index in the list. Again, this is has a time complexity of O(1) as we are accessing an item from a list using an index making this nice and simple.

We can also provide a method of checking whether the Stack is empty or not. This would simply return a boolean value of True if the stack is empty and False if it is not empty. This also runs in constant time as it is simply checking whether the list within the stack exists or not.

Finally, we can create a method that returns the size of the stack. This tells us the length of the stack, just like it would for a list, and allows the user to see how many items have been added.

We now have the main functionality of our Stack class and most of the additional functionality as well. This just makes it easier and simpler for our end user to interact with this Data structure in the final interface that we created.

The only issue is, if we try to print an instance of the class we get the ugly output of

<__main__.Stack object at 0x0000027F2C960FD0>

which doesn't look good and also doesn’t tell us much about the actual instance of the class. What can do then is to use the special __str__ dunder method of the class to tell the interpreter how we want to print out an instance of the class. In this case we simply want to return the entire list contained within the stack which can be implemented as:

The final thing to do then is to put all of this together so that we can create instances of this Stack class in our code. The final product then looks like:

At this point you must be thinking why would I need to know this? Well, common applications of this in programming can include:

• Evaluating mathematical expressions
• Parsing syntax of a programming language
• Storing parameters and local variables
• undo and redo operations in word processors
• Backtracking in a website

Which is all well and good when you are building these programs to know that this Data Structure can give you the functionality to be able to deal with these challenges.

On the other hand, A stack can also be used in a common interview question involving how to reverse a string. While you can simply do this using a list, if they ask you to create a Data Structure and reverse a given string a Stack is a good example.

For this we can simply add all the characters to an empty Stack, unpack all these characters in reverse order, join them together and then print out the result. An example of this can be seen below:

So there you go, you now know how to implement a Stack in Python and how to reverse a string using this Data Structure! Congrats!

This is the fifth article in a series exploring Data Structures and their use and implementation in Python. If you missed the previous three on Dictionaries, Tuples and Sets in Python you can find them at the following links:

Future articles in the series will cover Linked Lists, Queues and Graphs. To make sure you don’t miss any then sign up to receive email notifications when they are published:

And if you liked what you read but are not year a Medium member, then consider supporting both myself and other amazing authors on this platform by signing up using my referral code below:

Thank you for reading!

What Python data type is used for stack?

Which data type is used to represent stack?

What Python data type is best suited for implementing a queue?

How do you implement a stack using class in Python?