# Стек и очередь

![](ru/docs/assets/media/image142.jpeg){width="3.71873687664042in" height="4.8125in"}

1.  **Стек**

> *Стек* -- это линейная структура данных, которая следует логике «первый во- шел -- последний вышел».
>
> Стек можно сравнить со стопкой тарелок на столе: чтобы достать тарелку снизу, нужно сначала убрать все тарелки сверху. Заменив тарелки на элементы различных типов (например, целые числа, символы, объекты и т. д.), мы полу- чим структуру данных, называемую стеком.
>
> Верх стопки элементов называется вершиной стека, а низ -- основанием сте- ка, как показано на рис. 5.1. Операция добавления элемента на вершину стека называется вставка, а удаление элемента с вершины -- извлечение.

![](ru/docs/assets/media/image144.jpeg)Помещение

> Помещение
>
> Извлечение
>
> Извлечение
>
> **Рис. 5.1.** Правило «первый вошел -- последний вышел» для стека

### Основные операции со стеком

> Основные операции со стеком представлены в табл. 5.1, конкретные имена методов зависят от используемого языка программирования. Здесь в качестве примера используются распространенные имена push(), pop(), peek().
>
> **Таблица 5.1.** Эффективность операций со стеком

+-----------+--------------------------------------------------+---------------------------+
| **Метод** | > **Описание**                                   | > **Временная сложность** |
+==========:+==================================================+:=========================:+
| push()    | > Вставка элемента (добавление на вершину стека) | > *O*(1)                  |
+-----------+--------------------------------------------------+---------------------------+
| pop()     | > Извлечение элемента с вершины стека            | > *O*(1)                  |
+-----------+--------------------------------------------------+---------------------------+
| peek()    | > Доступ к элементу на вершине стека             | > *O*(1)                  |
+-----------+--------------------------------------------------+---------------------------+

> Обычно достаточно использовать классы стека, встроенные в язык програм- мирования. Однако в некоторых языках может не быть специального класса для стека. Тогда можно использовать массив или связный список в качестве стека, игнорируя операции, не связанные со стеком.
>
> \# === File: stack.py ===
>
> \# Инициализация стека.
>
> \# В Python нет встроенного класса стека, можно использовать list. stack: list\[int\] = \[\]
>
> \# Вставка элемента. stack.append(1) stack.append(3) stack.append(2) stack.append(5) stack.append(4)
>
> \# Доступ к элементу на вершине стека. peek: int = stack\[-1\]
>
> \# Извлечение элемента. pop: int = stack.pop()
>
> \# Получение длины стека. size: int = len(stack)
>
> \# Проверка на пустоту.
>
> is_empty: bool = len(stack) == 0

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

> Чтобы глубже понять механизм работы стека, попробуем реализовать соб- ственный класс стека.
>
> Стек следует принципу «первый вошел -- последний вышел», поэтому до- бавление и удаление элементов возможно только на вершине стека. Однако в массивах и связных списках элементы можно добавлять и удалять в любом месте, **поэтому стек можно рассматривать как ограниченный массив или связный список**. Иными словами, можно скрыть часть операций мас- сива или связного списка, чтобы их внешняя логика соответствовала харак- теристикам стека.

##### Реализация на основе связного списка

> При использовании для реализации стека связного списка можно считать головной узел связного списка вершиной стека, а хвостовой узел -- основа- нием стека.
>
> Для операции вставки элемента достаточно вставить его в начало связного списка, как показано на рис. 5.2. Этот метод вставки узла называется встав- ка в голову. Для операции извлечения элемента достаточно удалить головной узел из связного списка.
>
> ![](ru/docs/assets/media/image146.jpeg)

![](ru/docs/assets/media/image148.jpeg)![](ru/docs/assets/media/image150.jpeg)

> **Рис. 5.2.** Операции вставки и извлечения в стеке на основе связного списка
>
> Ниже приведен пример кода для реализации стека на основе связного списка.
>
> \# === File: linkedlist_stack.py === class LinkedListStack:
>
> \"\"\"Стек на основе связного списка.\"\"\"
>
> def init (self): \"\"\"Конструктор.\"\"\"
>
> self.\_peek: ListNode \| None = None self.\_size: int = 0
>
> def size(self) -\> int: \"\"\"Получение длины стека.\"\"\" return self.\_size
>
> def is_empty(self) -\> bool: \"\"\"Проверка стека на пустоту.\"\"\" return self.\_size == 0
>
> def push(self, val: int): \"\"\"Вставка элемента.\"\"\" node = ListNode(val) node.next = self.\_peek
>
> self.\_peek = node self.\_size += 1
>
> def pop(self) -\> int: \"\"\"Извлечение элемента.\"\"\" num = self.peek()
>
> self.\_peek = self.\_peek.next self.\_size -= 1
>
> return num
>
> def peek(self) -\> int:
>
> \"\"\"Доступ к элементу на вершине стека.\"\"\" if self.is_empty():
>
> raise IndexError(\"Стек пуст\") return self.\_peek.val
>
> def to_list(self) -\> list\[int\]: \"\"\"Преобразование в список для печати.\"\"\" arr = \[\]
>
> node = self.\_peek
>
> while node:
>
> arr.append(node.val) node = node.next
>
> arr.reverse() return arr

##### Реализация на основе массива

> При использовании для реализации стека массива можно считать конец мас- сива вершиной стека. Операции вставки и извлечения соответствуют добавле-
>
> нию и удалению элементов в конце массива, как показано на рис. 5.3. Времен- ная сложность этих операций составляет *O*(1).

![](ru/docs/assets/media/image152.jpeg)![](ru/docs/assets/media/image154.jpeg)![](ru/docs/assets/media/image156.jpeg)

> **Рис. 5.3.** Операции вставки и извлечения в стеке на основе массива
>
> Поскольку количество вставляемых элементов может постоянно увеличи- ваться, можно использовать динамический массив, чтобы не заниматься рас- ширением массива самостоятельно. Ниже приведен пример кода.
>
> \# === File: array_stack.py ===
>
> class ArrayStack:
>
> \"\"\"Стек на основе массива.\"\"\"
>
> def init (self): \"\"\"Конструктор.\"\"\" self.\_stack: list\[int\] = \[\]
>
> def size(self) -\> int: \"\"\"Получение длины стека.\"\"\" return len(self.\_stack)
>
> def is_empty(self) -\> bool: \"\"\"Проверка стека на пустоту.\"\"\" return self.size() == 0
>
> def push(self, item: int): \"\"\"Вставка элемента.\"\"\" self.\_stack.append(item)
>
> def pop(self) -\> int: \"\"\"Извлечение элемента.\"\"\" if self.is_empty():
>
> raise IndexError(\"Стек пуст\") return self.\_stack.pop()
>
> def peek(self) -\> int:
>
> \"\"\"Доступ к элементу на вершине стека.\"\"\" if self.is_empty():
>
> raise IndexError(\"Стек пуст\") return self.\_stack\[-1\]
>
> def to_list(self) -\> list\[int\]: \"\"\"Возврат списка для печати.\"\"\" return self.\_stack

### Сравнение двух реализаций

##### Поддерживаемые операции

> Обе реализации поддерживают все операции, определенные для стека. Реали- зация на основе массива дополнительно поддерживает произвольный доступ, но это выходит за рамки определения стека, поэтому обычно не используется.

##### Временная сложность

> В реализации на основе массива операции добавления и удаления элемента выполняются в заранее выделенной непрерывной памяти, что обеспечивает хорошую локальность кеша и, следовательно, высокую эффективность. Одна- ко, если при добавлении элемента превышается емкость массива, срабатыва- ет механизм расширения, что приводит к увеличению временной сложности данной операции до *O*(*n*).
>
> В реализации на основе связного списка расширение происходит очень гиб- ко, и не возникает проблемы снижения эффективности, как в случае расшире- ния массива. Однако операция добавления элемента требует инициализации объекта узла и изменения указателя, что делает ее относительно менее эффек- тивной. Тем не менее, если добавляемый элемент уже является объектом узла, можно избежать шага инициализации, что повысит эффективность.
>
> Таким образом, если элементы операций добавления и удаления являются примитивными типами данных, такими как int или double, можно сделать сле- дующие выводы:

1)  стек, реализованный на основе массива, при срабатывании механизма расширения теряет в эффективности, но, так как расширение является редкой операцией, средняя эффективность выше;

2)  стек, реализованный на основе связного списка, обеспечивает более ста- бильную эффективность.

##### Пространственная сложность

> При инициализации массива система выделяет для него начальную емкость, которая может превышать фактические потребности. Кроме того, механизм расширения обычно осуществляется с определенным коэффициентом (на- пример, в 2 раза), и емкость после расширения также может превышать фак- тические потребности. Поэтому **стек**, **реализованный на основе массива**, **может приводить к некоторым потерям пространства**.
>
> Однако, так как узлы связного списка требуют дополнительного хранения указателей, **занимаемое ими пространство сравнительно больше**.
>
> Таким образом, нельзя однозначно определить, какая реализация более эко- номична в плане памяти, необходимо анализировать конкретные ситуации.

### Типичные сценарии применения стека

- Возврат и переход вперед в браузере, отмена и повтор в программном обеспечении. Каждый раз, когда открывается новая веб-страница, бра- узер выполняет добавление предыдущей страницы в стек, что позволя- ет вернуться к ней с помощью операции возврата. Операция возврата фактически является выполнением удаления из стека. Если требуется поддержка как возврата, так и перехода вперед, необходимо использо- вать два стека.

- Управление памятью программы. Каждый раз при вызове функции си- стема добавляет на вершину стека фрейм для записи контекстной ин- формации функции. В рекурсивных функциях на этапе нисходящей ре-

> курсии постоянно выполняется добавление в стек, а на этапе восходящей рекурсии -- удаление из стека.

#### Очередь

> *Очередь* -- это линейная структура данных, следующая правилу «первый при- шел -- первый вышел». Как следует из названия, очередь моделирует реаль- ную очереди, когда новые элементы постоянно добавляются в конец очереди, а элементы в начале очереди покидают ее последовательно.
>
> Начало очереди называется голова, а конец -- хвост, см. рис. 5.4. Операция добавления элемента в конец очереди называется добавление в очередь, а уда- ление элемента из начала очереди -- удаление из очереди.

![](ru/docs/assets/media/image158.jpeg)

> **Рис. 5.4.** Правило очереди «первый пришел -- первый вышел»

### Основные операции с очередью

> Основные операции с очередью представлены в табл. 5.2. Следует отметить, что имена методов могут различаться в зависимости от языка программиро- вания. Здесь используются те же названия методов, что и для стека.

+-------------+---------------------------------------------------+---------------------------+
| > **Метод** | > **Описание**                                    | > **Временная сложность** |
+=============+===================================================+===========================+
| > push()    | > Добавление элемента в очередь, т. е. добавление | > *O*(1)                  |
+-------------+---------------------------------------------------+---------------------------+
| > pop()     | > Удаление элемента из головы очереди             | > *O*(1)                  |
+-------------+---------------------------------------------------+---------------------------+
| > peek()    | > Доступ к элементу в голове очереди              | > *O*(1)                  |
+-------------+---------------------------------------------------+---------------------------+

> элемента в конец очереди
>
> Можно использовать готовый класс очереди в языке программирования.
>
> \# === File: queue.py ===
>
> from collections import deque \# Инициализация очереди-
>
> \# В Python обычно используется класс двусторонней очереди deque.
>
> \# Хотя queue.Queue() является полноценным классом очереди, он не очень удобен, поэтому не рекомендуется к использованию.
>
> que: deque\[int\] = deque()
>
> \# Добавление элемента в очередь. que.append(1)
>
> que.append(3) que.append(2) que.append(5) que.append(4)
>
> \# Доступ к элементу в голове очереди. front: int = que\[0\]
>
> \# Удаление элемента из очереди. pop: int = que.popleft()
>
> \# Получение длины очереди. size: int = len(que)
>
> \# Проверка очереди на пустоту. is_empty: bool = len(que) == 0

### Реализация очереди

> Для реализации очереди требуется структура данных, которая позволяет до- бавлять элементы с одного конца и удалять с другого конца. И связный список, и массив соответствуют этим требованиям.

##### Реализация на основе связного списка

> Можно рассматривать головной узел и хвостовой узел связного списка как на- чало очереди и конец очереди соответственно. А также установить правило, что добавление узлов возможно только в конец очереди, а удаление узлов -- только из начала очереди, как показано на рис. 5.5.
>
> ![](ru/docs/assets/media/image160.jpeg)

![](ru/docs/assets/media/image162.jpeg)![](ru/docs/assets/media/image164.jpeg)

> **Рис. 5.5.** Операции добавления и удаления в очереди, реализованной на основе связного списка
>
> Ниже приведен код реализации очереди с использованием связного списка.
>
> \# === File: linkedlist_queue.py === class LinkedListQueue:
>
> \"\"\"Очередь на основе связного списка.\"\"\"
>
> def init (self): \"\"\"Конструктор.\"\"\"
>
> self.\_front: ListNode \| None = None \# Головной узел front. self.\_rear: ListNode \| None = None \# Хвостовой узел rear. self.\_size: int = 0
>
> def size(self) -\> int: \"\"\"Получение длины очереди.\"\"\" return self.\_size
>
> def is_empty(self) -\> bool: \"\"\"Проверка очереди на пустоту.\"\"\" return self.\_size == 0
>
> def push(self, num: int): \"\"\"Добавление в очередь.\"\"\"
>
> \# Добавление num после хвостового узла. node = ListNode(num)
>
> \# Если очередь пуста, то головной и хвостовой узлы указывают на этот
>
> узел.
>
> if self.\_front is None: self.\_front = node self.\_rear = node
>
> \# Если очередь не пуста, то узел добавляется после хвостового узла.
>
> else:
>
> self.\_rear.next = node self.\_rear = node
>
> self.\_size += 1
>
> def pop(self) -\> int: \"\"\"Удаление из очереди.\"\"\" num = self.peek()
>
> \# Удаление головного узла. self.\_front = self.\_front.next self.\_size -= 1
>
> return num
>
> def peek(self) -\> int:
>
> \"\"\"Доступ к элементу в начале очереди.\"\"\" if self.is_empty():
>
> raise IndexError(\"Очередь пуста\") return self.\_front.val
>
> def to_list(self) -\> list\[int\]: \"\"\"Преобразование в список для печати.\"\"\" queue = \[\]
>
> temp = self.\_front while temp:
>
> queue.append(temp.val) temp = temp.next
>
> return queue

##### Реализация на основе массива

> Удаление первого элемента в массиве имеет временную сложность *O*(*n*), что снижает эффективность операции удаления из очереди. Однако можно ис- пользовать следующий изящный метод, чтобы избежать этой проблемы.
>
> Можно использовать переменную front для указания на индекс первого эле- мента очереди и поддерживать переменную size для записи длины очереди. Определим переменную rear = front + size. Тогда rear будет указывать на сле- дующий элемент после хвоста очереди.
>
> В этой схеме **эффективный диапазон элементов в массиве составляет**

\[front, rear - 1\]. Методы реализации различных операций показаны на рис. 5.6.

- **Добавление в очередь**: присвоение нового элемента индексу rear и уве- личение size на 1.

- **Удаление из очереди**: достаточно увеличить front на 1 и уменьшить size

> на 1.
>
> Можно заметить, что добавление в очередь и удаление из нее требуют толь- ко двух операций, временная сложность каждой из которых равна *O*(1).

![](ru/docs/assets/media/image166.jpeg)

> **Рис. 5.6.** Операции добавления и удаления в очереди, реализованной на основе массива
>
> ![](ru/docs/assets/media/image168.jpeg)

![](ru/docs/assets/media/image170.jpeg)

> **Рис. 5.6.** *Окончание*
>
> Может возникнуть трудность: в процессе постоянного добавления и удале- ния положения front и rear перемещаются вправо, и **когда они достигают конца массива**, **дальнейшее перемещение становится невозможным**. Чтобы решить эту проблему, можно рассматривать массив как кольцевой мас- сив с соединенными концами.
>
> Для кольцевого массива необходимо, чтобы front или rear, пересекая конец массива, возвращались к его началу для продолжения обхода. Этот цикличе- ский процесс можно реализовать с помощью операции взятия остатка, при- мер кода приведен ниже.
>
> \# === File: array_queue.py ===
>
> class ArrayQueue:
>
> \"\"\"Очередь на основе кольцевого массива.\"\"\"
>
> def init (self, size: int): \"\"\"Конструктор.\"\"\"
>
> self.\_nums: list\[int\] = \[0\] \* size \# Массив для хранения
>
> \# элементов очереди. self.\_front: int = 0 \# Указатель на начало очереди,
>
> \# указывает на первый элемент. self.\_size: int = 0 \# Длина очереди.
>
> def capacity(self) -\> int: \"\"\"Получение емкости очереди.\"\"\" return len(self.\_nums)
>
> def size(self) -\> int: \"\"\"Получение длины очереди.\"\"\" return self.\_size
>
> def is_empty(self) -\> bool: \"\"\"Проверка, пуста ли очередь.\"\"\" return self.\_size == 0
>
> def push(self, num: int): \"\"\"Добавление в очередь.\"\"\"
>
> if self.\_size == self.capacity(): raise IndexError(\"Очередь полна\")
>
> \# Вычисление указателя на конец очереди, указывает на индекс конца + 1. \# Реализация возврата rear к началу массива после пересечения конца
>
> \# с помощью операции взятия остатка.
>
> rear: int = (self.\_front + self.\_size) % self.capacity() \# Добавление num в конец очереди.
>
> self.\_nums\[rear\] = num self.\_size += 1
>
> def pop(self) -\> int: \"\"\"Удаление из очереди.\"\"\" num: int = self.peek()
>
> \# Указатель на начало очереди перемещается на одну позицию вперед,
>
> \# если пересекает конец, возвращается к началу массива. self.\_front = (self.\_front + 1) % self.capacity() self.\_size -= 1
>
> return num
>
> def peek(self) -\> int:
>
> \"\"\"Доступ к элементу в начале очереди.\"\"\" if self.is_empty():
>
> raise IndexError(\"Очередь пуста\") return self.\_nums\[self.\_front\]
>
> def to_list(self) -\> list\[int\]: \"\"\"Возврат списка для печати.\"\"\" res = \[0\] \* self.size()
>
> j: int = self.\_front
>
> for i in range(self.size()):
>
> res\[i\] = self.\_nums\[(j % self.capacity())\] j += 1
>
> return res
>
> Реализованная выше очередь все еще имеет ограничение: ее длина неиз- менна. Однако эту проблему несложно решить, заменить массив на динамиче- ский с помощью механизма расширения. Заинтересованные читатели могут попробовать реализовать это самостоятельно.
>
> Выводы о сравнении двух реализаций аналогичны выводам о стеке, поэто- му здесь мы не будем повторяться.

### Типичные сценарии применения очереди

1.  Заказы на маркетплейсах. После оформления заказа покупателем он до- бавляется в очередь, и система затем обрабатывает заказы в порядке их поступления. В период распродаж за короткое время создается огром- ное количество заказов, и высокая нагрузка становится проблемой для разработчиков программного обеспечения.

2.  Различные списки задач. Любая ситуация, требующая реализации прин- ципа «первым пришел -- первым обслужен». Например, очередь заданий в принтере, очередь заказов в ресторане и т. д. Очередь в этих ситуациях эффективно поддерживает порядок обработки.

#### двусторонняя очередь

> В обычной очереди можно удалять только элементы из начала и добавлять элементы только в конец. *Двусторонняя очередь* предоставляет большую гиб- кость, позволяя выполнять операции добавления или удаления элементов как в начале, так и в конце, см. рис. 5.7.
>
> **Двусторонняя очередь**
>
> **(Deque)**
>
> **Голова очереди**
>
> Добавление элемента в голову
>
> ![](ru/docs/assets/media/image172.jpeg)push_first(**1**)
>
> Извлечение элемента с головы
>
> pop_first()
>
> **Извлечение из очереди**
>
> **Добавление в очередь**
>
> **Добавление в очередь**
>
> **Извлечение из очереди**
>
> **Хвост очереди**

Добавление Извлечение элемента элемента

> push_last(**4**)
>
> с хвоста
>
> pop_last()
>
> **Рис. 5.7.** Операции в двусторонней очереди

### Основные операции с двусторонней очередью

Обычные операции с двусторонней очередью представлены в табл. 5.3, кон- кретные имена методов зависят от используемого языка программирования.

> **Таблица 5.3.** Эффективность операций с двусторонней очередью

+----------------+----------------------------------------+---------------------------+
| > **Метод**    | > **Описание**                         | > **Временная сложность** |
+================+========================================+:=========================:+
| > push_first() | > Добавление элемента в начало очереди | > *O*(1)                  |
+----------------+----------------------------------------+---------------------------+
| > push_last()  | > Добавление элемента в конец очереди  | > *O*(1)                  |
+----------------+----------------------------------------+---------------------------+
| > pop_first()  | > Удаление элемента из начала очереди  | > *O*(1)                  |
+----------------+----------------------------------------+---------------------------+
| > pop_last()   | > Удаление элемента из конца очереди   | > *O*(1)                  |
+----------------+----------------------------------------+---------------------------+
| > peek_first() | > Доступ к элементу в начале очереди   | > *O*(1)                  |
+----------------+----------------------------------------+---------------------------+
| > peek_last()  | > Доступ к элементу в конце очереди    | > *O*(1)                  |
+----------------+----------------------------------------+---------------------------+

> Аналогично обычной очереди можно использовать уже реализованный в языке программирования класс двусторонней очереди.
>
> \# === File: deque.py ===
>
> from collections import deque
>
> \# Инициализация двусторонней очереди. deq: deque\[int\] = deque()
>
> \# Добавление элементов в очередь. deq.append(2) \# Добавление в конец. deq.append(5)
>
> deq.append(4)
>
> deq.appendleft(3) \# Добавление в начало. deq.appendleft(1)
>
> \# Доступ к элементам.
>
> front: int = deq\[0\] \# Элемент в начале очереди. rear: int = deq\[-1\] \# Элемент в конце очереди.
>
> \# Удаление элементов из очереди.
>
> pop_front: int = deq.popleft() \# Удаление из начала очереди. pop_rear: int = deq.pop() \# Удаление из конца очереди.
>
> \# Получение длины двусторонней очереди. size: int = len(deq)
>
> \# Проверка на пустоту двусторонней очереди is_empty: bool = len(deq) == 0

### Реализация двусторонней очереди\*

> Реализация двусторонней очереди схожа с обычной очередью -- можно вы- брать в качестве базовой структуры данных связный список или массив.

##### Реализация на основе двусвязного списка

> В предыдущем разделе для реализации очереди использовался обычный од- носвязный список, так как он позволяет удобно удалять головной узел (соот- ветствует операции удаления из очереди) и добавлять новый узел после хво- стового узла (соответствует операции добавления в очередь).
>
> Для двусторонней очереди операции добавления и удаления можно выпол- нять как в начале, так и в конце. Иными словами, двусторонняя очередь требу- ет реализации операций в симметричном направлении. Для этого в качестве базовой структуры данных двусторонней очереди удобно использовать дву- связный список.
>
> Головной и хвостовой узлы двусвязного списка рассматриваются как начало и конец двусторонней очереди. При этом реализуется возможность добавле- ния и удаления узлов с обеих сторон, см. рис. 5.8.
>
> ![](ru/docs/assets/media/image174.jpeg)

![](ru/docs/assets/media/image176.jpeg)![](ru/docs/assets/media/image178.jpeg)

> **Рис. 5.8.** Операции добавления и удаления в двусторонней очереди на основе связного списка
>
> ![](ru/docs/assets/media/image180.jpeg)

![](ru/docs/assets/media/image182.jpeg)

> **Рис. 5.8.** *Окончание*
>
> Ниже представлен код реализации.
>
> \# === File: linkedlist_deque.py === class ListNode:
>
> \"\"\" Узел двусвязного списка.\"\"\"
>
> def init (self, val: int): \"\"\" Конструктор.\"\"\" self.val: int = val
>
> self.next: ListNode \| None = None \# Ссылка на следующий узел. self.prev: ListNode \| None = None \# Ссылка на предыдущий узел.
>
> class LinkedListDeque:
>
> \"\"\" Двусторонняя очередь на основе двусвязного списка.\"\"\"
>
> def init (self):
>
> \"\"\" Конструктор.\"\"\"
>
> self.\_front: ListNode \| None = None \# Головной узел front. self.\_rear: ListNode \| None = None \# Хвостовой узел rear. self.\_size: int = 0 \# Длина двусторонней очереди.
>
> def size(self) -\> int:
>
> \"\"\" Получение длины двусторонней очереди.\"\"\" return self.\_size
>
> def is_empty(self) -\> bool:
>
> \"\"\" Проверка на пустоту двусторонней очереди.\"\"\" return self.\_size == 0
>
> def push(self, num: int, is_front: bool): \"\"\" Операция добавления в очередь.\"\"\" node = ListNode(num)
>
> \# Если список пуст, front и rear указывают на node. if self.is_empty():
>
> self.\_front = self.\_rear = node \# Добавление в начало очереди.
>
> elif is_front:
>
> \# Добавление node в начало списка. self.\_front.prev = node
>
> node.next = self.\_front
>
> self.\_front = node \# Обновление головного узла. \# Добавление в конец очереди.
>
> else:
>
> \# Добавление node в конец списка. self.\_rear.next = node
>
> node.prev = self.\_rear
>
> self.\_rear = node \# Обновление хвостового узла. self.\_size += 1 \# Обновление длины очереди.
>
> def push_first(self, num: int):
>
> \"\"\" Добавление в начало очереди.\"\"\" self.push(num, True)
>
> def push_last(self, num: int):
>
> \"\"\" Добавление в конец очереди.\"\"\" self.push(num, False)
>
> def pop(self, is_front: bool) -\> int: \"\"\" Операция удаления из очереди.\"\"\" if self.is_empty():
>
> raise IndexError(\" Двусторонняя очередь пуста.\") \# Удаление из начала очереди.
>
> if is_front:
>
> val: int = self.\_front.val \# Временное сохранение значения
>
> \# головного узла.
>
> \# Удаление головного узла.
>
> fnext: ListNode \| None = self.\_front.next if fnext != None:
>
> fnext.prev = None self.\_front.next = None
>
> self.\_front = fnext \# Обновление головного узла. \# Удаление из конца очереди.
>
> else:
>
> val: int = self.\_rear.val \# Временное сохранение значения
>
> \# хвостового узла. \# Удаление хвостового узла.
>
> rprev: ListNode \| None = self.\_rear.prev if rprev != None:
>
> rprev.next = None self.\_rear.prev = None
>
> self.\_rear = rprev \# Обновление хвостового узла. self.\_size -= 1 \# Обновление длины очереди.
>
> return val
>
> def pop_first(self) -\> int:
>
> \"\"\" Удаление из начала очереди.\"\"\" return self.pop(True)
>
> def pop_last(self) -\> int:
>
> \"\"\" Удаление из конца очереди.\"\"\" return self.pop(False)
>
> def peek_first(self) -\> int:
>
> \"\"\" Доступ к элементу в начале очереди.\"\"\" if self.is_empty():
>
> raise IndexError(\" Двусторонняя очередь пуста.\") return self.\_front.val
>
> def peek_last(self) -\> int:
>
> \"\"\" Доступ к элементу в конце очереди.\"\"\" if self.is_empty():
>
> raise IndexError(\" Двусторонняя очередь пуста.\") return self.\_rear.val
>
> def to_array(self) -\> list\[int\]:
>
> \"\"\" Возврат массива для печати.\"\"\" node = self.\_front
>
> res = \[0\] \* self.size()
>
> for i in range(self.size()): res\[i\] = node.val
>
> node = node.next return res

##### Реализация на основе массива

> Аналогично реализации обычной очереди для двусторонней очереди можно использовать кольцевой массив, как показано на рис. 5.9.

![](ru/docs/assets/media/image184.jpeg)![](ru/docs/assets/media/image186.jpeg)

> **Рис. 5.9.** Операции добавления и удаления в двусторонней очереди на основе массива
>
> ![](ru/docs/assets/media/image188.jpeg)

![](ru/docs/assets/media/image190.jpeg)

> **Рис. 5.9.** *Продолжение*
>
> ![](ru/docs/assets/media/image192.jpeg)
>
> **Рис. 5.9.** *Окончание*
>
> По сравнению с реализацией обычной очереди необходимо лишь добавить методы для добавления в начало очереди и для удаления из конца очереди.
>
> \# === File: array_deque.py === class ArrayDeque:
>
> \"\"\" Двусторонняя очередь на основе кольцевого массива.\"\"\"
>
> def init (self, capacity: int): \"\"\" Конструктор.\"\"\"
>
> self.\_nums: list\[int\] = \[0\] \* capacity self.\_front: int = 0
>
> self.\_size: int = 0
>
> def capacity(self) -\> int:
>
> \"\"\" Получение емкости двусторонней очереди.\"\"\" return len(self.\_nums)
>
> def size(self) -\> int:
>
> \"\"\" Получение длины двусторонней очереди.\"\"\" return self.\_size
>
> def is_empty(self) -\> bool:
>
> \"\"\" Проверка, пуста ли двусторонняя очередь.\"\"\" return self.\_size == 0
>
> def index(self, i: int) -\> int:
>
> \"\"\" Вычисление индекса кольцевого массива.\"\"\"
>
> \# Реализация соединения начала и конца массива с помощью \# операции взятия остатка.
>
> \# Когда i превышает конец массива, возвращается к началу. \# Когда i превышает начало массива, возвращается к концу. return (i + self.capacity()) % self.capacity()
>
> def push_first(self, num: int):
>
> \"\"\" Добавление в начало очереди.\"\"\" if self.\_size == self.capacity():
>
> print(\" Двусторонняя очередь полна.\") return
>
> \# Перемещение указателя начала очереди на одну позицию влево.
>
> \# Реализация возврата front к концу массива после превышения начала. self.\_front = self.index(self.\_front - 1)
>
> \# Добавление num в начало очереди. self.\_nums\[self.\_front\] = num self.\_size += 1
>
> def push_last(self, num: int):
>
> \"\"\" Добавление в конец очереди.\"\"\" if self.\_size == self.capacity():
>
> print(\" Двусторонняя очередь полна.\") return
>
> \# Вычисление указателя конца очереди, указывает на индекс конца + 1. rear = self.index(self.\_front + self.\_size)
>
> \# Добавление num в конец очереди. self.\_nums\[rear\] = num
>
> self.\_size += 1
>
> def pop_first(self) -\> int:
>
> \"\"\" Удаление из начала очереди.\"\"\" num = self.peek_first()
>
> \# Перемещение указателя начала очереди на одну позицию вправо. self.\_front = self.index(self.\_front + 1)
>
> self.\_size -= 1 return num
>
> def pop_last(self) -\> int:
>
> \"\"\" Удаление из конца очереди.\"\"\" num = self.peek_last()
>
> self.\_size -= 1 return num
>
> def peek_first(self) -\> int:
>
> \"\"\" Доступ к элементу в начале очереди.\"\"\"
>
> if self.is_empty():
>
> raise IndexError(\" Двусторонняя очередь пуста.\") return self.\_nums\[self.\_front\]
>
> def peek_last(self) -\> int:
>
> \"\"\" Доступ к элементу в конце очереди.\"\"\" if self.is_empty():
>
> raise IndexError(\" Двусторонняя очередь пуста.\") \# Вычисление индекса последнего элемента.
>
> last = self.index(self.\_front + self.\_size - 1) return self.\_nums\[last\]
>
> def to_array(self) -\> list\[int\]:
>
> \"\"\" Возврат массива для печати.\"\"\"
>
> \# Преобразование только элементов в пределах действительной длины. res = \[\]
>
> for i in range(self.\_size): res.append(self.\_nums\[self.index(self.\_front + i)\])
>
> return res

### Сценарии применения двусторонней очереди

> Двусторонняя очередь сочетает в себе логику стека и очереди. **Поэтому она применима для всех сценариев этих двух структур**, **одновременно пре- доставляя большую степень свободы**.
>
> Известно, что функция отмены в программном обеспечении обычно реа- лизуется с помощью стека: система помещает каждое изменение в стек с по- мощью операции push, а затем выполняет отмену с помощью операции pop. Однако, учитывая ограничения системных ресурсов, программное обеспече- ние обычно ограничивает количество шагов отмены (например, позволяет со- хранить только 50 шагов). Когда длина стека превышает 50, программе нужно выполнить удаление внизу стека (в начале очереди). **Но стек не может реа- лизовать эту функцию**, **и в этом случае необходимо использовать дву- стороннюю очередь вместо стека**. Следует отметить, что основная логика отмены по-прежнему следует принципу стека «первым пришел -- последним вышел», просто двусторонняя очередь позволяет более гибко реализовать не- которые дополнительные логические операции.

#### резюме

##### Ключевые моменты

- Стек -- это структура данных, которая следует принципу «первым при- шел -- последним вышел» и может быть реализована с помощью массива или связного списка.

- В плане временной сложности реализация стека с использованием мас- сива обладает более высокой средней эффективностью, но во время рас- ширения сложность времени выполнения одной операции добавления

> 5.4. Резюме ❖ **145**
>
> [в]{.smallcaps} стек может ухудшиться до *O*(*n*). В сравнении с этим реализация стека с использованием связного списка обладает более стабильной эффек- тивностью.

- В плане пространственной сложности реализация стека с использовани- ем массива может привести к определенной степени потери простран- ства. Однако следует отметить, что память, занимаемая узлами связного списка, больше, чем у элементов массива.

- Очередь -- это структура данных, которая следует принципу «первым пришел -- первым вышел» и также может быть реализована с помощью массива или связного списка. В плане временной и пространственной сложности выводы по очереди схожи с выводами по стеку.

- Двусторонняя очередь -- это очередь с большей степенью свободы, она позволяет добавлять и удалять элементы с обоих концов.

##### Вопросы и ответы

> **Вопрос**. Реализована ли функция «вперед-назад» в браузере с помощью дву- стороннего связного списка?
>
> **Ответ**. Функция «вперед-назад» в браузере, по сути, является типичным проявлением стека. Когда пользователь посещает новую страницу, она добав- ляется на вершину стека. Когда пользователь нажимает кнопку **Назад**, страни- ца извлекается с вершины стека. Использование двусторонней очереди позво- ляет удобно реализовать некоторые дополнительные операции, что упомина- ется в разделе «Двусторонняя очередь».
>
> **Вопрос**. Нужно ли освобождать память узла после извлечения из стека?
>
> **Ответ**. Если в дальнейшем необходимо использовать извлеченный узел, то освобождать память не нужно. Если узел больше не нужен, в языках Java и Python имеется автоматический механизм сборки мусора, поэтому ручное освобожде- ние памяти не требуется. В C и C++ необходимо освобождать память вручную.
>
> **Вопрос**. Двусторонняя очередь похожа на два стека, соединенных вместе.
>
> Каково ее назначение?
>
> **Ответ**. Двусторонняя очередь подобна комбинации стека и очереди или двум стекам, соединенным вместе. Она представляет собой логику стека и очереди, поэтому подходит для всех сценариев их применения, но является более гибкой. **Вопрос**. Как конкретно реализуются функции отмены и повтора операций?
>
> **Ответ**. Используются два стека: стек A для отмены, стек B для повтора.

1.  Когда пользователь выполняет операцию, она помещается в стек A, а стек

> B очищается.

2.  Когда пользователь выполняет отмену, из стека A извлекается последняя операция и помещается в стек B.

3.  Когда пользователь выполняет повтор, из стека B извлекается последняя операция и помещается в стек A.

> Глава 6