1
00:00:00,980 --> 00:00:01,550
OK.

2
00:00:01,730 --> 00:00:05,870
So this lecture is going to be pretty short.

3
00:00:06,800 --> 00:00:14,060
I just need to introduce a couple of data structures for the next section, and that is going to be

4
00:00:14,060 --> 00:00:23,770
stacks and Qs, and we are just going to be using the standard template library and versions of these.

5
00:00:23,780 --> 00:00:28,730
So we will just be including those libraries for stacks and queue.

6
00:00:29,150 --> 00:00:34,100
We're not going to create our own data structures, kind of how we did with link lists and things like

7
00:00:34,100 --> 00:00:34,400
that.

8
00:00:35,940 --> 00:00:37,620
But I just want to introduce them.

9
00:00:38,160 --> 00:00:40,980
I'm going to do this theoretical video, which would be really short.

10
00:00:41,490 --> 00:00:47,970
And then I'll do a quick little implementation and it'll be one file, you know, and something really

11
00:00:47,970 --> 00:00:52,110
basic just to show how they work and how the functions work with them.

12
00:00:53,280 --> 00:00:56,400
So, yeah, let's go ahead and get started.

13
00:00:58,020 --> 00:01:00,420
So first off, we're going to talk about a stack.

14
00:01:01,260 --> 00:01:08,640
A stack is what you consider a last in, first out or abbreviated like this LIFO data structure.

15
00:01:10,670 --> 00:01:18,710
So basically, the last thing that was added is going to be the first one that we have access to to

16
00:01:18,710 --> 00:01:19,220
take out.

17
00:01:20,460 --> 00:01:23,070
That's kind of like the order in which things happen.

18
00:01:23,490 --> 00:01:31,170
So we've talked about stacks a little bit when we are talking about recursion, that stack we were talking

19
00:01:31,170 --> 00:01:34,200
about was actually a stack in memory.

20
00:01:34,500 --> 00:01:38,730
So we have the, you know, the call stack in memory.

21
00:01:38,730 --> 00:01:46,230
When we had recursive calls which were like stack frames, the function, the function calls or stack

22
00:01:46,230 --> 00:01:48,270
frames in memory that we're kind of stacking up.

23
00:01:49,560 --> 00:01:55,320
It's pretty much the same thing that we're talking about now, but you can just imagine it like a standard

24
00:01:55,320 --> 00:02:00,480
data structure similar to like a vector when you push back to a vector.

25
00:02:01,140 --> 00:02:07,950
We also have a stack that we're just going to use, like an STL stack data structure, and you have

26
00:02:07,950 --> 00:02:10,490
these three operations down here.

27
00:02:10,500 --> 00:02:13,320
So you see this include stack right here.

28
00:02:14,400 --> 00:02:23,250
That's something we'll have to do to use that steel container and then pushing into the stack is basically

29
00:02:23,250 --> 00:02:25,290
adding something on top.

30
00:02:26,070 --> 00:02:32,850
So like this, we push something and you can imagine this kind of like a stack of plates.

31
00:02:32,850 --> 00:02:37,230
I think I use that analogy before, like pancakes or something like that.

32
00:02:38,430 --> 00:02:43,740
We basically start at the bottom and we just stack things on top of each other, hence the name stack.

33
00:02:44,820 --> 00:02:51,750
And then when you take something off this, you know, out of these three of the most basic operations,

34
00:02:51,880 --> 00:02:57,000
most fundamental operations that we're using on this pop is where you will take something off the top.

35
00:02:57,000 --> 00:03:04,620
So you can imagine that you only have access to the top of this data structure and given time, and

36
00:03:04,620 --> 00:03:08,100
you can either push something or pop something off.

37
00:03:09,760 --> 00:03:16,870
So we have the push and then we have the pop, which we take that top element off of the stack, and

38
00:03:16,870 --> 00:03:22,870
then we also have this third thing that just lets us refer to and grab like the top element.

39
00:03:23,680 --> 00:03:32,050
So top let us refer to the top element and be able to see what the thing is at the top of the stack.

40
00:03:33,670 --> 00:03:35,680
So that is how Stack works.

41
00:03:35,710 --> 00:03:43,120
Very simple, you know, things just stack on top of each other and you basically have access to the

42
00:03:43,570 --> 00:03:44,380
top element here.

43
00:03:44,380 --> 00:03:49,420
So if you wanted to take everything out, you'd have to start with that pop and pop from the top back

44
00:03:49,420 --> 00:03:50,080
to the bottom.

45
00:03:53,090 --> 00:03:55,640
OK, so with that, let's look at the queue.

46
00:03:55,760 --> 00:04:00,950
The queue is the obvious, first in, first out data structure.

47
00:04:02,550 --> 00:04:08,940
So very similar to like I mean, you can basically implement this with a vector as well, so very similar

48
00:04:08,940 --> 00:04:12,000
to the vector, you know how you push back to a vector.

49
00:04:13,500 --> 00:04:21,300
And then you might like loop through it going from the first to the last or something like that, you

50
00:04:21,300 --> 00:04:27,510
might like reference to the first item and then loop through till the end of the vector until you get

51
00:04:27,510 --> 00:04:28,050
to the end.

52
00:04:29,150 --> 00:04:32,570
That would be kind of like the same ideas as a cue.

53
00:04:33,260 --> 00:04:39,470
But there actually is a cutaneous structure that would be including and it is like a cue in real life.

54
00:04:39,470 --> 00:04:46,730
If you think of like a cue as in people waiting for, you know, a teller at a bank or something like

55
00:04:46,730 --> 00:04:47,090
that.

56
00:04:48,690 --> 00:04:50,580
You know, people are waiting in line.

57
00:04:50,790 --> 00:04:53,910
And it's kind of like a first come, first serve.

58
00:04:54,240 --> 00:05:02,990
So the first thing to arrive is like the first thing to, you know, go out, so get served and and

59
00:05:03,000 --> 00:05:03,330
leave.

60
00:05:04,050 --> 00:05:09,510
So that would be, you know, like the last the.

61
00:05:11,770 --> 00:05:15,880
The oldest thing is the first out.

62
00:05:16,300 --> 00:05:19,270
Basically, you know, the person that's been there the longest.

63
00:05:20,530 --> 00:05:22,210
And so we have, you know, a similar thing.

64
00:05:22,210 --> 00:05:27,220
We're going to include Q and it's already in the structure, which is nice.

65
00:05:27,640 --> 00:05:29,860
A lot of the things that we've been doing so far.

66
00:05:30,580 --> 00:05:36,310
There's like, you know, a list data structure that's included in the standard template library, I

67
00:05:36,310 --> 00:05:39,670
believe, but we've been kind of making our own things.

68
00:05:40,400 --> 00:05:46,000
You know, just like the stack, we're going to actually use something that's already been implemented.

69
00:05:48,320 --> 00:05:51,440
And so we have these three big operations here as well.

70
00:05:53,690 --> 00:05:58,070
You know, there I think there's other functions that you can use from the queue, but these are the

71
00:05:58,070 --> 00:06:06,170
three main ones I'm going over, so we have a push which push us to the back pop, which pops the front

72
00:06:06,950 --> 00:06:08,420
and we have a get front.

73
00:06:10,000 --> 00:06:16,150
So kind of similar to the to the stack, except we're building it out the opposite direction.

74
00:06:16,150 --> 00:06:21,820
So if you imagine the stack kind of turned sideways, like flopped on its side.

75
00:06:26,540 --> 00:06:32,780
Like, I'm going back here, so if you took like this whole thing and rotated it, so these bars were

76
00:06:32,780 --> 00:06:39,950
pointing up, then we would kind of be building from right to left like stacking stuff out this way.

77
00:06:41,020 --> 00:06:45,880
But the Q is the opposite, it's going to build out from left to right.

78
00:06:46,090 --> 00:06:49,900
If we're thinking of those being on the same, like playing there.

79
00:06:52,150 --> 00:06:58,930
OK, so I'm just using like faces for people, if you're imagining those people waiting in line at like

80
00:06:59,290 --> 00:07:00,670
a bank or something like that.

81
00:07:00,910 --> 00:07:04,780
So this would be us pushing something to the queue.

82
00:07:05,870 --> 00:07:10,010
And then we push something else, and I have a Green Line, you know, just referring to the front.

83
00:07:11,090 --> 00:07:15,470
And so we push again, we push again, we push again.

84
00:07:16,920 --> 00:07:26,020
And push again, so it builds out from left to right there, and the front is the thing that can potentially

85
00:07:26,020 --> 00:07:29,220
be the first out, that is the Green Line.

86
00:07:29,230 --> 00:07:32,620
So we're referring to the person that's been there the longest over here.

87
00:07:35,000 --> 00:07:38,930
So now if we do pop in, we're referring to that first person.

88
00:07:39,660 --> 00:07:45,940
It'll pop different, so we pop that person at the next one and the next one, the next one.

89
00:07:45,980 --> 00:07:47,870
And now we're just on our last person.

90
00:07:49,510 --> 00:07:52,450
So hopefully that explains it pretty simple data structures here.

91
00:07:52,990 --> 00:07:59,590
I'm just giving this brief explanation of them so we can use them in the next section, which is going

92
00:07:59,590 --> 00:08:03,440
to be about graph algorithms.

93
00:08:03,820 --> 00:08:10,270
So well, we're going to need to use Qs and Stack, so I want to make sure that they're understood before

94
00:08:10,270 --> 00:08:12,280
we get into those algorithms.

95
00:08:13,060 --> 00:08:13,440
All right.

96
00:08:13,450 --> 00:08:19,960
So with that, I'll see you in the next video to this be a quick implementation of these nine implementation,

97
00:08:19,960 --> 00:08:24,220
but just using them in a small see purpose program.