Что такое ADT?
- Абстрактный тип данных (ADT) — это набор данных плюс набор операций над ними.
- Вы используете операции и игнорируете, как они реализованы внутри.
- Стек, очередь и связный список — всё это ADT.
Стек работает по принципу LIFO
- Стек работает по принципу Last In, First Out (LIFO — последний вошел, первый вышел).
- Последний добавленный элемент является первым извлеченным.
- Представьте стопку тарелок: вы берете верхнюю тарелку первой.
push и pop со списком
- Мы можем создать стек на основе списка Python.
- push =
stack.append(x)— добавить в конец (на вершину). - pop =
stack.pop()— удалить и вернуть конец (вершину).
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
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?
В псевдокоде 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
Распространенные ошибки
- Стек работает по принципу last-in, first-out: push на вершину, pop с вершины.
- Проверяйте, что он не пуст, перед тем как выполнять pop.
Теперь попробуйте сами
- Используйте список в качестве стека (
appendдля push,popдля удаления). - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Стек работает по принципу LIFO
A stack pushes and pops at one end — last in, first out.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
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].)
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Use a stack to обратным the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].)
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Write top(stack) that отдачи the top item (the last one) without removing it. If the stack is empty, return None.
Нажмите Запустить, чтобы увидеть результат здесь.