Stacks
Python for A-Level CS Lesson 4 2:10 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A stack is the first abstract data type in this course, and the word abstract is doing real work.
栈是这门课里的第一个抽象数据类型，而"抽象"这个词是有实际含义的。
What defines a stack is its operations: push, pop, peek, is-empty.
定义一个栈的，是它的操作：push、pop、peek、is_empty。
How it is built inside is a separate question, and there is more than one way — a Python list, an array with a top index, a linked list.
它内部怎么实现，是另一个问题，而且不止一种做法—— 可以是 Python 的列表，可以是数组加一个 top 下标，也可以是链表。
Change the inside and every program that used the operations still works.
换掉内部实现，所有用这些操作的程序照样能跑。
The rule is last in, first out.
规则是后进先出。
Push three of them — one, then two, then three — and watch the pile grow upward.
连着 push 三个——1、然后 2、然后 3——看着这摞东西往上长。
Now pop, and the three comes back, because it was the last one on.
现在 pop，回来的是 3，因为它是最后放上去的那个。
Nothing else can come off first; there is no way to reach the one at the bottom without taking everything above it off.
别的都不可能先出来； 不把上面的全部拿掉，你没有办法够到最底下那个。
Since the inside is a choice, it is worth seeing the one the exam makes.
既然内部实现是一种选择，那就值得看看考卷选的是哪一种。
It builds a stack from an array and a pointer called top, which holds how many items are in.
它用一个数组，加上一个叫 top 的指针来构建栈， top 记录着里面有几个元素。
Pushing moves the pointer up and writes there; popping moves it down and reads.
入栈是把指针往上移一格再写进去； 出栈是把它往下移一格再读出来。
Python's append and pop do exactly that, with the pointer kept for you.
Python 的 append 和 pop 做的正是这件事，只是那个指针由它替你维护。
The second task reverses a list, and it shows what a stack is naturally good at.
第二道题是把一个列表反转，它展示了栈天生擅长的事。
Push every item on, then pop them all off into a new list — and it comes out backwards.
把每个元素都 push 进去，再全部 pop 出来放进一个新列表—— 出来的就是倒序的。
Notice you did not write a reversing algorithm anywhere; LIFO did it for you.
注意你并没有在任何地方写过反转算法； 是"后进先出"替你做了。
That is why an undo feature is a stack, and why the call stack that returns from your functions is one too.
这就是为什么"撤销"功能是一个栈， 也是为什么让函数逐层返回的调用栈同样是一个栈。
Four things to take with you.
带走四点。
One: an ADT is a set of operations, not an implementation.
第一：抽象数据类型是一组操作，不是一种实现。
Two: a stack is last in, first out.
第二：栈是后进先出。
Three: peek reads the top without removing it.
第三：peek 读取栈顶，但不取走它。
Four: pushing everything then popping it reverses an order.
第四：全部压入再全部弹出，就把顺序反了过来。
Now do the three tasks, and check the stack is not empty before you pop.
现在去做那三道题， 而且在 pop 之前先确认栈不是空的。