1
00:00:05,540 --> 00:00:07,220
In this video, we'll
learn about the queue.

2
00:00:08,099 --> 00:00:11,590
The queue is a first-in,
first-out data structure.

3
00:00:12,320 --> 00:00:16,790
Like the stack, the queue is an adapter
class because it's implemented in terms

4
00:00:16,790 --> 00:00:19,230
of already existing STL containers.

5
00:00:20,500 --> 00:00:23,810
Since operations on the queue
happen on both ends, the front and

6
00:00:23,810 --> 00:00:27,720
the back, we can easily implement
a queue based on any container

7
00:00:27,869 --> 00:00:29,200
that has a front and the back.

8
00:00:29,580 --> 00:00:31,270
These are the list and the deque.

9
00:00:32,040 --> 00:00:35,499
So, the queue methods use
delegation, and call the methods

10
00:00:35,500 --> 00:00:36,909
of the underlying container.

11
00:00:37,839 --> 00:00:40,960
Like stacks, queues have wide
applications in computer science.

12
00:00:41,210 --> 00:00:44,310
And the STL provides a simple
concise implementation.

13
00:00:45,380 --> 00:00:49,030
You can think of a queue as a
waiting line, elements enter on one

14
00:00:49,030 --> 00:00:50,579
end and are removed from the other.

15
00:00:51,179 --> 00:00:54,119
As with stacks, iterators really
don't make sense with queues

16
00:00:54,119 --> 00:00:55,080
and they're not supported.

17
00:00:55,250 --> 00:00:57,510
So, we can't use the
STL algorithms either.

18
00:01:00,390 --> 00:01:04,199
In order to use the queue containers,
we must include the queue header file.

19
00:01:04,620 --> 00:01:07,560
Like the stack, the queue provides
a handful of methods that have

20
00:01:07,560 --> 00:01:09,100
very well-defined behavior.

21
00:01:09,780 --> 00:01:12,840
The push method inserts an
element at the back of the queue.

22
00:01:13,590 --> 00:01:16,429
The pop method removes an element
from the front of the queue.

23
00:01:17,080 --> 00:01:20,510
The front and back methods access
the front and back elements of the

24
00:01:20,510 --> 00:01:22,420
queue, but does not remove them.

25
00:01:23,179 --> 00:01:25,810
Finally, we have the empty and
size methods that we've seen

26
00:01:25,810 --> 00:01:26,910
with the other containers.

27
00:01:29,379 --> 00:01:32,539
Since the queue is an adapter
class, we can choose what

28
00:01:32,570 --> 00:01:34,240
underlying container will be used.

29
00:01:34,530 --> 00:01:36,010
Same thing we did with the stack.

30
00:01:36,240 --> 00:01:39,040
In the first example, I'm
providing no information about

31
00:01:39,040 --> 00:01:42,940
the underlying container, so the
STL will use a deque by default.

32
00:01:43,789 --> 00:01:46,070
You can see in the next two
examples that I'm explicitly

33
00:01:46,070 --> 00:01:50,020
stating which underlying container
to use as the template parameter.

34
00:01:52,720 --> 00:01:54,850
Now let's see how the
push method works.

35
00:01:55,750 --> 00:01:58,590
Suppose we have a queue of
integers named q and it's empty.

36
00:01:59,460 --> 00:02:03,570
When we push 10 onto the queue, we
add 10 to the back of the queue.

37
00:02:04,059 --> 00:02:05,600
In this case, the queue was empty.

38
00:02:05,840 --> 00:02:08,550
So, 10 is both the back and
the front element in the queue.

39
00:02:09,240 --> 00:02:12,600
Then when we push 20, we push
it at the back of the queue.

40
00:02:12,960 --> 00:02:16,330
So, now 10 is at the front of the queue
and 20 is at the back of the queue.

41
00:02:16,809 --> 00:02:19,810
You can see the front of the queue
is the shaded box in the diagrams.

42
00:02:20,009 --> 00:02:21,579
The back of the queue is the other end.

43
00:02:22,430 --> 00:02:24,350
We then push 30 at
the back of the queue.

44
00:02:26,550 --> 00:02:29,120
Once we have a queue that contains
elements, we can access the

45
00:02:29,120 --> 00:02:32,280
elements at the front and at
the back without removing them

46
00:02:32,429 --> 00:02:34,070
with the front and back methods.

47
00:02:34,750 --> 00:02:39,559
In this example, q.front will display
10, and q.back will display 30.

48
00:02:40,730 --> 00:02:44,010
Now when we pop elements from the
queue, they're removed from the front.

49
00:02:44,200 --> 00:02:48,800
The first q.pop removes the 10 from
the front of the queue, and now 20

50
00:02:48,800 --> 00:02:50,070
becomes the new front of the queue.

51
00:02:51,270 --> 00:02:55,360
The second q.pop removes the 20 from
the front of the queue, and now 30

52
00:02:55,360 --> 00:02:56,720
becomes the new front of the queue.

53
00:02:58,420 --> 00:03:01,530
If we call the size method for the
queue here, we'll display 1 since

54
00:03:01,530 --> 00:03:02,870
there's one element in the queue.

55
00:03:04,000 --> 00:03:06,900
As you can see the queue is really
a very simple data structure

56
00:03:07,230 --> 00:03:10,160
but like the stack, it's used
extensively in computer science

57
00:03:10,360 --> 00:03:12,079
to solve many types of problems.

58
00:03:12,320 --> 00:03:13,469
So, let's head over to the ide.

59
00:03:13,730 --> 00:03:15,060
And we'll see some q examples.

60
00:03:16,209 --> 00:03:17,459
Okay, so I'm back in the ide.

61
00:03:17,680 --> 00:03:20,005
I'm in the section 20 workspace.

62
00:03:20,310 --> 00:03:21,690
And I'm in the queue project.

63
00:03:22,230 --> 00:03:24,790
And just like the stack, the
queue is really, really, simple.

64
00:03:25,110 --> 00:03:26,850
So, let's go over some
of these examples.

65
00:03:27,080 --> 00:03:29,950
First thing you'll see is I've already
got the run over here on the right and

66
00:03:29,950 --> 00:03:31,499
I'll discuss that in just a second.

67
00:03:32,230 --> 00:03:34,790
First thing you'll see is I've
got this template function that

68
00:03:34,799 --> 00:03:38,050
displays the queue very similar
to what we did with the stack.

69
00:03:38,500 --> 00:03:41,190
In this case, I'm passing by
value because I don't want a

70
00:03:41,210 --> 00:03:42,760
reference to the real queue.

71
00:03:42,950 --> 00:03:43,960
And I don't want to destroy it.

72
00:03:43,960 --> 00:03:47,210
So, this is going to make a copy
of the cube that's passed in, and

73
00:03:47,210 --> 00:03:48,609
that's the one I'm going to process.

74
00:03:48,889 --> 00:03:50,179
So, how do I display this?

75
00:03:50,210 --> 00:03:54,760
Well, while the queue is
not empty, I'm going to get

76
00:03:54,770 --> 00:03:55,830
the element from the front.

77
00:03:55,830 --> 00:04:02,459
Remember with the queue, we push on
the back, and we pop from the front.

78
00:04:02,920 --> 00:04:05,920
So, this is first-in, first-out.

79
00:04:06,480 --> 00:04:08,029
Alright, so it's like a waiting line.

80
00:04:08,040 --> 00:04:09,859
Someone gets in at the back
of the line, they come off

81
00:04:09,860 --> 00:04:10,680
in the front of the line.

82
00:04:12,469 --> 00:04:14,119
So, I'm getting the
element from the front.

83
00:04:14,600 --> 00:04:15,970
I'm removing it from the queue.

84
00:04:16,100 --> 00:04:16,909
I'm displaying it.

85
00:04:17,040 --> 00:04:18,409
That's it, really, really, simple.

86
00:04:18,970 --> 00:04:20,829
Okay, so let's talk about main again.

87
00:04:20,829 --> 00:04:22,920
There's only one test
here right in my main.

88
00:04:23,969 --> 00:04:26,880
First thing I'm doing is I'm
creating a queue right here

89
00:04:26,880 --> 00:04:28,389
and it's a queue of integers.

90
00:04:28,539 --> 00:04:32,420
Again this could be just
about any type and I'm pushing

91
00:04:32,520 --> 00:04:34,920
1,2,3,4 and 5 onto the queue.

92
00:04:35,120 --> 00:04:38,920
Now remember I'm pushing at
the back, so when I push 1.

93
00:04:38,920 --> 00:04:40,220
I'm pushing it at the back.

94
00:04:40,220 --> 00:04:42,220
Then 2, then 3, then 4, then 5.

95
00:04:43,700 --> 00:04:46,900
I display the queue. And this is
what I'm getting right here.

96
00:04:47,520 --> 00:04:48,869
Now what's the front, what's the back?

97
00:04:48,890 --> 00:04:50,950
Let's be sure that we
understand what's going on here.

98
00:04:51,210 --> 00:04:54,119
We can say q.front, q.back,
and you can see that the front

99
00:04:54,120 --> 00:04:55,570
here is the one, makes sense.

100
00:04:55,640 --> 00:04:57,450
It's the first one that I pushed on.

101
00:04:57,990 --> 00:05:00,500
First customer in line is the
first customer out of the line.

102
00:05:00,670 --> 00:05:03,890
So, that's the front,
the back is the 5.

103
00:05:05,930 --> 00:05:09,000
Now I want to push a 100
onto the back of the queue,

104
00:05:09,360 --> 00:05:10,539
and display the queue again.

105
00:05:10,980 --> 00:05:13,830
And you can see the output right
here, you can see the 100 here

106
00:05:13,830 --> 00:05:14,930
is at the back of the queue.

107
00:05:16,139 --> 00:05:20,350
I want to pop two elements
from the front of the queue.

108
00:05:21,150 --> 00:05:24,209
So, what happens is the 1
and the 2 get removed from

109
00:05:24,209 --> 00:05:25,310
the front, and they're gone.

110
00:05:25,830 --> 00:05:28,169
So, now what's left
is 3,4, 5, and a 100.

111
00:05:28,170 --> 00:05:30,560
Three is at the front,
100 is at the back.

112
00:05:31,800 --> 00:05:34,540
If I want to remove everything
from the queue, I need to use

113
00:05:34,550 --> 00:05:35,780
some sort of loop like this.

114
00:05:35,780 --> 00:05:37,659
We can't use iterators with the queues.

115
00:05:37,929 --> 00:05:41,890
So, while the queue is not empty,
pop the front element out of there.

116
00:05:42,510 --> 00:05:44,610
And when I'm done, it'll be
empty, and I display the queue.

117
00:05:44,740 --> 00:05:47,469
And I will get an empty queue
just like you see right there.

118
00:05:48,430 --> 00:05:50,810
When I display the size of
that queue, I'm right here.

119
00:05:50,810 --> 00:05:54,510
It's down line 42, I will get a
zero because it's empty right now.

120
00:05:55,480 --> 00:05:57,599
And let me just clear
this and I'll scroll up.

121
00:05:59,910 --> 00:06:01,630
And there's a few more
lines, not too many.

122
00:06:01,860 --> 00:06:03,760
So, we're right here, we're on line 44.

123
00:06:06,760 --> 00:06:10,190
I've got an empty queue at this point,
I just printed out the size right here.

124
00:06:10,670 --> 00:06:13,630
So, I'm going to push 10,
100 and then a 1000 onto the

125
00:06:13,630 --> 00:06:14,739
queue, and display the queue.

126
00:06:15,190 --> 00:06:18,359
There you go. You can see 10 is at the
front, 1000 is at the back.

127
00:06:18,359 --> 00:06:20,810
And you can see that that
being displayed right here.

128
00:06:21,710 --> 00:06:23,719
10 is at the front,
1000 is at the back.

129
00:06:25,280 --> 00:06:27,599
Now I have access to
the front and the back.

130
00:06:27,740 --> 00:06:30,590
The front method and the back
method return references.

131
00:06:30,849 --> 00:06:33,960
So, if I wanted to change the
front or change the back, I can.

132
00:06:34,219 --> 00:06:37,100
So, in this case, I'm setting
whatever element it is at the

133
00:06:37,100 --> 00:06:40,020
front to 5 and at the back to 5000.

134
00:06:40,450 --> 00:06:42,390
You can see them change right there.

135
00:06:43,550 --> 00:06:47,330
Right, they were 10, now it's
5 was the 1000, now it's 5000.

136
00:06:47,780 --> 00:06:50,649
And you can see again that the
front of the queue is the 5 and

137
00:06:50,649 --> 00:06:52,119
the back of the queue is the 5000.

138
00:06:53,090 --> 00:06:55,010
So, that's it in a
nutshell, that's the queue.

139
00:06:55,490 --> 00:07:00,850
So, remember this is first-in,
first-out as opposed to the stack

140
00:07:00,870 --> 00:07:03,169
which was the last-in, first-out.

141
00:07:03,710 --> 00:07:07,529
And there's uses for all of
these first-in, first-out

142
00:07:07,530 --> 00:07:11,289
queues are used all the time for
scheduling, job scheduling, task

143
00:07:11,289 --> 00:07:12,810
scheduling, and operating systems.

144
00:07:13,500 --> 00:07:15,909
Stacks are used a lot in compiling.

145
00:07:16,300 --> 00:07:19,290
They're used a lot to solve
problems where you have to calculate

146
00:07:19,290 --> 00:07:23,180
expressions, and you have to figure
out how many parentheses are there?

147
00:07:23,200 --> 00:07:24,729
Do they balance and things like that?

148
00:07:25,210 --> 00:07:26,099
Okay, so, that's it.

149
00:07:27,429 --> 00:07:30,570
In the next video, what we'll do
is we'll do a challenge that's

150
00:07:30,570 --> 00:07:32,100
going to use stacks and queues.

151
00:07:32,100 --> 00:07:35,230
And remember that palindrome example,
we did a while back with the deque.

152
00:07:35,520 --> 00:07:37,289
We're going to do the same thing
except we're going to use a

153
00:07:37,290 --> 00:07:38,539
stack and a queue to solve it.