Join us and get access to thousands of tutorials and a community of expert Pythonistas.

This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.

Unlock This Lesson

Which Implementation Should You Use?

Implementing a Stack in Python Liam Pulsifer 05:05

In this lesson, you’ll cover which implementation you should use for a Python stack in various contexts. You’ll also follow a run-through in the terminal to get a practical idea of what to consider if you want to use these implementations in your code.

Download

Sample Code (.py)

1.7 KB

Download

Course Slides (.pdf)

302.5 KB

Congratulations, you made it to the end of the course! Make it stick: Mentor AI will check what you’ve got down, help you build something with it, and find your #1 takeaway to share in the discussion.

Or go straight to the discussion section and share your #1 takeaway and how you’ll put your new skills to use.

00:00 In this last lesson, I’m going to answer the question of which implementation you should use for a Python stack in various contexts. I’m also going to give you a quick run through in the terminal of the various syntaxes and things you might want to consider when you’re actually using these implementations in code.

00:19 The question of which implementation you should use in any context is really a pretty simple one. If you need airtight thread safety, use queue.LifoQueue, because this is the only class that is standardly available in the Python world which allows you to implement a stack completely thread-safely, with all of its operations guaranteed to be thread-safe. In other cases, you should use deque, because deque is faster than both LifoQueue and list, and it still gives you some thread-safe considerations. But in general, it’s just really fast and still really simple to use.

00:55 There are a couple of cases where you might want to use a list: If you need the indexing capability if you’re implementing a kind of a hybrid stack where you sometimes might need to look at items other than the top of the stack. Or if you have a really, really limited Python environment, like perhaps on a machine which is very strapped for memory, you might want to use list because it’s part of the core Python language features and you might not want to use the collections module.

01:19 But that’s a very rare case, so really it boils down to thread safety, use queue.LifoQueue, and in other cases use deque. Let’s take a look in the terminal and see how these all work.

01:32 So, stack equals just a list stack. You can say for i in range(10):, and this is going to be my go-to example. I’m sorry it’s a little boring, but it’s very simple to see what it looks like, so. So, there’s the stack.

01:49 And as you know, the LIFO Last-In/First-Out ordering guarantees that 9 will be the first thing to be popped and so on. And one way to just iterate through the stack is you can say while the stack, so while stack has a length of more than 0, I’m just going to print(stack.pop()).

02:08 So as you can see, it pops in the reverse order that they came in, as you might expect. So then you can also say from collections import deque,

02:18 and you can say stack = deque(). And with this, you can do almost exactly the same stuff. It has exactly the same syntax as a list, and it has a little bit faster performance, but it doesn’t give you the indexing capability of a list.

02:33 So if you need to access items other than just the top of the stack or at the beginning of the stack, because a deque is a doubly-linked list under the hood, then a list might be a better choice.

02:43 But you can still examine the stack very easily with a deque by just putting it into your Python REPL or printing it or whatever. It shows you exactly what’s in it. So now, I have the last implementation, which is from queue import LifoQueue, and you can do the same thing, except this time it’ll be stack.put(i) because that’s the slightly different…. Oh, I’m sorry. As you can see, I forgot to actually make the stack equal to the LifoQueue. Silly me.

03:22 But we can do the same thing with .put(). And if you need to examine it, you use the .queue object of the LifoQueue class, and you can examine it.

03:33 And then—this is another slight difference here. If you want to just pop all of the things in the stack, you can say stack.get(), which will get you the last item and so on. stack.get(), and you can see that the .queue has changed a little bit.

03:48 But if you want to just iterate through, you have to do something a little bit different. You have to say while not stack.empty():

03:57 stack.get(). We’ll just use stack.get().

04:04 So as you can see, now that stack.queue has nothing in it because they’ve all been gotten. And you have to remember, of course, that if you call stack.get() on an empty LifoQueue, it will just wait infinitely.

04:19 So, be careful with that. Instead, you have to use .get_nowait(),

04:23 which will raise the familiar exception if the queue is empty. And remember that list.pop() will give you pop from empty list, which is an IndexError. And deque.pop() will give you the same thing.

04:38 So remember to always check for that. With a deque and a list, you can just say while the list or the deque has elements. With a LifoQueue, you’ll have to use the .empty() method because it does not implement the same Boolean checking that deque and list do.

04:54 So, there are your three implementations and the various things you have to think about when using them. I hope you found this lesson and this series informative.

05:02 Thanks.

Max on March 4, 2020

Nicely done, to the point, no overhead. Just perfect to start off my working day :)

rolandgarceau on March 4, 2020

Can you give examples for the last few seconds of the video when you mentioned we need to add in checks?

Liam Pulsifer RP Team on March 4, 2020

@rolandgarceau sure, happy to! I’m guessing you mean when I say you should implement checks to avoid errors caused by popping from an empty stack? If not, feel free to drop another comment and clarify what you’re looking for, but here goes:

while my_list: # Assuming a list-based stack implementation called "my_list"
    my_list.pop()

while my_deque: # Deque version
    my_deque.pop()

while not my_stack.empty(): # with LifoQueue 
    my_stack.get()

DanielHao5 on March 7, 2020

Good Intro to the stack. It would be great to elaborate more on the Use Cases for different scenarios, eg. is_valid_brackets(), type of questions.

Thanks. Daniel

Lee Crampton on March 8, 2020

Nice and concise. Thanks.

patientwriter on April 5, 2020

If you are not interested in a stack, is LifoQueue() still the way to go for thread safety?

Liam Pulsifer RP Team on April 5, 2020

@patientwriter the queue module is definitely still the right place to go if you need thread safety as well as some sort of queue-like behavior because all of the functions and objects in that module are written with thread safety in mind, but of course you might not always need the LIFO behavior that queue.LifoQueue gives you, so it’s worth reading through the documentation to see what (if anything) in that module fits your needs.

Soumya Ranjan Sahu on June 7, 2020

Thanks Liam! It was a very informative session.

TheManWhoSoldTheWorld on June 12, 2020

I really like to learn about LifoQueue(). Thanks Liam, nice videos.

Ghani on Oct. 26, 2020

Very informative course; thanks!

Become a Member to join the conversation.