Join Barron Stone for an in-depth discussion in this video Stacks, part of Programming Foundations: Real-World Examples.
- While I was outside I grabbed the mail, and unfortunately, it looks like today is nothing but bills and junk mail. As I sorted through my mail, when I come across a bill, I'll put it on a stack to be processed. And, as for the junk mail, I'll just toss that. So this first item is a bill, I'll place it on my stack. The next item is also a bill, so I'll place it into the stack on top of that first one. Junk mail, junk mail. Another bill, that goes on the stack. Junk mail, and a bill.
Now, the bills on my stack are ordered from top to bottom with the most recent bill I put onto the stack at the top, and the oldest bill at the bottom. When I'm ready to begin paying these bills, I'll grab the last envelope that I put onto the stack, which is at the top, and I'll start working my way down the stack paying my bills in the opposite order that I put them onto the stack. - Hey, it looks like you dropped a bill on the way in. - Whoops! Well, I'll just put that here on top of the stack. Since that bill Olivia found is the newest item on the stack, it'll get processed next after I finish with this one.
Of all the different concepts and data structures in Computer Science, I think stacks are one of the most sensibly named because they work like a stack of things in real life. Python does not have a built-in data type or module called "stack". Instead, I can use the list data structure to accomplish the same thing as a stack. So, for this example, I'm going to create a new list object named "stack", which I'll be able to add and remove objects from in a "last in, first out" manner. When I use a list to implement a stack, think of the front of that list, or index 0, as being the bottom of the stack, and the back of the list, or the highest index, as the top of that stack.
I have access to all of the standard list methods. So, I can add an object to the stack by using the append method, which attaches an object to the back of the list. I'll add two bills to this stack by calling stack.append "bill1", and stack.append "bill2". Now, if I want to get the bill from the top of the stack to process it, I can use the pop method, which removes and returns the last item in the list, which is equivalent to the top of our stack. I got back "bill2" because that was the last bill I added to the stack.
If I add two more bills to the stack, we'll call these "bills3 and 4", and to call pop again, I'll get "bill4" because that was the most recent object placed on the stack. And if I continue to call the pop method, I'll get back "bill3", and then "bill1", which makes sense, because "bill1" was the first bill I put into the stack so it should be the last one out. LIFO. So, now the stack is empty because we've paid all the bills. If I tried calling pop again, it'll return an error letting me know that the stack is empty.
You might be wondering why we can use a list to implement a stack, but to create a queue in the previous video, we used the special queue module. Couldn't we just use a list to implement a queue as well, by appending items to the back of the list and then retrieving them from the front? Technically, yes. But there's a reason to use the special queue module to create queues, and that's efficiency. Under the hood, the queue module is built in a way that allows for items at the front of the queue to be removed easily. Lists, on the other hand, are structured in a way that makes it super easy to add and remove items from the back of the list, but removing items from the front of the list is inefficient.
Therefore, a list is a great way to implement a stack by appending and popping objects from the back of the lists since it's last in, first out. But with a queue, it's better to use the special queue module which has been optimized to efficiently handle the first in, first out transactions.
- Reusing functions
- Local vs. global variables
- Creating and naming custom objects
- Class inheritance
- Modules and packages
- Multidimensional lists and tuples
- Queues and stacks
- Creating and combining sets
- Storing data in dictionaries
- If/else and switch statements
- For vs. while loops
- Error handling
- Polling and event-driven programming