Stacks and queues
C Programming Lesson 18 2:21 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A stack and a queue both hold a line of items.
栈和队列都装着一排元素。
They differ in one thing only: which item comes out next.
它们只有一点不同：下一个出来的是哪一个。
Put one, two and three into a stack and it behaves like a pile of plates — you take the last one you put on, so three comes back first.
把 1、2、3 放进栈里，它的表现就像一摞盘子—— 你拿走的是最后放上去的那一个，所以先出来的是 3。
Put the same three into a queue and it behaves like a line of people: out comes the one who arrived first.
把同样的三个放进队列，它的表现就像排队的人： 出来的是最先到的那一个。
Same items in, opposite order out.
放进去的一样，出来的顺序正好相反。
In code, a stack is an array plus one number called top.
在代码里，一个栈就是一个数组，加上一个叫 top 的数字。
And read that number carefully, because it is where the mistakes come from: top is not the index of the top item, it is how many are in.
而这个数字要仔细读，因为错误都出在这里： top 不是栈顶元素的下标，它是“里面有几个”。
So to push, write at top and step up afterwards.
所以入栈时，先写在 top 位置，然后再加一。
To pop, step down first, then read.
出栈时，先减一，然后再读。
And the item on top, without moving anything, sits at top minus one.
而在不移动任何东西的情况下， 栈顶那个元素位于 top 减 1 处。
A queue needs two numbers, because things arrive at one end and leave at the other.
队列需要两个数字，因为元素从一头进来，从另一头出去。
Front is the next to leave.
front 是下一个要离开的。
Back is the next free slot.
back 是下一个空位。
Enqueue writes at back and moves back along; dequeue reads at front and moves front along.
入队时写在 back 处，然后 back 往前挪； 出队时读 front 处，然后 front 往前挪。
So the front chases the back up the array, and the used part of it drifts forwards as the queue runs.
于是 front 一路追着 back 在数组里前进， 队列使用中的那一段也就随之往前漂移。
The second task is peek: return the top item without removing it.
第二道题是 peek：返回栈顶元素，但不把它取走。
Put it next to pop and the whole thing is clear.
把它和 pop 并排放在一起，一切就清楚了。
Pop steps top down and then reads.
pop 先把 top 减一，然后再读。
Peek reads the same box — top minus one — and leaves top exactly where it was.
peek 读的是同一个格子——top 减 1—— 并且让 top 停在原处不动。
Both look at the same value; only one of them changes the stack.
两者看的是同一个值；只有其中一个改变了这个栈。
That is the difference between looking and taking.
这就是“看一眼”和“拿走”的区别。
Four things to take with you.
带走四点。
One: a stack is last in, first out — you push and pop at the top.
第一：栈是后进先出——在顶部入栈和出栈。
Two: a queue is first in, first out — in at the back, out at the front.
第二：队列是先进先出——从尾部进，从头部出。
Three: top is a count, so the top item sits at top minus one.
第三：top 是个数，所以栈顶元素位于 top 减 1 处。
Four: peek reads the top without changing anything.
第四：peek 读取栈顶，但什么都不改变。
Now do the three tasks, and check the structure is not empty before you take from it.
现在去做那三道题， 并且在取元素之前，先确认结构不是空的。