What Is a Stack?
Have you heard ofstacks 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 adata structure
- How to decide whichimplementation is best for your program
- What extra considerations to make about stacks in athreading or multiprocessing environment
This course is for Pythonistas who are comfortablerunning scripts, know what alist is and how to use it, and are wondering how to implement Python stacks.
00:00Hi, and welcome to this Real Python video course on stacks in Python. In this firstlesson, I’m going to cover what stacks are,why they’re a useful data structure, and how you would actually interact withsome code using a stack. So, what is a stack? And by a stack I meana data structure stack, not simply a stack of objects, thoughthe two have a lot more in common than might be obvious at first glance.
00:26A stack is simply a data structurewhich has a Last-In/First-Out ordering. That is, you put items in and then you getthem out in the exact reverse order that you put them in.
00:37So, as a quick example of why this is a useful thing,imagine that you were implementing something like Microsoft Word and you neededa 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:52And then maybe you want to remove the edit before thatthat 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:06You 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 thathistory in the reverse order that the user visited the pages.
01:21Those are just some examples of how and why you could use a stack.
01:26And what I want to emphasize is that a stack really is functionally just like areal stack. And by a real stack, I meana 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 topso 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:55So let’s take a look and imagine that exact case, that you have someblocksA,B,C, andD and you want to stack them up. And then, of course,at some point you’ll have to unstack them.
02:05And so what normally is the assumption for a data structure stack is that youcan 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:20So, this Last-In/First-Out order is what characterizes a stack as opposed to alist or a queue. Let’s see this in action.
02:29Canonically, adding items to a stack in computer science is referred to aspushing to the stack. You can pushA, thenB, thenC,thenD, and so on.
02:39And then removing items is calledpopping from the stack.So becauseD was on the top, it was the last item that was added—it is the first to be popped. And thenC,B, andA. So, pushing and popping happen inreverse order.
02:53That’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. Inpractice, this might have to be relaxed a little bit.
03:04It’s often useful to look at the top couple of items, or to just look at an itemwithout actually popping it, and so on. But those are more advanced usage.
03:13So, a stack is a list-like data structurewhich has a Last-In/First-Out ordering,so the elements are popped in the reverse order that they’re pushed in.
03:23Let’s take a look at what happens when you want to actually use a stack incode.I’ve defined aSimpleStack class that just has the operations.push() and.pop().
03:37That’s about all you can do with this. And it tells you as wella little bit about what’s happening when you push or pop something.So, I’m just going to push1,2, and3 here.
03:48And 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 youmight expect. Now generally, in any implementation of a stackthere should be an error thrown when you pop from an empty stack.
04:11And in this case, I’m using a list under the hood, so that’swhat’s throwing the actual error,but this will always essentially throw an error because it’s not really clearwhat’s happening when you pop from an empty list.
04:23What 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:31I’ll show you one way to mitigate that.
04:34I’m just going to add the first 10 numbers to the stack here,and you can take a look. Again, the top is9,the last element added. The bottom is0, the first element added.
04:50One way to mitigate this is to just saywhile the stack,so while the stack has elements, then you can pop.And that allows you to…. Oh, and I’m silly.
05:01What I should’ve done was printed each popped element.So let’s just quickly do that again. Let’s print
05:12s.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 elementswhenever you pop it, you won’t run into that error.
05:25So 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.
TheManWhoSoldTheWorld onJune 12, 2020
Great content! but please add subtitles or try to speak a little slow.
kiran onAug. 14, 2020
can you implement other data structures also?
Liam PulsiferRP Team onAug. 14, 2020
@TheManWhoSoldTheWorld thanks for the feedback! We’ve just started adding subtitles to the new courses.
Liam PulsiferRP Team onAug. 14, 2020
@kiran thanks for the question! I’m not quite sure what you mean – would you mind clarifying the question?
kiran onAug. 15, 2020
@Liam Pulsifer Other Data structures also… Like queue, trees, graphs, linked list & it’s types, etc.
Liam PulsiferRP Team onAug. 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 onJune 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 PulsiferRP Team onJune 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.
Course Contents
