Операции: push, pop, peek

Операции push, pop и peek являются основными операциями, выполняемыми над стеком (stack), структурой данных, основанной на принципе LIFO (Last In, First Out).

Push (Добавление)

Push — это операция добавления нового элемента на вершину стека.

1. Описание: Добавляет элемент в верхнюю часть стека, увеличивая его размер на единицу.
2. Параметры: Элемент, который нужно добавить в стек.
3. Возвращаемое значение: Отсутствует (в большинстве реализаций).
4. Временная сложность: $O(1)$ (константное время), так как операция выполняется непосредственно на вершине стека.
5. Пример реализации (Python):
   1. ```python
   2. class Stack:
   3. def __init__(self):
   4. self.items = []
   6. def push(self, item):
   7. self.items.append(item)
   8. ```

Особенности операции push:

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

Pop (Удаление)

Pop — это операция удаления элемента с вершины стека.

1. Описание: Удаляет элемент из верхней части стека, уменьшая его размер на единицу.
2. Параметры: Отсутствуют.
3. Возвращаемое значение: Элемент, удаленный с вершины стека.
4. Временная сложность: $O(1)$ (константное время), так как операция выполняется непосредственно на вершине стека.
5. Пример реализации (Python):
   1. ```python
   2. class Stack:
   3. def __init__(self):
   4. self.items = []
   6. def pop(self):
   7. if not self.is_empty():
   8. return self.items.pop()
   9. else:
   10. return None # Или выбросить исключение
   12. def is_empty(self):
   13. return len(self.items) == 0
   14. ```

Особенности операции pop:

1. Опустошение стека (Stack Underflow): Если стек пуст, то при попытке удаления элемента из стека происходит опустошение стека. В этом случае необходимо предусмотреть обработку ошибки или возвращать специальное значение (например, `None`).
2. Обработка исключений: В некоторых реализациях стека при попытке удаления элемента из пустого стека выбрасывается исключение.

Peek (Просмотр)

Peek — это операция просмотра элемента, находящегося на вершине стека, без его удаления.

1. Описание: Возвращает значение элемента, находящегося на вершине стека, не удаляя его.
2. Параметры: Отсутствуют.
3. Возвращаемое значение: Элемент, находящийся на вершине стека.
4. Временная сложность: $O(1)$ (константное время), так как операция выполняется непосредственно на вершине стека.
5. Пример реализации (Python):
   1. ```python
   2. class Stack:
   3. def __init__(self):
   4. self.items = []
   6. def peek(self):
   7. if not self.is_empty():
   8. return self.items[-1]
   9. else:
   10. return None # Или выбросить исключение
   12. def is_empty(self):
   13. return len(self.items) == 0
   14. ```

Особенности операции peek:

1. Пустой стек: Если стек пуст, то операция peek должна возвращать специальное значение (например, `None`) или выбрасывать исключение.
2. Неизменность стека: Операция peek не должна изменять состояние стека.

Сводная таблица операций

Операция	Описание	Параметры	Возвращаемое значение	Временная сложность
Push	Добавляет элемент на вершину стека	Элемент для добавления	Отсутствует	$O(1)$
Pop	Удаляет элемент с вершины стека	Отсутствуют	Удаленный элемент	$O(1)$
Peek	Возвращает значение элемента на вершине стека, не удаляя его	Отсутствуют	Элемент на вершине стека	$O(1)$

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

1. Добавление элементов в стек:

1. 1. ```python
   2. stack = Stack()
   3. stack.push(10)
   4. stack.push(20)
   5. stack.push(30)
   6. ```
2. Удаление элемента из стека:

1. 1. ```python
   2. stack = Stack()
   3. stack.push(10)
   4. stack.push(20)
   5. top_element = stack.pop() # top_element = 20
   6. ```
2. Просмотр элемента на вершине стека:

1. 1. ```python
   2. stack = Stack()
   3. stack.push(10)
   4. stack.push(20)
   5. top_element = stack.peek() # top_element = 20
   6. ```

Применение

Операции push, pop и peek являются основными операциями, используемыми для работы со стеками, которые применяются в различных областях программирования, таких как:

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

Понимание операций push, pop и peek является важным для разработки эффективного и надежного программного обеспечения, использующего стеки.