6.1 Определение стека и его свойства
Стек — это абстрактная структура данных, представляющая собой коллекцию элементов, организованную по принципу "последним пришёл — первым ушёл" (Last In, First Out, LIFO). Стек можно представить как стопку книг: последняя добавленная книга находится на вершине стопки и будет удалена/взята первой.
Свойства стека:
LIFO(Last In, First Out): Последний добавленный элемент извлекается первым.- Ограниченные операции: В стеке поддерживаются только добавление
(push), удаление(pop)и просмотр(peek)элемента на вершине. - Однонаправленный доступ: Доступ к элементам возможен только с вершины стека.
- Простота реализации: Стек можно легко реализовать с помощью массива или связного списка.
- Управление памятью: Временные данные или состояния могут храниться и извлекаться в обратном порядке их добавления.
Принцип работы LIFO:
- Добавление элемента
(push): Новый элемент добавляется на вершину стека. - Удаление элемента
(pop): Последний добавленный элемент удаляется с вершины стека. - Просмотр вершины
(peek): Позволяет увидеть элемент на вершине стека без его удаления.
Элементы стека добавляются и удаляются с одной стороны, называемой вершиной (top). Таким образом, последний добавленный элемент всегда оказывается на вершине и будет удалён первым.
6.2 Основные операции
Основные операции: push, pop, peek
Операция push: Добавляет новый элемент на вершину стека.
Временная сложность: O(1).
Пример эмуляции стека на Python с помощью класса list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Вывод: [10, 20]
Операция pop: Удаляет и возвращает элемент с вершины стека.
Временная сложность: O(1).
Пример эмуляции стека на Python с помощью класса list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Вывод: 20
print(stack) # Вывод: [10]
Операция peek: Возвращает элемент на вершине стека без его удаления.
Временная сложность: O(1).
Пример реализации:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Вывод: 10
6.3 Примеры использования стека
Давайте приведём несколько примеров использования стека:
Управление вызовами функций
В Python стек используется для отслеживания функций во время выполнения программы. Каждый раз, когда функция вызывается, её адрес возврата и локальные переменные помещаются в стек. Когда функция завершает выполнение, управление возвращается к функции, которая вызвала её, и данные извлекаются из стека.
Пример использования стека вызовов:
В этом примере рекурсивные вызовы функции factorial используют стек вызовов для хранения состояния каждого вызова до тех пор, пока не будет достигнуто базовое условие (n == 1).
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Вывод: 120
Отмена операций (Undo)
Стек используется для реализации функции отмены действий в текстовых редакторах и других приложениях. Когда пользователь выполняет действие, оно сохраняется в стек. При выполнении операции Undo последнее действие извлекается из стека и отменяется.
Пример использования стека для отмены операций:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Пример использования:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Вывод: "Hello World"
editor.undo()
print(editor.text) # Вывод: "Hello"
editor.undo()
print(editor.text) # Вывод: ""
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ