1 00:00:00,000 --> 00:00:04,750 Today we continue to learn Chapter 3 of Data Structure and Algorithm - Stack and Queue. 我们继续数据结构与算法第三章-栈与队列的学习。 2 00:00:04,750 --> 00:00:08,370 The main content of this video is queue. 这一讲的主要内容是队列。 3 00:00:08,370 --> 00:00:16,570 Queue is a First In First Out(FIFO) data structure. 那队列呢,它是一种先进先出的数据结构。 也可以简称FIFO。 4 00:00:16,570 --> 00:00:22,210 Insertion is limited on one endpoint, and deletion limited on the other. 它限制插入操作在表的一端,删除在另一端进行。 5 00:00:22,210 --> 00:00:26,510 Main elements of queue include head and tail. 主要的元素有队头和队尾。 6 00:00:26,510 --> 00:00:34,580 Main operations are enqueue and dequeue. Its definition is like this. 那主要的操作呢,就是入队、出队。 相应的它的定义如下, 7 00:00:34,580 --> 00:00:39,950 This is insertion, and this is deletion. 这个是插入,还有这个是删除操作。 8 00:00:39,950 --> 00:00:44,920 The implementations of queue include 那队列的实现方式呢, 9 00:00:44,920 --> 00:00:49,890 sequential and linked methods. For sequential method, pseudo overflow should be prevented. 就是有顺序和链式的两种,然后注意顺序里面呢,要防止假溢出。 10 00:00:49,890 --> 00:00:55,210 This is an example of sequential queue. 那这个是顺序队列的一个例子。 11 00:00:55,210 --> 00:01:03,045 In the situation of empty queue, we can see 'rear' should be in front of 'front'. 那在空队列的情况下呢,我们可以看到。 它的rear呢,是要在front的前面。 12 00:01:03,045 --> 00:01:07,250 Actually, it is the case of none data. 其实也就是说,它是一个没有数据的这个情况。 13 00:01:07,250 --> 00:01:13,715 Then, this is a queue of two elements. 然后呢,这是一个有两个元素的队列。 14 00:01:13,715 --> 00:01:20,180 The pointers of front and rear are both true-pointers. In other words, front points to the first element, while rear points to the last element. 那front和rear呢,它都是实指。也就是这个front指向的就是第一个元素,rear指向的就是最后一个元素。 15 00:01:20,180 --> 00:01:25,460 We do some insertions. 那我们在队里面进行插入操作,那 16 00:01:25,460 --> 00:01:30,740 After some insertions we can see, if you add one more element, 插入了以后我们可以看到,如果你还要再加一个元素的时候, 17 00:01:30,740 --> 00:01:37,760 you fail. It is a full queue, while there is an empty position. 这个时候,它是不能加入的。这已经是个满队列。虽然这里有一个空位子存在, 18 00:01:37,760 --> 00:01:44,380 But in order to distinguish full queue and empty queue, the empty position must be setted. 但是我们为了区分这个满队列和空队列,那必须要有一个这样的空位置。 19 00:01:44,380 --> 00:01:49,770 Actually it is a false overflow. 那实际上这就是它的一个虚的溢出。 20 00:01:49,770 --> 00:01:56,400 In the definition of sequential queue, we use an array to store the elements of queue. 顺序队列的类定义呢,我们要用一个数组来存放这些队列的元素。 21 00:01:56,400 --> 00:02:01,190 And there are pointers of front and rear, and 而且有front,rear指针,然后还有就是整个 22 00:02:01,190 --> 00:02:05,980 area that the queue can accommodate. 这个队列的它的可容纳的最大的数据区域的这样一个大小。 23 00:02:05,980 --> 00:02:12,750 Through subtracting rear by front, adding one, and mod mSize, 那队列里面有效元素的个数呢,我们实际上是可以通过 24 00:02:12,750 --> 00:02:19,520 we can get the number of valid elements in queue. rear减front加一,再对这个mSize取模能够得出它的元素的大小。 25 00:02:19,520 --> 00:02:26,340 Let us consider the maintaining of queue, mainly the pointers of front and rear. 那我们看一下队列的这个维护。也就是说我们这个front和rear。 26 00:02:26,340 --> 00:02:33,160 When inserting, element is added in the end of queue, and rear changes. 如果是插入时候,那实际上是元素往后面插,然后rear指针发生改变。 27 00:02:33,160 --> 00:02:39,870 When deleting, we shouldn't move the data forward. Just do as we did just now. 那删除的时候呢,我们不应该把这个数据往前挪位,应该像我们刚才那样子。 28 00:02:39,870 --> 00:02:46,580 We maintain the front pointer by moving it backward when the data is deleted. 我们是通过这个front指针它的一个指向,就是在前面删了以后,front指针往后移来维护。 29 00:02:46,580 --> 00:02:54,100 Just like this. 12 and 17 are unchanged in the queue. 也就是这样的一个情况。就是12,17在队列里面一直没有变化的。 30 00:02:54,100 --> 00:03:00,715 After insertion and deletion, the queue becomes so. 然后呢通过这个插入和删除操作之后,这个,它的队列呢变成这个情况。 31 00:03:00,715 --> 00:03:07,330 The front pointer is no longer in the most front of the array. 那这个front元素呢它已经不在这个,整个数组里面最前端了。 32 00:03:07,330 --> 00:03:15,480 It is at the back, a effective position. It needn't move position as before when inserting and deleting. 它已经在后面,当前的有效位置。 这样的话呢就不需要像先前表里面插入删除挪动位置的一个操作。 33 00:03:15,480 --> 00:03:21,030 It only keeps the position of the index of current effective element. 只需要保持当前的有效元素的它的下标位置。 34 00:03:21,030 --> 00:03:27,090 That insures the time of insertion and deletion to be constant. 这就保证了我们的插入删除它的操作都是在大O(1)时间能够完成的。 35 00:03:27,090 --> 00:03:32,600 Well, let us see the implementation of sequential queue. 那我们看一下这个顺序队列的实现。 36 00:03:32,600 --> 00:03:37,025 We firstly consider the case of empty queue. 那首先呢就是对于这个空队列的情况, 37 00:03:37,025 --> 00:03:44,840 Note that, the rear pointer locates in front of the front pointer. Then we consider the enqueue operation. 我们注意,这个rear呢它跑到了front前面的一位。 然后呢就是入队操作。 38 00:03:44,840 --> 00:03:51,020 As we mentioned, we should reserve an empty position. That is, 那刚才我们说过,就是要留一个空位置,也就是 39 00:03:51,020 --> 00:03:56,370 when there is only one empty position and you request an insertion, it would report that the queue is full. 在还有一个空位的时候,你要插入,我们就要报满。 40 00:03:56,370 --> 00:04:02,050 With these two elements added, we have not let 所以加上这个两个元素,我们还没有达到 41 00:04:02,050 --> 00:04:06,735 front and rear meet. So we can insert more elements. 这个front和rear它们相遇。那这样的话我们是可以插入元素的。 42 00:04:06,735 --> 00:04:11,420 Because it is true-pointer, rear should be added by one, 那这个时候因为是实指,所以rear呢先要加一, 43 00:04:11,420 --> 00:04:17,720 pointing the next insertable position. Dequeue is easier. 是下一个可插入的位置。 然后插入进去。出队操作呢,就相对比较简单。 44 00:04:17,720 --> 00:04:21,960 We just confirm that there is element in queue, and get it out. 只需要判断这个队里面有元素,我们就可以把它取出来。 45 00:04:21,960 --> 00:04:28,080 In sequential queue, reading is easier. If the queue is not empty, 在顺序队列里面,读的时候更简单了,主要是整个队列 46 00:04:28,080 --> 00:04:32,950 we can read the first element out directly. 它不是空队列的情况下,我们就可以读出队首的元素。 47 00:04:32,950 --> 00:04:37,395 Let us consider the case mentioned above. 我们思考一下,如果是在前面那种情况, 48 00:04:37,395 --> 00:04:44,830 That is, if we only use variables of front, rear and the length of queue, 也就是我们只采用front、rear, 还有这个最大的队列的长度, 49 00:04:44,830 --> 00:04:51,095 how many elements can the queue contain? 这样的几个变量。那么我们可以容纳的最大元素个数是多少? 50 00:04:51,095 --> 00:04:57,360 Actually we have said, we should reserve one position. But why? Please present a derivation process. 那么其实我们刚才已经说过了,我们要预留一位。但是为什么要这样预留一位呢?请给出一个推导的过程。 51 00:04:57,360 --> 00:05:04,840 Then if we don't want to waste this empty position, which method can we apply? 还有就是我们如果不愿意浪费这个空的存储单元,我们可以采用什么样的方法? 52 00:05:04,840 --> 00:05:12,090 That is, we store n elements when the queue is full, and 0 when empty. 也就是说我这个满队列情况,我就是存N个元素,空队列当然是存零个。 53 00:05:12,090 --> 00:05:18,120 There are some troubles to be overcome by some auxiliary methods. 那这样的话我们会有一些问题要处理的。因此可能一些辅助的方法。 54 00:05:18,120 --> 00:05:24,125 For linked queue, we use single link to implement. 那链式队列呢,就是用单链的形式来实现的, 55 00:05:24,125 --> 00:05:30,130 Then we should keep the two pointer of head and tail. 然后我们要注意要保持一个队首和队尾的两个个指针。 56 00:05:30,130 --> 00:05:33,670 This is the definition of linked queue. 这是链式队列的类定义。 57 00:05:33,670 --> 00:05:40,620 In addition, we can keep the number of current elements as a variable. 那还有就是我们也可以它保留当前的元素个数这样一个变量。 58 00:05:40,620 --> 00:05:45,400 In the case of enqueue, we firstly see 入队的情况呢,我们就是首先看 59 00:05:45,400 --> 00:05:50,180 whether it is empty queue. If it is, the element to be insert 是不是空队,如果是空队,这个先插入的元素 60 00:05:50,180 --> 00:05:55,475 would be the head, and tail concurrently. Otherwise, the new element 就是它同时是队首,也是队尾,那否则添加的这个新元素嘛 61 00:05:55,475 --> 00:06:00,770 should be added in the back of rear, and rear should be modified to point the new element. 要在这个rear之后添加,而且rear要指向新的元素。 62 00:06:00,770 --> 00:06:04,640 In the case of deleting, namely dequeue, 删除的这个情况,就是出队, 63 00:06:04,640 --> 00:06:10,100 if the queue is empty, it fails. 那如果队是空的,就是不能够删除。 64 00:06:10,100 --> 00:06:16,500 Otherwise, we read the head element out. 否则的话呢,我们把这个队首的这个元素呢读出来, 65 00:06:16,500 --> 00:06:22,200 Then modify the head pointer to point the next position. 然后呢把这个队首呢指向它的下一位, 66 00:06:22,200 --> 00:06:27,480 Like this, we delete the head, 那这样的话就可以删掉当前的这个队首,而 67 00:06:27,480 --> 00:06:32,760 and make the head pointer to point the next position we have stored. 这个队首指针呢就指向我们刚才已经保存好的这个下一位的位置。 68 00:06:32,760 --> 00:06:37,405 The insertion and deletion operations of sequential and linked queues 顺序与链式队它们的插入和删除操作 69 00:06:37,405 --> 00:06:42,050 cost big O(1) time, satisfying some upper-level operations. 都是大O(1)的时间,可以满足一些上层的运算。 70 00:06:42,050 --> 00:06:49,510 In sequential queue, static storage is needed. Linked queue can cope with dynamic storage. 在顺序队列里面呢,它是需要有固定的存储空间的,链式队呢可以应付动态变化的情况。 71 00:06:49,510 --> 00:06:54,210 They both reject visits to inner elements. 它们都是不允许访问队列内部元素的。 72 00:06:54,210 --> 00:06:58,910 That is, you can not read inner elements, except head element. 也就是你不能在内部读。你要是在内部读,只能读队首元素。 73 00:06:58,910 --> 00:07:07,420 Queue can be applied to many occasions, especially the First Come First Serve applications. 队列它也有很多的应用。 可以满足那些先来先服务的应用 74 00:07:07,420 --> 00:07:12,570 Such as message buffer, mails, 例如那个像消息缓冲器,然后还有邮件, 75 00:07:12,570 --> 00:07:18,580 and buffer of hardware device. 另外呢就是一些硬件通讯设备也是运用队列作为数据缓冲的。 76 00:07:18,580 --> 00:07:23,250 Resource management in operating system also applies queue. 操作系统里面的资源管理,我们也有很多队列的应用。 77 00:07:23,250 --> 00:07:27,920 Well, there are some variants of queue, such as priority queue. 那么,在,队列它还有一些变种,比如说是优先队列。 78 00:07:27,920 --> 00:07:34,690 Processors in OS has priorities. To manage processors is to manage priority queue. 在操作系统里面进程它是有优先级的。对进程的管理实际是对优先队列的管理。 79 00:07:34,690 --> 00:07:40,270 In our following complex data structures, such as tree and graph, 我们在后续的这些复杂数据结构,例如数和图里面我们都可以看到 80 00:07:40,270 --> 00:07:45,850 we can see queue is applied widely, such as in breadth-first search. 队列可以是广泛的应用在宽度的优先搜索里面。 81 00:07:45,850 --> 00:07:50,085 At last, please consider these questions. 最后留给大家一些思考题, 82 00:07:50,085 --> 00:07:54,320 Why we use single linked list to implement queue rather than double linked list? 也就是我们为什么用单链来实现队列而不用双链? 83 00:07:54,320 --> 00:08:00,750 And, if we apply false-pointers to a tail of a sequential queue, 还有就是如果对于顺序队列我们采用虚指的方法 84 00:08:00,750 --> 00:08:07,180 what is the difference from the case we have introduced? 来表示这个尾指针,这种方法的话呢,它跟我们前面介绍的实指这样的方法 85 00:08:07,180 --> 00:08:12,670 Thank you! 它有什么异同呢?谢谢!