Просмотр исходного текста страницы Принцип LIFO (Last In, First Out)

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

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

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

== Свойства LIFO ==

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

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

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

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

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

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

## ```python
## class Stack:
##     def __init__(self, capacity):
##         self.capacity = capacity
##         self.arr = [None] * capacity
##         self.top = -1
##
##     def push(self, data):
##         if self.top == self.capacity - 1:
##             print("Stack Overflow")
##             return
##         self.top += 1
##         self.arr[self.top] = data
##
##     def pop(self):
##         if self.top == -1:
##             print("Stack Underflow")
##             return None
##         data = self.arr[self.top]
##         self.arr[self.top] = None
##         self.top -= 1
##         return data
##
##     def peek(self):
##         if self.top == -1:
##             print("Stack is empty")
##             return None
##         return self.arr[self.top]
##
##     def isEmpty(self):
##         return self.top == -1
##
##     def size(self):
##         return self.top + 1
## ```
# '''Реализация стека с использованием связного списка''':

## ```python
## class Node:
##     def __init__(self, data):
##         self.data = data
##         self.next = None
##
## class Stack:
##     def __init__(self):
##         self.head = None
##         self.size = 0
##
##     def push(self, data):
##         new_node = Node(data)
##         new_node.next = self.head
##         self.head = new_node
##         self.size += 1
##
##     def pop(self):
##         if self.head is None:
##             print("Stack Underflow")
##             return None
##         data = self.head.data
##         self.head = self.head.next
##         self.size -= 1
##         return data
##
##     def peek(self):
##         if self.head is None:
##             print("Stack is empty")
##             return None
##         return self.head.data
##
##     def isEmpty(self):
##         return self.head is None
##
##     def size(self):
##         return self.size
## ```

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

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

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

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

# '''Проверка баланса скобок''':

## ```python
## def is_balanced(expression):
##     stack = []
##     for char in expression:
##         if char in "([{":
##             stack.append(char)
##         elif char in ")]}":
##             if not stack:
##                 return False
##             top = stack.pop()
##             if (char == ")" and top != "(") or \
##                (char == "]" and top != "[") or \
##                (char == "}" and top != "{"):
##                 return False
##     return not stack
##
## print(is_balanced("(){}[]"))  # Вывод: True
## print(is_balanced("({[}])"))  # Вывод: False
## ```
# '''Вычисление выражения в постфиксной нотации''':

## ```python
## def evaluate_postfix(expression):
##     stack = []
##     operators = {
##         "+": lambda a, b: a + b,
##         "-": lambda a, b: a - b,
##         "*": lambda a, b: a * b,
##         "/": lambda a, b: a / b
##     }
##     for token in expression.split():
##         if token.isdigit():
##             stack.append(int(token))
##         elif token in operators:
##             if len(stack) < 2:
##                 return "Invalid expression"
##             operand2 = stack.pop()
##             operand1 = stack.pop()
##             result = operators[token](operand1, operand2)
##             stack.append(result)
##         else:
##             return "Invalid token"
##     if len(stack) == 1:
##         return stack[0]
##     else:
##         return "Invalid expression"
##
## print(evaluate_postfix("3 4 + 2 *"))  # Вывод: 14
## ```

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

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

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

=== Недостатки: ===

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

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