This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.
Stacks and Queues
Loading...
来自 Rice University 的课程
Principles of Computing (Part 2)
251 个评分
从本节课中
Searching and Data Structures
This week, we will explain the importance of searching. We will also explore various data structures and learn about inheritance.
与讲师见面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[MUSIC]
In this video we're going to talk about two
relatively simple but important data structures in Computer Science.
Stacks and Queues.
Both of these data structures are used to hold information in between computations.
They do so in such a way that restricts
how you can add and remove elements from them.
Okay, this allows you to provide a
simplified interface that makes it very clear how
you intend to pass data from one position in the program to another, all right?
With that, let's take a look at how they work.
All right, let's first talk about Stacks.
All right?0 And to explain Stacks, I'm going to talk about Building blocks.
So, here's my floor and I have some blocks.
I'm going to stack them up.
All right?
So, first I put a block on the floor, that's my first block.
Then, I stack another block on top of it, that's my second block.
Then, I stack another block here and finally I stack a block right there.
So now I have my stack of four blocks, all right?
And the question is what order do I put them in?
Well obviously you put the one in the bottom first and then you build up okay?
Now what stack, what order do you take these blocks away?
Well [LAUGH] if you're my son, you pull
out this block here in the bottom all right?
But [LAUGH] more you know, people that are not trying to knock the stack
of blocks over, right, this would be the first one you would take off.
And then you would take this one off, then you would take
this one, and so on, and then this block would be the fourth.
Okay.
So blocks, you stack them in a certain
order, and you unstack them in the opposite order.
Okay?
So a stack is what's called a LIFO structure.
Okay?
Last in, first-out.
Okay?
The last block I stacked up, is the first block I take off.
And, as computer scientists, we usually draw it like this.
And we say, "Okay I put things in the top, I take things out from the top".
So this is a push operation, this is a pop operation okay,
and pop only, always gets the most recent element that was pushed.
So when you push it goes down to the bottom
so I put something down on the bottom then you
push again it goes here and you push again and
then when you pop you take this last item out.
Okay?
So, Stacks are this last-in, first-out kind
of structure, kind of like building blocks.
Okay.
So, let's talk about Queues now.
So, what is a Queue?
Well, let's think about, I go to some sort of store.
Here's the checkout counter, here's my little cash register.
Okay, all right.
So I show up in line, I am the first person to show up in line is here.
Okay, this person is first.
Okay, then another person shows up in line.
This person is second and then another person shows
up in line, this person is third, all right?
What order do they leave the line?
Well this person gets to go first, check out
first, then this person, so we got one, two, three.
Okay?
So, in contrast to a stack, a queue is actually a FIFO structure,
okay, first in, first out.
Okay.
And we usually draw this a queue as this, where we go in here and out here.
Okay, and just for you know, similarity I'm going to call this push and this pop.
Okay, now when I stick something into the queue, right?
The first thing I stick in, then I stick something else.
then I stick something else.
When I pop, I get this first and then I get this and then I get this.
Okay?
So a Stack, the last thing you put in is the first thing you get out.
In a Queue, the first thing you put in is the first thing you get out.
Okay lets take a look at stacks and queues in action.
I have a very simple program here that basically pushes a couple elements on.
Pops one, pushes another and then pops three off.
Okay, so I'm going to start by making my container via queue.
Okay.
And my queue implements the push method and the pop method.
Okay, so I'm going to push three things here.
Push the elements one, two three.
Okay, and then I'm going to pop one element, I'm going to
push four, and I'm going to do three pops, all right?
Now I want you to think about what going to happen here, hall right?
What order are things going to print in, right?
Remember, a queue is a FIFO structure, or first in, first out, okay?
So, let's see if it works the way you think it does.
Okay, it prints 1, 2, 3, 4.
Why?
Because I put 1 in first, then 2, then 3, then 4, and these
pops occur in this order, so it gets it back 1, 2, 3, 4.
All right?
Okay, now, let's replace the queue with a stack.
Right?
Now I'm going to behave differently.
Right?
I'm going to push one, two, three.
Then I'm going to pop.
Then I'm going to push four.
Then I'm going to pop, pop, pop.
I want you to think for a second, about what you think's going to happen here.
Remember that a stack, is a LIFO structure, or last-in, first-out.
So let's see what happens.
Three, four, two, one.
Okay.
Well, I pushed one, two, three.
Then I did a pop.
That pop, gets the most recent element: the three.
So it prints three.
Then I push four.
The next pop, gets the most recent element: which is four.
Okay, and then pop, pop.
Which gets the elements before that, which are left: two and one, in that order.
Okay?
So you can see that by using a Stack
versus a Queue, I dramatically change the behavior, all right?
The question is, do I want the thing that I most recently pushed, or do
I want things to come back out in the order that I put them in?
So, here is the simple Queue class that we're going to use in this course.
Okay, and you can see I've defined it as q
with a capital Q, obviously, and we have an init
method that just initializes the Q, and you can see,
internally I'm going to represent the queue as a phyton list.
All right?
Now we've got some methods that you might not have seen before,
lets talk about this first one here, underbar underbar len underbar underbar.
Well, this allows me to get the length of the queue, all right?
And when you actually called len in python, that's the method
that it calls, so lets initialize a queue here, All right?
And I should be able to now print the length of the queue.
And I would expect that to be zero since I haven't put anything into the queue.
Okay, and it is zero, all right.
Now that we're talking about this, you can see that
I have an enqueue and a dequeue method, all right.
These two methods are the workhorse methods here that
allow me to actually implement the behavior of a queue.
So I should be able to add some things.
Let's enqueue [SOUND] number 37 and let's
equeue [SOUND] number 14 [SOUND] all right?
And let's print the length again.
[SOUND] Okay, now the length is two because I've added two things, all right?
So when I call len in Python, what it's actually doing is it's taking
the object and calling its under bar, under bar len under bar, under bar method.
And another method you might not have seen
before: under bar itter under bar under bar.
And the idea here is to allow us to iterate over this queue.
And if you look at the implementation, it's actually a generator.
All right.
But let's actually use it.
Okay.
How do I iterate?
Well raise the four loop.
So I say four item in queue.
Print, item.
All right.
And that's actually going to use that, itter method, to get an iterator.
And since we built a generator, it'll allow us to go
across, the, the queue and I get 37, and then 14.
All right, I get em back in the order that they
were put in, and that makes sense for a queue, okay.
And I have an underbar, underbar stir, underbar underbar method.
Okay that's just going to return a string representation, and
I'm choosing to just use the Python list representation, there.
So, if I do print queue, it'll call that stir
method and print it out like it was a list.
Okay.
I can end queue and dequeue things, and then, I can also clear things, okay?
So, this is my queue abstraction.
Now, if you look at the implementation of
these methods, I'm really just using list methods.
And, they're all very simple methods, right.
All of them are basically one line, except for the itterator.
And so the question you might have is why not just a Python list?
Well, it's actually very useful important to use a queue class, okay?
I'm creating an abstraction here and I'm saying this is a queue,
and I'm restricting the ways in which you can access that queue.
I'm saying if you want to add something to the queue, you can't just insert
it in the middle of the list, you can't you know put it anywhere you want.
You have to call end queue.
Which we'll put it at the end of the list.
And then when I want an item back, I
can't just look anywhere I want inside the queue.
I can't take the last thing off.
I can only call dequeue, which will take the thing at
the beginning of the list and give it back to you.
So it, it enforces this first in and first out behavior.
And this is critically important.
All right, so that's how Stacks and Queues work.
All you really need to remember here: stacking
blocks and standing in line at the store.
All right?
Those are really the models here.
I have a Stack, all right, where the last thing I put in is the first thing I take
out, and I have a Queue where the first thing
I put in is the first thing I take out.
And both of these are extremely valuable data structures
that occur again and again and again in computer science.
All right and by restricting the ways in which you can access these
things, it helps you to make better and more reliable programs, all right?
