What Is a Stack?
Have you heard of stacks and wondered what they are? Do you have a general idea but are wondering how to implement a Python stack? You’ve come to the right place!
In this course, you’ll learn:
- How to recognize when a stack is a good choice for a data structure
- How to decide which implementation is best for your program
- What extra considerations to make about stacks in a threading or multiprocessing environment
This course is for Pythonistas who are comfortable running scripts, know what a list is and how to use it, and are wondering how to implement Python stacks.
00:00 Hi, and welcome to this Real Python video course on stacks in Python. In this first lesson, I’m going to cover what stacks are, why they’re a useful data structure, and how you would actually interact with some code using a stack. So, what is a stack? And by a stack I mean a data structure stack, not simply a stack of objects, though the two have a lot more in common than might be obvious at first glance.
00:26 A stack is simply a data structure which has a Last-In/First-Out ordering. That is, you put items in and then you get them out in the exact reverse order that you put them in.
00:37 So, as a quick example of why this is a useful thing, imagine that you were implementing something like Microsoft Word and you needed a Control + Z function. So, when you enter in some text, you want to be able to remove that text quickly by hitting Control + Z.
00:52 And then maybe you want to remove the edit before that that you made, and the edit before that, and so on. You can see how a stack might be useful because the things that you’ve done, you want to undo them in exactly the reverse order that you’ve done them.
01:06 You could also use this to generate website histories, you know, for Google Chrome or Mozilla Firefox or Internet Explorer—any web browser has to have a history function and you need to traverse that history in the reverse order that the user visited the pages.
01:21 Those are just some examples of how and why you could use a stack.
01:26 And what I want to emphasize is that a stack really is functionally just like a real stack. And by a real stack, I mean a stack of papers on a desk or books on a shelf or something like that—or even Jenga blocks! You know, when you put them down and they’re stacked up, the easiest way to get access to them is to remove from the top so you don’t make them topple. Of course, in Jenga you’re trying to remove from other places, so the analogy doesn’t really work perfectly. But luckily, in this case, you’re coding rather than playing Jenga.
01:55 So let’s take a look and imagine that exact case, that you have some blocks A, B, C, and D and you want to stack them up. And then, of course, at some point you’ll have to unstack them.
02:05 And so what normally is the assumption for a data structure stack is that you can only interact with the top block, in this case, which generates what’s called a Last-In/First-Out, or LIFO, ordering, which I mentioned earlier.
02:20 So, this Last-In/First-Out order is what characterizes a stack as opposed to a list or a queue. Let’s see this in action.
02:29 Canonically, adding items to a stack in computer science is referred to as pushing to the stack. You can push A, then B, then C, then D, and so on.
02:39 And then removing items is called popping from the stack. So because D was on the top, it was the last item that was added—it is the first to be popped. And then C, B, and A. So, pushing and popping happen in reverse order.
02:53 That’s the really important thing to note about the behavior of a stack. And canonically, those are really the only two options that are allowed to happen on a stack. In practice, this might have to be relaxed a little bit.
03:04 It’s often useful to look at the top couple of items, or to just look at an item without actually popping it, and so on. But those are more advanced usage.
03:13 So, a stack is a list-like data structure which has a Last-In/First-Out ordering, so the elements are popped in the reverse order that they’re pushed in.
03:23
Let’s take a look at what happens when you want to actually use a stack in code. I’ve defined a SimpleStack class that just has the operations .push() and .pop().
03:37
That’s about all you can do with this. And it tells you as well a little bit about what’s happening when you push or pop something. So, I’m just going to push 1, 2, and 3 here.
03:48 And then you can examine it. The top of the stack is the last item, with this Last-In/First-Out ordering, and then just pop from it. They pop in exactly the reverse order that the elements were added, just as you might expect. Now generally, in any implementation of a stack there should be an error thrown when you pop from an empty stack.
04:11 And in this case, I’m using a list under the hood, so that’s what’s throwing the actual error, but this will always essentially throw an error because it’s not really clear what’s happening when you pop from an empty list.
04:23 What value should be returned? Because there’s nothing in the list to return, so that’s going to throw an error. So that’s something you should be really careful with in your own code.
04:31 I’ll show you one way to mitigate that.
04:34
I’m just going to add the first 10 numbers to the stack here, and you can take a look. Again, the top is 9, the last element added. The bottom is 0, the first element added.
04:50
One way to mitigate this is to just say while the stack, so while the stack has elements, then you can pop. And that allows you to…. Oh, and I’m silly.
05:01 What I should’ve done was printed each popped element. So let’s just quickly do that again. Let’s print
05:12
s.pop(). You can see that they’re popped in the reverse order that they were pushed. And if you make sure to check that the stack has non-zero elements whenever you pop it, you won’t run into that error.
05:25 So that’s how you actually use a stack a little bit in practice, and we’ll talk about how to actually implement this yourself in the next lesson.
kiran on Aug. 14, 2020
can you implement other data structures also?
Liam Pulsifer RP Team on Aug. 14, 2020
@TheManWhoSoldTheWorld thanks for the feedback! We’ve just started adding subtitles to the new courses.
Liam Pulsifer RP Team on Aug. 14, 2020
@kiran thanks for the question! I’m not quite sure what you mean – would you mind clarifying the question?
kiran on Aug. 15, 2020
@Liam Pulsifer Other Data structures also… Like queue, trees, graphs, linked list & it’s types, etc.
Liam Pulsifer RP Team on Aug. 15, 2020
Ahh, gotcha @kiran! We have some video courses in the pipeline that are going to deal with some of those concepts, and we also have some written courses out already. Check out
- realpython.com/linked-lists-python/
- realpython.com/python-thinking-recursively/
- realpython.com/lessons/collectionsdeque/
for some examples, and stay tuned for future courses!
Doug Ouverson on June 24, 2021
Great presentation of stacks Liam!
You used the work “canonically” several times. I wasn’t 100% on the meaning so I did some investigating. After looking up the word, I replayed the video. Still not 100%.
Would you be so kind and elaborate on the use of this word within the context of your presentation.
P.S. Please, please don’t dumb down your language on future presentations; that’s one way I can improve my understanding of the subject matter.
Liam Pulsifer RP Team on June 29, 2021
Thanks for the comment @Doug Ouverson——glad you enjoyed the course! As to the word “canonically,” I generally use it to mean “aligning with the canon of the computer science literature.” So when I say “Canonically, adding items to the stack is referred to as ‘pushing’ to the stack,” I mean that that’s the terminology that’s commonly accepted within the computer science community. It has the connotation as well that it’s more of a convention than anything else. Hope that’s helpful! Feel free to follow up with any other questions.
Become a Member to join the conversation.
TheManWhoSoldTheWorld on June 12, 2020
Great content! but please add subtitles or try to speak a little slow.