1
00:00:00,450 --> 00:00:02,580
‫So now we're going to look at cues.

2
00:00:03,030 --> 00:00:11,700
‫And a cue is just like when you stand in line, you can add items to the queue and then you can remove

3
00:00:11,700 --> 00:00:13,230
‫items from the queue.

4
00:00:13,650 --> 00:00:24,930
‫We saw with a stack that a stack is litho last in, first out a queue is FIFO, first in, first out.

5
00:00:25,290 --> 00:00:31,680
‫So with our queue, we're going to write a function that is called in queue which adds items to the

6
00:00:31,680 --> 00:00:32,280
‫queue.

7
00:00:32,550 --> 00:00:39,330
‫And then we'll write another function called DX queue, which removes items from the queue.

8
00:00:39,780 --> 00:00:44,190
‫So just like we did with stacks, we're going to look at two different data structures that we could

9
00:00:44,190 --> 00:00:46,920
‫use for implementing our queue.

10
00:00:46,950 --> 00:00:48,840
‫So we're going to start with a vector.

11
00:00:49,230 --> 00:00:58,290
‫And as we discussed before, on this end of the vector, removing and adding are both O of one.

12
00:00:58,680 --> 00:01:04,620
‫But at this end of the vector, removing and adding are both o of RN.

13
00:01:05,040 --> 00:01:10,200
‫So with the queue we have to add from one end and remove from the other.

14
00:01:10,350 --> 00:01:19,170
‫So if we add from this end and we remove from this end, we have one that is O of N and the other that

15
00:01:19,170 --> 00:01:20,640
‫is of one.

16
00:01:20,970 --> 00:01:27,060
‫And likewise, if we add from this end and remove from this end, it's the same thing.

17
00:01:27,060 --> 00:01:31,410
‫One of them is O of one and the other is O of PN.

18
00:01:31,800 --> 00:01:36,400
‫Now let's compare this to a linked list with the linked list.

19
00:01:36,420 --> 00:01:42,570
‫If you remove from this end, it's O of n, and if you add its o of one and on the other end, removing

20
00:01:42,570 --> 00:01:45,720
‫as o of one and adding an item is o of one.

21
00:01:46,170 --> 00:01:51,240
‫So if you're going to implement a queue with the length list you don't want to remove from this end,

22
00:01:51,630 --> 00:01:58,950
‫what you want to do is in queue from this end and D queue from this end and they're both O of one.

23
00:01:59,250 --> 00:02:05,910
‫And since you can do both of these as of one, a linked list is always going to be more efficient for

24
00:02:05,910 --> 00:02:08,640
‫implementing a queue than a vector.

25
00:02:09,000 --> 00:02:13,110
‫So that is the way we are going to implement our queue.

26
00:02:13,470 --> 00:02:17,640
‫So with a linked list, we had head and tail and a queue.

27
00:02:17,670 --> 00:02:23,820
‫We're going to call these first and last and that is our quick introduction.

28
00:02:24,510 --> 00:02:25,590
‫To accuse.