Последовательности

В этом разделе мы рассмотрим АТД “последовательность”, его реализацию при помощи массивов и связанных списков, а также два специальных вида последовательностей: стеки, где элементы вставляются и удаляются только на одном конце последовательности, и очереди, когда элементы добавляются на одном конце последовательности, а удаляются на другом. Последовательности часто служат основой для реализации более сложных нелинейных структур данных.

1. АТД “последовательность элементов типа $T$”. Массивы и связанные списки

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

Обсудим хранение последовательностей в памяти. АТД “последовательность типа $T$” хранит множество элементов $a_1, a_2, \dots, a_n$ типа $T$, расположенных в определенном порядке (при $n = 0$ последовательность пуста).

Предположим, что для хранения всех элементов типа $T$ используется одно и то же число байт памяти. Тогда элементы последовательности можно расположить в памяти друг за другом:

Это массив элементов типа $T$ длины $n$, доступ к элементам которого выполняется по значению так называемого индекса массива. На абстрактном языке этот тип данных обозначается $T[0..n-1]$, а на языке программирования C++ массив целых чисел можно объявить как

int MAX_N = 100;
static int a[MAX_N];

Ключевое слово static указывает, что массив следует хранить в статической памяти. Вообще различают статическую, автоматическую (стековую) и динамическую память. Статическая память выделяется программе при ее запуске. Также выделяется специальный объем памяти, называемый стеком вызовов, в котором будут храниться все локальные переменные внутри функций и параметры функций. Динамическая память выделяется по запросу и обязательно лолжна освобождаться (в C++ оператором delete или delete[]).

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

В C++ тип “элемент списка” объявляется так:

struct ListElem {
   int data;
   ListElem* next;
};

то есть структура ListElem содержит указатель на структуру того же типа.

Переменная

ListElem* head;

хранит указатель на первый элемент списка либо нулевой указатель, если список пуст. Последний элемент списка содержит поле next = NULL.

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

Если заранее неизвестно, сколько памяти потребуется для массива, применяют динамические массивы, которые могут изменять свой размер в ходе выполнения программы. Для оптимизации процедуры копирования массива в новый выделенный блок памяти для хранения элементов массива оставляют место и увеличивают/уменьшают размер массива только вдвое – тогда при вставке $N$ элементов придется скопировать весь массив $\log N$ раз [Лудов; Скиена, с. 85].

Существует модификация структуры однонаправленного связанного списка, которая называется двунаправленным связанным списком. Отличие между ними в том, что каждый узел двунаправленного списка (кроме первого и последнего) содержит указатели на предыдущий и последующий узлы.

И наконец, если требуется хранить упорядоченную последовательность с операциями вставки и удаления элементов, то ни массив, ни список не подойдут: в массиве можно быстро найти нужный элемент, но нельзя быстро вставить или удалить элемент, а в списке не реализуем двоичный поиск, так как там нет быстрой операции доступа к произвольному элементу. Кстати, в массиве эта операция выполняется быстро, так как адреса элементов массива образуют арифметическую прогрессию. Для хранения модифицируемой упорядоченной последовательности подойдет структура данных “сбалансированное двоичное дерево поиска”, реализованное в стандартных контейнерах map, set, multimap, multiset. Динамический массив реализован в стандартном контейнере vector, а связанный список – в контейнере list. Вставка и удаление элементов осуществляется посредством специальных объектов – итераторов, например:

list<int> a;
list<int>::iterator it;
// ...
a.insert(it, 10);

Стек и очередь, о которых речь пойдет ниже, также реализованы в стандартных контейнерах stack и queue.

2. АТД “стек” и “очередь”

Стеком (stack) называют такую последовательность, в которой можно удалить только последний элемент, а новый элемент добавить только в его конец. Последний часто называют вершиной стека, поскольку стеки обычно изображают на рисунках в виде вертикального прямоугольника (по аналогии со стопкой тарелок, которую он напоминает). Кратко сформулировать принцип работы стека можно так: “последним вошел, первым вышел” (“last-in-first-out”, или LIFO), поскольку первым из стека всегда удаляется элемент, добавленный в него последним. Этим стек напоминает стопку тарелок, поскольку мы можем взять из нее только верхнюю тарелку, а новую тарелку — положить на верх стопки. Стеки широко применяются на практике, в частности, без них не обойтись при реализации рекурсивных алгоритмов.

Нетрудно реализовать стек емкостью не более $n$ элементов на базе массива $S[1..n]$. Наряду с массивом мы храним число ${\tt top}$, являющееся индексом последнего добавленного в стек элемента. Стек состоит из элементов $S[1..{\tt top}]$, где $S[1]$ – нижний элемент стека (“дно”), а $S[top]$ – верхний элемент, или вершина стека. Если ${\tt top} = 0$, то стек пуст. Если ${\tt top} = n$, то при попытке добавить элемент происходит переполнение (ошибка). Также ошибка возникает при попытке удалить элемент из пустого стека. Реализацию стека см. в [КЛРШ, с. 265], [Ахо, с. 60].

Под очередью (queue) понимается такая последовательность, элементы которой удаляются с одной стороны структуры (она называется головой (front)), а добавляются с другой (она называется хвостом (rear)). Первая операция называется удалением элемента из очереди (dequeue), а вторая — постановкой в очередь (enqueue). Таким образом, принцип работы очереди можно сформулировать так: “первым вошел, первым вышел” (“first-in-first-out”, или FIFO). Здесь прослеживается полная аналогия с очередью в магазине, которая образуется, если продавец медленно отпускает товар или наплыв покупателей слишком велик. Очереди также находят широкое практическое применение, в частности, в некоторых алгоритмах решения задач теории графов.

Покажем, как реализовать очередь, вмещающую не более чем $n-1$ элементов, на базе (циклического) массива $Q[1..n]$. Мы храним числа ${\tt head}$ – индекс головы очереди, и ${\tt tail}$ – индекс свободной ячейки, в которую будет помещен следующий добавляемый к очереди элемент. Очередь состоит из элементов массива, стоящих в местах с номерами ${\tt head}, {\tt head} + 1, \ldots {\tt tail} - 1$ (подразумевается, что массив свернут в кольцо: за $n$ следует 1). Первоначально имеем ${\tt head} = {\tt tail} = 1$. Если очередь пуста, попытка удалить элемент из нее ведет к ошибке; если ${\tt head} = {\tt tail} + 1$, то очередь полностью заполнена, и попытка добавить к ней элемент вызовет переполнение. Заметим, что прибавление 1 к индексу циклического массива следует реализовать так: $i \bmod n + 1$. Реализацию очереди см. в [КЛРШ, с. 197], [Ахо, с. 63].

В [Луридас, с. 19] приводится пример задачи, в которой требуется найти промежуток времени, в течение которого цена на акции была меньше текущей (то есть для каждого элемента последовательности как бы просмотреть ее в обратном порядке и остановиться на ближайшем элементе, когда цена была не меньше, чем сейчас). Для эффективного решения этой задачи использовался стек: все такие $a[j]$, для которых среди $a[1..i]$ найдется $a[k] \geq a[j]$, удаляются из стека, как только нашелся элемент, больший данного и находящийся в последовательности правее него. Инвариант: в стеке хранится невозрастающая подпоследовательность последовательности $a[1..i]$, то есть для каждого $a[j]$ удалены все предшествующие $a[k+1..j-1]$, для которых $a[.] < a[j]$. На каждом шаге алгоритм извлекает из стека все дни, в которые цена на акции была меньше текущей, тогда при добавлении текущего дня в стек инвариант сохранится. Каждый элемент последовательности $a[1..n]$ будет однажды добавлен в стек и однажды извлечен из стека, и других долгих операций алгоритм не требует. Следовательно, временная сложность алгоритма $O(n)$ – по числу элементов, добавленных в стек.

В [Топп, с. 194] стек применяется для вычисления выражения, записанного в обратной польской записи (постфиксный калькулятор).

3. АТД “упорядоченная последовательность элементов типа $T$”

В такой структуре данных необходимо поддерживать инвариант – упорядоченность последовательности по возрастанию (или по убыванию). В таком случае поиск заданного элемента в упорядоченном массиве можно произвести за время $O(\log n)$ при помощи метода деления массива пополам (двоичный поиск).

Дана упорядоченная по неубыванию последовательность $s[1], s[2], \ldots, s[n]$. Требуется найти множество ${i \colon s[i] = x}$.

Пространство поиска: $X = a..b$, $a < b$.

$c = \left[\dfrac{a+b}{2}\right] \; \Rightarrow \; c \leq b-1$

$X = Y \cup Z$, $Y \cap Z = \varnothing$,$\;\;$ $Y = a..c$, $Z = c+1..b$

Если $s[c] < x$, то $s[i] < x \; \,\forall\, i \in Y \; \Rightarrow \; X \leftarrow Z$.

Если $s[c] > x$, то $s[i] > x \; \,\forall\, i \in Z \; \Rightarrow \; X \leftarrow Y$.

Если $s[c] = x$, то пройти влево и вправо от $i = c$, пока $s[i] = x$.

Задачи

1. 3-сумма. [Принстон] Найти все тройки чисел из последовательности $a_i$ такие, что $a_i + a_j + a_k = 0$.

Задача решается перебором всех пар $i, j$, затем в отсортированном массиве $a_i$ двоичным поиском ищем число $-(a_i + a_j)$.

2. [Скиена, с. 120]

См. [Метельский].

3. (Хитрый член) Найти в последовательности ${a_i}_1^n \subset \mathbb N$ хитрый член $a_k$ такой, что \(\left|\sum_{\substack{i=1\\a_i<a_k}}^n a_i - \sum_{\substack{i=1\\a_i>a_k}}^n a_i \right| \to \min_k.\) Если хитрых $k$ несколько, вывести их все.

Решение. Для быстрого вычисления минимизируемого выражения при всех $k$ отсортируем массив $a_i$ (сохранив при этом индексы всех элементов в исходном массиве) и вычислим суммы $\displaystyle\sum_{\substack{i=1\a_i<a_k}}^n a_i$ и $\displaystyle\sum_{\substack{i=1\a_i>a_k}}^n a_i$ путем прохода по массиву в прямом и обратном порядке, для этого достаточно реализовать одну функцию и вызвать ее для исходного и перевернутого массива.

Тестирование решений

Литература

[Левитин] Левитин – Алгоритмы: введение в разработку и анализ (2006) – С. 54-58

[Ахо] Ахо, Хопкрофт, Ульман – Структуры данных и алгоритмы (2000) – С. 45-66

[КЛРШ] Кормен, Лейзерсон, Ривест, Штайн – Алгоритмы: Построение и анализ (2013) – С. 264-272

[Скиена] Скиена - Алгоритмы. Руководство по разработке (2011)

[Лудов] Лудов - Введение в структуры данных (2008)

[Луридас] Луридас – Алгоритмы для начинающих. Теория и практика для разработчика (2018)

[Топп] Топп, Форд – Структуры данных в С++ (1999)

[Метельский] Метельский - Структуры данных (2004)

[Принстон] Алгоритмы, часть 1. Онлайн курс от Принстонского университета на платформе Coursera