Queues
Python for A-Level CS Lesson 5 2:03 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A queue is the other ADT, and it behaves like a line of people.
队列是另一个抽象数据类型，它的行为就像排队的人群。
A new item joins at the back.
新来的元素排到队尾。
The next item out leaves from the front.
下一个出去的元素从队首离开。
Put the two structures side by side and the difference is one sentence: a stack reverses the order you put things in, and a queue preserves it.
把这两种结构并排放着，区别就是一句话： 栈把你放进去的顺序颠倒过来，而队列把它保持住。
That is why a print queue is a queue and not a stack.
这就是为什么打印队列是队列，而不是栈。
You can build one from a Python list, just as you did with the stack.
你可以用 Python 的列表来构建它，就像刚才做栈那样。
Append still adds to the back.
append 仍然是加到后面。
But instead of a bare pop, you write pop of nought, which takes the first item rather than the last.
但取出时不是写光秃秃的 pop，而是写 pop(0)， 它取走的是第一个元素，而不是最后一个。
And index nought on its own looks at the front without removing it.
而单独写下标 0，就是看一眼队首而不取走它。
One character is the whole difference between a stack and a queue in code.
在代码里，栈和队列的全部区别，就是这一个字符。
But that one character has a price, and this is the first time in the course that a working answer is not automatically a good one.
但这一个字符是有代价的， 而这也是这门课里第一次出现"能跑"并不自动等于"好"。
Take the front item out of a list and everything else moves up one place, because index nought must now hold what used to be at index one.
从列表前端取走一个元素，其余所有元素都要往前挪一格， 因为下标 0 现在必须装着原来下标 1 的那个东西。
On a queue of a million items, that is a million moves for every single dequeue.
在一个有一百万个元素的队列上， 每出队一次，就是一百万次移动。
The exam's version avoids the whole problem.
考卷上的做法完全避开了这个问题。
It keeps two pointers, front and rear, and dequeuing just steps the front pointer along — nothing moves at all.
它维护两个指针，front 和 rear， 出队只是把 front 指针往前挪一格——什么都不用搬。
That is worth carrying with you beyond this lesson: does it work, and is it a good choice, are two questions, and an A-Level answer is expected to consider both.
这一点值得带出这一课： "它能不能用"和"它是不是好选择"是两个问题， 而 A-Level 的答案要求你把两者都考虑到。
Four things to take with you.
带走四点。
One: a queue is first in, first out.
第一：队列是先进先出。
Two: join at the back, and leave from the front.
第二：从队尾加入，从队首离开。
Three: a stack reverses an order and a queue preserves it.
第三：栈把顺序颠倒，队列把顺序保持。
Four: removing from the front of a list shifts every item along, which is a real cost.
第四：从列表前端删除，会让每一个元素都往前挪，这是实打实的代价。
Now do the four tasks.
现在去做那四道题。