Просмотр исходного текста страницы Операции: push, pop, peek

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

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

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

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

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

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

== Pop (Удаление) ==

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

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

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

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

== Peek (Просмотр) ==

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

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

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

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

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

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

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

# '''Добавление элементов в стек''':

## ```python
## stack = Stack()
## stack.push(10)
## stack.push(20)
## stack.push(30)
## ```
# '''Удаление элемента из стека''':

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

## ```python
## stack = Stack()
## stack.push(10)
## stack.push(20)
## top_element = stack.peek()  # top_element = 20
## ```

== Применение ==

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

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

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