Принцип LIFO (Last In, First Out)

Принцип LIFO (Last In, First Out) — это принцип организации данных, при котором последний добавленный элемент является первым, который будет извлечен. Этот принцип является основой для структуры данных, называемой стеком (stack).

Основные понятия

1. Стек (Stack): Абстрактная структура данных, представляющая собой упорядоченную коллекцию элементов, в которой добавление и удаление элементов происходит только с одной стороны, называемой вершиной стека (top).
2. Вершина стека (Top): Место, где происходит добавление и удаление элементов в стеке.
3. Добавление элемента (Push): Операция добавления нового элемента на вершину стека.
4. Удаление элемента (Pop): Операция удаления элемента с вершины стека.
5. Последний вошел, первым вышел (Last In, First Out - LIFO): Элемент, добавленный в стек последним, будет удален из стека первым.

Свойства LIFO

1. Упорядоченность: Элементы в стеке хранятся в определенном порядке, который определяется порядком их добавления.
2. Ограниченный доступ: Доступ к элементам стека ограничен только вершиной стека. Невозможно получить доступ к элементам, находящимся внутри стека, без удаления элементов с вершины.
3. Простота реализации: Стек является простой структурой данных, которую легко реализовать с использованием массивов или связных списков.

Операции над стеком

1. Push (Добавление): Добавляет новый элемент на вершину стека.
   1. Сложность: $O(1)$
2. Pop (Удаление): Удаляет элемент с вершины стека и возвращает его значение.
   1. Сложность: $O(1)$
3. Peek (Просмотр): Возвращает значение элемента, находящегося на вершине стека, не удаляя его.
   1. Сложность: $O(1)$
4. isEmpty (Проверка на пустоту): Проверяет, является ли стек пустым. Возвращает `true`, если стек пуст, и `false` в противном случае.
   1. Сложность: $O(1)$
5. size (Размер): Возвращает количество элементов в стеке.
   1. Сложность: $O(1)$

Реализация стека

Стек можно реализовать с использованием массивов или связных списков.

1. Реализация стека с использованием массива:

1. 1. ```python
   2. class Stack:
   3. def __init__(self, capacity):
   4. self.capacity = capacity
   5. self.arr = [None] * capacity
   6. self.top = -1
   8. def push(self, data):
   9. if self.top == self.capacity - 1:
   10. print("Stack Overflow")
   11. return
   12. self.top += 1
   13. self.arr[self.top] = data
   15. def pop(self):
   16. if self.top == -1:
   17. print("Stack Underflow")
   18. return None
   19. data = self.arr[self.top]
   20. self.arr[self.top] = None
   21. self.top -= 1
   22. return data
   24. def peek(self):
   25. if self.top == -1:
   26. print("Stack is empty")
   27. return None
   28. return self.arr[self.top]
   30. def isEmpty(self):
   31. return self.top == -1
   33. def size(self):
   34. return self.top + 1
   35. ```
2. Реализация стека с использованием связного списка:

1. 1. ```python
   2. class Node:
   3. def __init__(self, data):
   4. self.data = data
   5. self.next = None
   7. class Stack:
   8. def __init__(self):
   9. self.head = None
   10. self.size = 0
   12. def push(self, data):
   13. new_node = Node(data)
   14. new_node.next = self.head
   15. self.head = new_node
   16. self.size += 1
   18. def pop(self):
   19. if self.head is None:
   20. print("Stack Underflow")
   21. return None
   22. data = self.head.data
   23. self.head = self.head.next
   24. self.size -= 1
   25. return data
   27. def peek(self):
   28. if self.head is None:
   29. print("Stack is empty")
   30. return None
   31. return self.head.data
   33. def isEmpty(self):
   34. return self.head is None
   36. def size(self):
   37. return self.size
   38. ```

Применение стеков

Стеки используются в широком спектре приложений, включая:

1. Вычисление выражений: Стеки используются для разбора и вычисления математических выражений в инфиксной, префиксной или постфиксной нотации.
2. Управление вызовами функций: Стеки используются для хранения информации о вызовах функций (адреса возврата, параметры функций, локальные переменные).
3. Реализация алгоритмов поиска в глубину (DFS): Стеки используются для хранения информации о посещенных вершинах графа.
4. Отмена действий (Undo): Стеки используются для хранения информации о последних выполненных действиях, чтобы пользователь мог их отменить.
5. Проверка баланса скобок: Стеки используются для проверки правильности расстановки скобок в выражениях.
6. Алгоритмы обхода деревьев: Стеки используются для реализации нерекурсивных алгоритмов обхода деревьев.

Примеры использования стека

1. Проверка баланса скобок:

1. 1. ```python
   2. def is_balanced(expression):
   3. stack = []
   4. for char in expression:
   5. if char in "([{":
   6. stack.append(char)
   7. elif char in ")]}":
   8. if not stack:
   9. return False
   10. top = stack.pop()
   11. if (char == ")" and top != "(") or \
   12. (char == "]" and top != "[") or \
   13. (char == "}" and top != "{"):
   14. return False
   15. return not stack
   17. print(is_balanced("(){}[]")) # Вывод: True
   18. print(is_balanced("({[}])")) # Вывод: False
   19. ```
2. Вычисление выражения в постфиксной нотации:

1. 1. ```python
   2. def evaluate_postfix(expression):
   3. stack = []
   4. operators = {
   5. "+": lambda a, b: a + b,
   6. "-": lambda a, b: a - b,
   7. "*": lambda a, b: a * b,
   8. "/": lambda a, b: a / b
   9. }
   10. for token in expression.split():
   11. if token.isdigit():
   12. stack.append(int(token))
   13. elif token in operators:
   14. if len(stack) < 2:
   15. return "Invalid expression"
   16. operand2 = stack.pop()
   17. operand1 = stack.pop()
   18. result = operators[token](operand1, operand2)
   19. stack.append(result)
   20. else:
   21. return "Invalid token"
   22. if len(stack) == 1:
   23. return stack[0]
   24. else:
   25. return "Invalid expression"
   27. print(evaluate_postfix("3 4 + 2 *")) # Вывод: 14
   28. ```

Преимущества и недостатки использования стеков

Преимущества:

1. Простота реализации: Стеки легко реализовать с использованием массивов или связных списков.
2. Эффективность операций: Операции добавления и удаления элементов выполняются за константное время $O(1)$.
3. Широкий спектр применения: Стеки используются в различных областях программирования.

Недостатки:

1. Ограниченный доступ: Доступ к элементам стека ограничен только вершиной стека.
2. Фиксированный размер (при реализации с использованием массива): При реализации стека с использованием массива необходимо заранее определять его размер, что может быть ограничением в некоторых случаях.

Понимание принципа LIFO и стеков является важным для разработки эффективного и надежного программного обеспечения.