Курс Модуль 1: Python Core - Лекція: Стек

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)  # Вивід: ""