FREELessons: 48Length: 7.6 hours

Next lesson playing in 5 seconds

  • Overview
  • Transcript

4.1 Lists, Stacks, and Queues, Oh My!

In this lesson, we will revisit our friend the list and get introduced to some of its close cousins, the stack and queue.

2 lessons, 11:32



2.Python Building Blocks
6 lessons, 1:08:07

Introduction to the Interpreter




Standard Input and Formatting

Building a Tip Calculator

3.Controlling the Flow
7 lessons, 1:20:10

Conditional Statements

Looping With For

The Range Function

Looping With While

Creating Functions: Part 1

Creating Functions: Part 2

Building an Average Calculator

4.Common Data Structures
4 lessons, 46:49

Lists, Stacks, and Queues, Oh My!


Iterating Data Structures

Building a Sentence Analyzer

5.Application Structure
7 lessons, 1:15:12






A Special Calculator: Part 1

A Special Calculator: Part 2

7 lessons, 46:55

What Are Comprehensions?

List Comprehensions

Dictionary Comprehensions





7.File I/O
6 lessons, 48:51

File Basics

Reading Entire Files

Navigating a File

Writing to Files

Reading and Writing to Files

Reading and Writing Complex Objects

5 lessons, 43:48

Introducing the Socket

Getting a Remote IP Address

Handling Socket Errors

Create a Socket Server

Create a Socket Client

9.Connecting to Network Services
3 lessons, 34:27

Getting the Current Time With NTP

Getting Websites With HTTP

Downloading Files With FTP

1 lesson, 02:08


4.1 Lists, Stacks, and Queues, Oh My!

Well congratulations, to this point in the course you have learned quite a bit about Python. And to be completely honest with you, you would really be able to get quite far in learning just what you've learned in the past few sections. And being able to go out and actually write applications, and write reusable code, and use functions and loops and conditional statements. You'd be quite capable of going out and starting to do real work. Now I could definitely stop the course here and let you go do that, but I wouldn't be happy with that. I want to be able to push you a little bit further, and take these new foundational skills in Python that you've learned. And begin to push them a little bit further and start to introduce to you some new constructs, and some new data structures, that you're definitely gonna see out in the world of software development, regardless of the language you're talking about. And we're going to use the list that we talked about back in the section on the building blocks of Python as the basis for the first couple, the first two. And the first one that we're going to talk about is a stack. Now if you have ever done any sort of software development classes, maybe in school, then you've no doubt heard of stacks and queues which basically in the role of Python are more or less just glorified lists. So let's go ahead and see what the basic concept of these are and maybe where some applicable uses are of these things. So the first thing we're gonna start to play around with here is gonna be the concept of a stack. So what I'm going to do is I'm gonna go into my interpretive shell. And now I'm gonna start to introduce to you the concept of a stack. Now the stack, if you visualize it, if you've never thought about it before is this. Let's say you and a number of your friends or family are in the kitchen and you have just finished a meal. Now you all have these plates and dishes at your places. And you're going to start to bring them into the kitchen to wash or put away or clean up or whatever have you. Now typically what's going to happen is you're going to come in line, into the kitchen, and you're gonna start to stack or place these things on top of each other in the kitchen. And then whoever has drawn the short straw if you will, and actually has to do something with these dirty dishes, like wash them, or put them in the dishwasher, or what have you. Is typically going to take the dishes, at least I will, off the top of the stack, process it, do something with it, and then move back to the stack and take the next one off the top. And the whole time that I'm doing this, people are streaming in from the dining room or where have you, and placing things back on the top of the stack. So this concept of entering this stack or this list from the top and then me taking things off or popping them off the top, is this concept known as last in first out, which is exactly the definition of how a stack works. So let's see how we would implement something like that in Python. So we will start by just creating a simple stack, and the stack is really gonna be nothing more than a list. So we'll go ahead and we'll initialize this with a couple values. Let's say 1, 2, and 3. So now if I were to just say, give me stack, as you can see here we have 1, 2, and 3. Now just as I said before, we have individuals coming in from other places, bringing in data, bringing in plates or what have you and adding them onto the stack. Well, if you recall back in a previous lesson, one of the functions that we used quite often was append when it came to stack, and that's how we add things to the quote unquote top of the stack. So as you see here, we'll do stack.append, and let's say we'll go ahead and add 4, and then we'll add 5, and then we'll add 6. So at this point if I were to investigate stack you'll see now I have 1, 2, 3, 4, 5, 6. Now if we were continuing this analogy, if I were in the kitchen and as people started to bring things, or append them, or push them as it's known, onto the stack. I would now start to take things off the top, and that taking off of the top, in terms of a stack, is known as popping off the top of a stack. So the way that I would do that in Python is simply by using the stack.pop function. Now what pop is actually going to do here, is it's going to take off one of the values off the top of the stack, and it's also going to return it. So if you had to visualize that like we were doing before, the concept here is that imagine pop as being a function, something that looks like this. And it's going to do some sort of removal of something off of the stack and then it's ultimately going to return that value. So when we call pop, we're actually going to get a value out of that function. So I could assign this value that's being popped off to a variable. So I could do something like value = stack.pop. And now val is going to equal the next variable or the next value that was popped off the stack, which in this case would probably be 5 and it is. And if I were to take a look at stack at this point, you would now see, 1, 2, 3, 4, because this pop is removing things off the top of the stack. Now you may say to yourself, okay, big deal, where would I ever use something like this? Well, believe it or not, you use something like this on a fairly regular basis. If you have ever used a calculator of any sort of difficulty, it's actually using a stack. And the basic process for doing any sort of basic mathematical equation calculations, is going to use the basic process of a stack where it's going to go through it and inspect each one of the elements that it finds individually. And based on whatever type of value it is, if it's a parentheses, an open parentheses or a closed parentheses, or a plus symbol, or a minus symbol, or digits, or something along those lines. There are certain things that it's going to do to figure out, what are the next steps? Well, if it's a certain symbol that I need to pop or I need to push onto the stack, or I need to do things like that, and that's how basic calculators work. So you can definitely Google around the internet, and you'll find a lot of examples and code snippets of how to do something like that in not only Python, but other languages as well. So, if you ever wanted to play around with this concept of processing the last thing coming in is the first thing coming out, then a stack would definitely be a good choice. Now the second one that I wanted to touch on very briefly here, is this concept of a queue. Now what is a queue? Well I'm sure you're very familiar with what a queue is, maybe you don't speak of it in those terms. Maybe you think of it in a line or as a queue depending on what part of the world you're in. But ultimately the queue is the opposite of a stack in that the first one in is the first one out. So if you're doing basic sequential processing of data, the first piece of data that comes in is the first one processed, and ultimately gone out. So you can think of a call queue, if you were to call the support line of some company or some business, it will typically say that your call will be handled in the order that it is received. And that is a basic concept of a queue. So how can we do that in Python? Well, to be honest with you, you could definitely create a queue on your own, and we may save that for another lesson. But because at this point we don't have all of the necessary skills I feel like that will get us there. So I'm going to give you a little bit of a precursor into an upcoming lesson. Then to show you another skill that we're gonna start to talk about, so I'm actually going to clear this out and I'm gonna start over. So within Python we have this concept of modules, and it's kind of akin to maybe namespacing, if you've ever heard of something like that in other programming languages. But what I'm going to do right now, is I'm going to import a class that's actually going to help us use Python as a queue. So I'm going to import from a particular module, or a namespace if you want to think of it that way, from collections, which is a built in module in Python. And then from collections, I'm going to import a deck or a DQ depending on how you typically say that. I like to call it a deck, but you can call it whatever you would like. So now that I have done that, I now have this concept of a deck and I can do certain operations on it that are very akin to a queue. So what I wanna do is I'm going to create a queue, and I'm gonna set that equal to a new instance of a deck. So think of this deck instance here that I'm creating as a function, that's going to initialize a new instance of my deck class. So then say I put in here a number or basically a list of different pieces of data that I want to process. So let's do something similar to what we did in the previous example. We'll say 1, 2, 3, and 4 is what we're going to start off with. So let's go ahead and hit Enter. Now if I were to investigate queue, you're gonna see here that is providing me back the concept that this is a deck and it contains a list of 1, 2, 3 and 4. Now the process of adding data to this deck is very similar to how it worked for a stack. And for a list, I'm simply going to use the append function here, and I'm going to append to it let's say 5. And then we'll append 6, and then we'll also append 7 just for good measure. Now let's take a look at what queue looks like now. So once again as you can see, now this append is putting things onto the end of the queue here. So where everything is lining up in the order that it is received. So we started with 1, 2, 3, 4, then we added 5, 6, and 7, which wound up adding themselves here on the end. So at this point, how do I get the data out of this queue and be able to process it? Now remember, if we were dealing with a stack in this case, if we were to start popping things off the stack. We would get them off the back end here from the right-hand side, in the order that they were put on. So it'd be 7, 6, 5, 4, 3, 2, 1. But in the world of queues, I want to not just necessarily pop them, I want to popleft, is the operation that we're going to use, is a function that we're going to use that's on this deck class. So if I were to popleft, once again you're going to see here that I get a value returned out of this function. But this time instead of coming off the top, if you want to visualize it that way, or on the end, you're getting it from the beginning. So now I'm processing these in the order in which they were received. And once again I can say val = q.popleft. And I can investigate val, and that's going to be equal to 2, and if I look at queue, once again we have 3, 4, 5, 6, 7. So as you can see now, this is the exact opposite of what we did when we were working with a stack. So there are two very, very common and very powerful data structures that you can definitely use in your process of creating applications to process any sort of data. Or create calculators or create queuing applications to process incoming calls or what have you. So those are two very powerful data structures that you can use to do those types of operations. Now the next lesson, I'm gonna start to talk about one final data structure that just so happens to be one of my favorites and is very near and dear to my heart, the dictionary.

Back to the top