WEBVTT 00:00.180 --> 00:04.590 Hello again! In this video, we are going to look at the queue class in the C++ library. 00:05.430 --> 00:07.860 We probably know about queues in the real world. 00:08.280 --> 00:09.870 So here is a queue of people. 00:10.200 --> 00:15.840 The person at the front is the first person to arrive and the person at the back is the latest person 00:15.840 --> 00:16.560 to arrive. 00:17.650 --> 00:23.770 Presumably, they are all waiting to be processed in some way: to be allowed into the venue, or to buy 00:23.770 --> 00:25.810 their ticket, or to collect something. 00:27.040 --> 00:29.140 So these are going to be processed, one person at a time. 00:29.530 --> 00:35.470 The first person will leave the queue, and then the person behind them will then become the first person, 00:35.710 --> 00:36.610 at the front of the queue. 00:37.270 --> 00:40.030 And if any more people arrive, there will be at the back of the queue. 00:42.520 --> 00:48.040 In computer science, there is a data structure called a queue, which is based on similar principles. 00:48.430 --> 00:54.310 The elements in a queue are stored in the order in which they were inserted into the queue, with the first 00:54.310 --> 00:57.100 element at the front, and the most recent element at the back. 00:58.120 --> 01:04.240 As the program processes the queue, the element at the front is removed, and then the element which was 01:04.240 --> 01:06.040 behind it now becomes the front element. 01:06.610 --> 01:10.060 Then that one is processed and removed, and the next one becomes the front, and so on. 01:11.650 --> 01:16.150 Elements can only be removed from the front of the queue. And they can only be removed in the same 01:16.150 --> 01:17.500 order in which they were added. 01:21.100 --> 01:25.630 So a queue data structure looks a bit like this. So we have some elements here. 01:26.020 --> 01:31.270 The one at the front of the queue is the first one which was inserted and the one at the back is the 01:31.660 --> 01:32.560 latest arrival. 01:34.360 --> 01:37.420 If we add another element, then that goes on the back of the queue. 01:38.640 --> 01:43.440 And if we remove an element, that comes off the front of the queue, and then this now becomes the front. 01:45.730 --> 01:49.330 C++ has an implementation of the queue in the library. 01:50.140 --> 01:54.610 The first element which is added to the queue is always the first element to be removed. 01:54.970 --> 02:02.620 So this is an example of a FIFO structure, standing for "First In, First Out". (Not to be confused with FIFA, 02:02.620 --> 02:04.810 which is the International Football Association!) 02:06.280 --> 02:10.750 A queue is usually implemented as a deque, and you might want to think about why that is. 02:11.380 --> 02:17.110 Although it can be implemented as a vector or a list. And the reason for using a queue is that there 02:17.170 --> 02:21.760 are a lot of operations at the front of the container, and that is something that deques are good at. 02:24.310 --> 02:26.530 The interface for a queue is rather limited. 02:27.070 --> 02:32.890 We can use push() or pop(), to add or remove elements. When we use push(), the element goes on the back of 02:32.890 --> 02:36.700 the queue. When we use pop(), the element comes off the front of the queue. 02:37.570 --> 02:40.480 We can also access the front and back elements. 02:41.200 --> 02:44.860 We can find out if the queue is empty, or how many elements there are. 02:46.800 --> 02:50.160 And many of the typical container operations are not supported. 02:50.490 --> 02:52.530 For example, there are no iterators for queues. 02:55.560 --> 02:58.430 So let's look at how to use a queue structure. 02:58.890 --> 03:05.970 We include the queue header. We create a queue object, and then we call push() to insert some elements into 03:05.970 --> 03:06.420 the queue. 03:06.900 --> 03:08.220 So 4 is the first. 03:08.340 --> 03:09.410 So that is going to be the front. 03:10.140 --> 03:11.910 Then 3, 5, and 1 is the last. 03:12.210 --> 03:13.860 So 1 will be the back of the queue. 03:15.170 --> 03:17.660 We have this function for printing out some information. 03:17.990 --> 03:21.950 We cannot print out all the elements, because queues do not support iterators. 03:22.610 --> 03:28.400 But we can print out the front and back elements and also some information about the number of elements 03:28.400 --> 03:28.910 in the queue. 03:30.930 --> 03:33.000 Then we call push() to add another element. 03:33.030 --> 03:38.130 So this will go to the back of the queue. And then we call pop() to remove an element. 03:38.400 --> 03:41.400 So this will remove the element which was at the front of the queue. 03:43.820 --> 03:48.830 So there we are. We have a queue of four elements, with 4 at the front and 1 at the back. 03:49.580 --> 03:53.210 Then when we add the element, the queue now has five elements. 03:53.600 --> 03:55.940 And this new element is the one at the back. 03:56.600 --> 04:01.190 And after removing the front element, the new front element is 3. 04:01.880 --> 04:08.660 And then when we remove the front element, we remove this element 4, and 3 now becomes the front 04:08.660 --> 04:09.170 of the queue. 04:12.320 --> 04:15.140 So what sort of application would use a queue? 04:15.610 --> 04:20.990 Queues are mainly useful if you want somewhere where you can keep data temporarily, and keep that data 04:21.200 --> 04:22.580 in the order in which it arrived. 04:23.240 --> 04:28.460 So, for example, in networking programs, you can have some packets which arrive. For a lot of 04:28.460 --> 04:29.000 protocols, 04:29.000 --> 04:31.580 these assume that the packets are going to be processed in sequence. 04:31.880 --> 04:33.740 So you need to keep these packets in order. 04:34.250 --> 04:36.260 But it may be that the processor is not ready. 04:36.260 --> 04:43.610 Or perhaps it is more efficient to process a lot of elements in bulk, rather than as they come in. Or if you are writing 04:43.610 --> 04:45.770 an inventory system for perishable goods. 04:45.770 --> 04:51.260 So if you have a warehouse which is storing fish, or orange juice, or something which has a fairly short 04:51.260 --> 04:55.370 life, you do not want stock hanging around for longer than necessary. 04:55.790 --> 05:00.500 So you try to make sure that the oldest goods get shipped first, while they are still saleable. 05:03.010 --> 05:07.840 So queues are useful for processing events in the order in which they occur, or processing data in the 05:07.840 --> 05:09.220 order in which it arrives. 05:10.240 --> 05:15.460 We can only access the front element OR the back element, that should be. If you want to be able to 05:15.460 --> 05:19.510 access other elements in the queue, then you could use a vector. 05:19.510 --> 05:22.150 But then you need to manage the ordering yourself. 05:22.870 --> 05:27.910 Or you could use a map, with the arrival order as the key, and the data as the value. 05:28.360 --> 05:32.950 And in that case, the map will order it automatically in arrival time. 05:34.760 --> 05:40.850 A queue does things strictly in order. First come, first served. And sometimes that is not always helpful 05:40.850 --> 05:41.540 in the real world. 05:42.110 --> 05:46.460 For example, if you have a queue of patients who are awaiting treatment, and somebody comes in who needs 05:46.460 --> 05:51.020 an emergency operation, that person needs to get their operation before the other patients get seen 05:51.020 --> 05:51.650 by the doctor. 05:52.640 --> 05:58.550 Or if you have an aeroplane which arrives and misses the take off, then it may need to be moved in 05:58.550 --> 06:00.320 front of aircraft which arrived later. 06:01.940 --> 06:03.410 OK, so that is it for this video. 06:03.800 --> 06:06.680 I will see you next time, but until then, keep coding!