Stacks · 栈
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
English
What is an ADT?
- An Abstract Data Type (ADT) is a collection of data plus a set of operations on it.
- You use the operations and ignore how it is built inside.
- A stack, a queue, and a linked list are all ADTs.
中文
什么是 ADT?
- 抽象数据类型(ADT,Abstract Data Type)是一组数据加上对它的一组操作。
- 你使用这些操作,而不必关心它内部是怎么实现的。
- 栈(stack)、队列(queue)和链表(linked list)都是 ADT。
English
A stack is LIFO
- A stack is Last In, First Out (LIFO).
- The last item you add is the first one you take off.
- Think of a stack of plates: you take the top plate first.
中文
栈是 LIFO
- 栈是后进先出(LIFO,Last In, First Out)。
- 你最后放进去的元素,会最先被取出来。
- 想象一摞盘子:你先拿最上面的那一个。
English
push and pop with a list
- We can build a stack from a Python list.
- push =
stack.append(x)— add to the end (the top). - pop =
stack.pop()— remove and return the end (the top).
中文
用列表实现 push 和 pop
- 我们可以用一个 Python 列表来构建栈。
- push(入栈)=
stack.append(x)—— 加到末尾(栈顶)。 - pop(出栈)=
stack.pop()—— 移除并返回末尾(栈顶)。
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
English
peek and empty
- peek at the top without removing it:
stack[-1]. - A stack is empty when
len(stack) == 0. - Popping an empty stack is an error, so check first.
中文
peek 与判空
- peek(查看栈顶)而不移除它:
stack[-1]。 - 当
len(stack) == 0时,栈是空的。 - 对空栈做 pop 会出错,所以要先检查。
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
English
In Cambridge pseudocode
- The exam builds a stack from an array plus a
toppointer (an index).
中文
用剑桥伪代码表示
- 考试用一个数组加上一个
top指针(一个索引)来构建栈。
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
English
Common mistakes
- A stack is last-in, first-out: push to the top, pop from the top.
- Check it is not empty before you pop.
中文
常见错误
- 栈是后进先出:从顶部压入,从顶部弹出。
- pop 之前先检查它不是空的。
English
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
中文
现在轮到你
- 把列表当作你的栈(用
append入栈,用pop移除)。 - 按检查答案来测试你的代码。
Explore · 探索
A stack is LIFO · 栈是后进先出
A stack pushes and pops at one end — last in, first out. · 栈在同一端压入和弹出——后进先出。
Start with an empty stack. Push 1, then 2, then 3. Then pop once, storing the removed value in top. (top should be 3 and the stack should be [1, 2].) · 从一个空栈开始。依次入栈 1、2、3。然后出栈一次,把移除的值存进 top。(top 应为 3,栈应为 [1, 2]。)
Click Run to see the output here. · 点击“运行”查看此处输出。
Use a stack to reverse the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].) · 用一个栈来反转列表 items。把每个元素都入栈,然后全部出栈到 result。(result 应为 [3, 2, 1]。)
Click Run to see the output here. · 点击“运行”查看此处输出。
Write top(stack) that returns · 返回值 the top item (the last one) without removing it. If the stack is empty, return None. · 编写 top(stack),返回栈顶元素(最后一个)且不移除它。如果栈是空的,返回 None。
Click Run to see the output here. · 点击“运行”查看此处输出。