Today we continue to learn Chapter 3 of Data Structure and Algorithm - Stack and Queue. 我们继续数据结构与算法第三章-栈与队列的学习。
The main content of this video is queue. 这一讲的主要内容是队列。
Queue is a First In First Out(FIFO) data structure. 那队列呢，它是一种先进先出的数据结构。 也可以简称FIFO。
Insertion is limited on one endpoint, and deletion limited on the other. 它限制插入操作在表的一端，删除在另一端进行。
Main elements of queue include head and tail. 主要的元素有队头和队尾。
Main operations are enqueue and dequeue. Its definition is like this. 那主要的操作呢，就是入队、出队。 相应的它的定义如下，
This is insertion, and this is deletion. 这个是插入，还有这个是删除操作。
The implementations of queue include 那队列的实现方式呢，
sequential and linked methods. For sequential method, pseudo overflow should be prevented. 就是有顺序和链式的两种，然后注意顺序里面呢，要防止假溢出。
This is an example of sequential queue. 那这个是顺序队列的一个例子。
In the situation of empty queue, we can see 'rear' should be in front of 'front'. 那在空队列的情况下呢，我们可以看到。 它的rear呢，是要在front的前面。
Actually, it is the case of none data. 其实也就是说，它是一个没有数据的这个情况。
Then, this is a queue of two elements. 然后呢，这是一个有两个元素的队列。
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指向的就是最后一个元素。
We do some insertions. 那我们在队里面进行插入操作，那
After some insertions we can see, if you add one more element, 插入了以后我们可以看到，如果你还要再加一个元素的时候，
you fail. It is a full queue, while there is an empty position. 这个时候，它是不能加入的。这已经是个满队列。虽然这里有一个空位子存在，
But in order to distinguish full queue and empty queue, the empty position must be setted. 但是我们为了区分这个满队列和空队列，那必须要有一个这样的空位置。
Actually it is a false overflow. 那实际上这就是它的一个虚的溢出。
In the definition of sequential queue, we use an array to store the elements of queue. 顺序队列的类定义呢，我们要用一个数组来存放这些队列的元素。
And there are pointers of front and rear, and 而且有front，rear指针，然后还有就是整个
area that the queue can accommodate. 这个队列的它的可容纳的最大的数据区域的这样一个大小。
Through subtracting rear by front, adding one, and mod mSize, 那队列里面有效元素的个数呢，我们实际上是可以通过
we can get the number of valid elements in queue. rear减front加一，再对这个mSize取模能够得出它的元素的大小。
Let us consider the maintaining of queue, mainly the pointers of front and rear. 那我们看一下队列的这个维护。也就是说我们这个front和rear。
When inserting, element is added in the end of queue, and rear changes. 如果是插入时候，那实际上是元素往后面插，然后rear指针发生改变。
When deleting, we shouldn't move the data forward. Just do as we did just now. 那删除的时候呢，我们不应该把这个数据往前挪位，应该像我们刚才那样子。
We maintain the front pointer by moving it backward when the data is deleted. 我们是通过这个front指针它的一个指向，就是在前面删了以后，front指针往后移来维护。
Just like this. 12 and 17 are unchanged in the queue. 也就是这样的一个情况。就是12,17在队列里面一直没有变化的。
After insertion and deletion, the queue becomes so. 然后呢通过这个插入和删除操作之后，这个，它的队列呢变成这个情况。
The front pointer is no longer in the most front of the array. 那这个front元素呢它已经不在这个，整个数组里面最前端了。
It is at the back, a effective position. It needn't move position as before when inserting and deleting. 它已经在后面，当前的有效位置。 这样的话呢就不需要像先前表里面插入删除挪动位置的一个操作。
It only keeps the position of the index of current effective element. 只需要保持当前的有效元素的它的下标位置。
That insures the time of insertion and deletion to be constant. 这就保证了我们的插入删除它的操作都是在大O(1)时间能够完成的。
Well, let us see the implementation of sequential queue. 那我们看一下这个顺序队列的实现。
We firstly consider the case of empty queue. 那首先呢就是对于这个空队列的情况，
Note that, the rear pointer locates in front of the front pointer. Then we consider the enqueue operation. 我们注意，这个rear呢它跑到了front前面的一位。 然后呢就是入队操作。
As we mentioned, we should reserve an empty position. That is, 那刚才我们说过，就是要留一个空位置，也就是
when there is only one empty position and you request an insertion, it would report that the queue is full. 在还有一个空位的时候，你要插入，我们就要报满。
With these two elements added, we have not let 所以加上这个两个元素，我们还没有达到
front and rear meet. So we can insert more elements. 这个front和rear它们相遇。那这样的话我们是可以插入元素的。
Because it is true-pointer, rear should be added by one, 那这个时候因为是实指，所以rear呢先要加一，
pointing the next insertable position. Dequeue is easier. 是下一个可插入的位置。 然后插入进去。出队操作呢，就相对比较简单。
We just confirm that there is element in queue, and get it out. 只需要判断这个队里面有元素，我们就可以把它取出来。
In sequential queue, reading is easier. If the queue is not empty, 在顺序队列里面，读的时候更简单了，主要是整个队列
we can read the first element out directly. 它不是空队列的情况下，我们就可以读出队首的元素。
Let us consider the case mentioned above. 我们思考一下，如果是在前面那种情况，
That is, if we only use variables of front, rear and the length of queue, 也就是我们只采用front、rear， 还有这个最大的队列的长度，
how many elements can the queue contain? 这样的几个变量。那么我们可以容纳的最大元素个数是多少？
Actually we have said, we should reserve one position. But why? Please present a derivation process. 那么其实我们刚才已经说过了，我们要预留一位。但是为什么要这样预留一位呢？请给出一个推导的过程。
Then if we don't want to waste this empty position, which method can we apply? 还有就是我们如果不愿意浪费这个空的存储单元，我们可以采用什么样的方法？
That is, we store n elements when the queue is full, and 0 when empty. 也就是说我这个满队列情况，我就是存N个元素，空队列当然是存零个。
There are some troubles to be overcome by some auxiliary methods. 那这样的话我们会有一些问题要处理的。因此可能一些辅助的方法。
For linked queue, we use single link to implement. 那链式队列呢，就是用单链的形式来实现的，
Then we should keep the two pointer of head and tail. 然后我们要注意要保持一个队首和队尾的两个个指针。
This is the definition of linked queue. 这是链式队列的类定义。
In addition, we can keep the number of current elements as a variable. 那还有就是我们也可以它保留当前的元素个数这样一个变量。
In the case of enqueue, we firstly see 入队的情况呢，我们就是首先看
whether it is empty queue. If it is, the element to be insert 是不是空队，如果是空队，这个先插入的元素
would be the head, and tail concurrently. Otherwise, the new element 就是它同时是队首，也是队尾，那否则添加的这个新元素嘛
should be added in the back of rear, and rear should be modified to point the new element. 要在这个rear之后添加，而且rear要指向新的元素。
In the case of deleting, namely dequeue, 删除的这个情况，就是出队，
if the queue is empty, it fails. 那如果队是空的，就是不能够删除。
Otherwise, we read the head element out. 否则的话呢，我们把这个队首的这个元素呢读出来，
Then modify the head pointer to point the next position. 然后呢把这个队首呢指向它的下一位，
Like this, we delete the head, 那这样的话就可以删掉当前的这个队首，而
and make the head pointer to point the next position we have stored. 这个队首指针呢就指向我们刚才已经保存好的这个下一位的位置。
The insertion and deletion operations of sequential and linked queues 顺序与链式队它们的插入和删除操作
cost big O(1) time, satisfying some upper-level operations. 都是大O(1)的时间，可以满足一些上层的运算。
In sequential queue, static storage is needed. Linked queue can cope with dynamic storage. 在顺序队列里面呢，它是需要有固定的存储空间的，链式队呢可以应付动态变化的情况。
They both reject visits to inner elements. 它们都是不允许访问队列内部元素的。
That is, you can not read inner elements, except head element. 也就是你不能在内部读。你要是在内部读，只能读队首元素。
Queue can be applied to many occasions, especially the First Come First Serve applications. 队列它也有很多的应用。 可以满足那些先来先服务的应用
Such as message buffer, mails, 例如那个像消息缓冲器，然后还有邮件，
and buffer of hardware device. 另外呢就是一些硬件通讯设备也是运用队列作为数据缓冲的。
Resource management in operating system also applies queue. 操作系统里面的资源管理，我们也有很多队列的应用。
Well, there are some variants of queue, such as priority queue. 那么，在，队列它还有一些变种，比如说是优先队列。
Processors in OS has priorities. To manage processors is to manage priority queue. 在操作系统里面进程它是有优先级的。对进程的管理实际是对优先队列的管理。
In our following complex data structures, such as tree and graph, 我们在后续的这些复杂数据结构，例如数和图里面我们都可以看到
we can see queue is applied widely, such as in breadth-first search. 队列可以是广泛的应用在宽度的优先搜索里面。
At last, please consider these questions. 最后留给大家一些思考题，
Why we use single linked list to implement queue rather than double linked list? 也就是我们为什么用单链来实现队列而不用双链？
And, if we apply false-pointers to a tail of a sequential queue, 还有就是如果对于顺序队列我们采用虚指的方法
what is the difference from the case we have introduced? 来表示这个尾指针，这种方法的话呢，它跟我们前面介绍的实指这样的方法
Thank you! 它有什么异同呢？谢谢！