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

Операции enqueue и dequeue являются основными операциями, выполняемыми над очередью (queue), структурой данных, основанной на принципе FIFO (First In, First Out).

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

'''Enqueue''' — это операция добавления нового элемента в конец очереди (rear).

# '''Описание''': Добавляет элемент в конец очереди, увеличивая ее размер на единицу.
# '''Параметры''': Элемент, который нужно добавить в очередь.
# '''Возвращаемое значение''': Отсутствует (в большинстве реализаций).
# '''Временная сложность''': $O(1)$ (константное время), при использовании связного списка или циклического массива. При использовании линейного массива может потребоваться сдвиг всех элементов, что занимает $O(n)$.
# '''Пример реализации (Python, связный список)''':
## ```python
## class Node:
##     def __init__(self, data):
##         self.data = data
##         self.next = None
##
## class Queue:
##     def __init__(self):
##         self.head = None
##         self.tail = None
##
##     def enqueue(self, item):
##         new_node = Node(item)
##         if self.tail is None:
##             self.head = new_node
##             self.tail = new_node
##         else:
##             self.tail.next = new_node
##             self.tail = new_node
## ```

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

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

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

'''Dequeue''' — это операция удаления элемента из начала очереди (front).

# '''Описание''': Удаляет элемент из начала очереди, уменьшая ее размер на единицу.
# '''Параметры''': Отсутствуют.
# '''Возвращаемое значение''': Элемент, удаленный из начала очереди.
# '''Временная сложность''': $O(1)$ (константное время), при использовании связного списка или циклического массива. При использовании линейного массива может потребоваться сдвиг всех элементов, что занимает $O(n)$.
# '''Пример реализации (Python, связный список)''':
## ```python
## class Queue:
##     def __init__(self):
##         self.head = None
##         self.tail = None
##
##     def dequeue(self):
##         if self.head is None:
##             return None  # Или выбросить исключение
##         item = self.head.data
##         self.head = self.head.next
##         if self.head is None:
##             self.tail = None
##         return item
## ```

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

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

== Сравнение операций enqueue и dequeue ==

{| class="wikitable"
|-
! Операция
! Описание
! Расположение
! Временная сложность
! Особенности
|-
! Enqueue
| Добавление элемента в очередь
| Конец очереди (rear)
| $O(1)$ (связный список, циклический массив), $O(n)$ (линейный массив)
| Переполнение очереди
|-
! Dequeue
| Удаление элемента из очереди
| Начало очереди (front)
| $O(1)$ (связный список, циклический массив), $O(n)$ (линейный массив)
| Опустошение очереди
|}

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

# '''Добавление элементов в очередь''':

## ```python
## queue = Queue()
## queue.enqueue(10)
## queue.enqueue(20)
## queue.enqueue(30)
## ```
# '''Удаление элемента из очереди''':

## ```python
## queue = Queue()
## queue.enqueue(10)
## queue.enqueue(20)
## first_element = queue.dequeue()  # first_element = 10
## ```

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

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

# Планирование задач.
# Обработка запросов.
# Моделирование.
# Поиск в ширину.
# Буферизация данных.
# Системы обмена сообщениями.

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