Stacks · Стеки
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) — это набор данных плюс набор операций над ними.
- Вы используете операции и игнорируете, как они реализованы внутри.
- Стек, очередь и связный список — всё это ADT.
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
- Стек работает по принципу Last In, First Out (LIFO — последний вошел, первый вышел).
- Последний добавленный элемент является первым извлеченным.
- Представьте стопку тарелок: вы берете верхнюю тарелку первой.
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)
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 и empty
- peek (посмотреть) на вершину без удаления:
stack[-1]. - Стек считается пустым, когда
len(stack) == 0. - Извлечение из пустого стека — ошибка, поэтому проверяйте сначала.
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
In Cambridge pseudocode
- The exam builds a stack from an array plus a
toppointer (an index).
В псевдокоде Cambridge
- На экзамене стек строится на массиве со указателем
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
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.
Распространенные ошибки
- Стек работает по принципу last-in, first-out: push на вершину, pop с вершины.
- Проверяйте, что он не пуст, перед тем как выполнять pop.
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
Теперь попробуйте сами
- Используйте список в качестве стека (
appendдля push,popдля удаления). - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
A stack is LIFO · Стек работает по принципу LIFO
A stack pushes and pops at one end — last in, first out. · Стек выполняет операции добавления (push) и удаления (pop) с одной стороны — последний вошёл, первый вышел.
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].) · Начните с пустого стека. Добавьте (push) элементы 1, затем 2, затем 3. Затем выполните одну операцию удаления (pop), сохранив удалённое значение в переменную 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. · Нажмите Запустить, чтобы увидеть результат здесь.