Стек
Представьте стопку бумаги. Вы можете положить на нее еще один лист либо взять верхний. Лист, который добавили в стопку первым, всегда будет удален из стопки в последнюю очередь. Стек (stack) представляет такую стопку и позволяет работать только с ее верхним элементом. Элемент на вершине стека — это всегда элемент, который был добавлен последним. Реализация стека должна обеспечивать по крайней мере две операции:
• push(e) — добавить элемент e на вершину стека;
• pop() — получить и удалить элемент с вершины стека.
Более совершенные разновидности стеков могут поддерживать дополнительные операции: проверку наличия в стеке элементов или получение их текущего количества.
Такая обработка данных известна под названием LIFO (Last-In, First-Out, «последним пришел, первым вышел»); мы можем удалить только верхний элемент, который был добавлен последним. Стек — это важный тип данных, он встречается во многих алгоритмах. Для реализации функции «Отменить ввод» в текстовом редакторе каждая вносимая вами правка помещается в стек. Если вы хотите ее отменить, то текстовый редактор выталкивает правку из стека и возвращается к предыдущему состоянию.
Чтобы реализовать поиск с возвратом (см. соответствующий раздел главы 3) без рекурсии, вы должны запоминать в стеке последовательность вариантов, которые привели вас к текущей точке. Обследуя новый узел, мы помещаем ссылку на него в стек. Чтобы вернуться на шаг назад, мы просто выталкиваем (pop()) последний элемент из стека, заодно получая ссылку на предыдущее состояние.
Очередь
Очередь (queue) — это полная противоположность стека. Она тоже позволяет сохранять и извлекать данные, но элементы всегда берутся из начала очереди — тот, который находился в очереди дольше всего. Звучит пугающе? В действительности это то же самое, что и реальная очередь из людей, стоящих у раздачи в столовой! Вот основные операции с очередями:
• enqueue(e) — добавить элемент e в конец очереди;
• dequeue() — удалить элемент из начала очереди.
Очередь работает по принципу организации данных FIFO (First-In, FirstOut, «первый пришел, первый вышел»), потому что первый помещенный в очередь элемент всегда покидает ее первым.
Очереди используются во многих вычислительных сценариях. Если вы реализуете онлайновую службу доставки пиццы, то вы, скорее всего, будете хранить заказы в очереди. В качестве мысленного эксперимента подумайте, что вышло бы, если б ваша пиццерия обслуживала заказы с использованием стека вместо очереди.
Очередь с приоритетом
Очередь с приоритетом (priority queue) аналогична обычной очереди с той лишь разницей, что помещенным в нее элементам присваивается приоритет. Люди, ожидающие медицинской помощи в больнице, — вот реальный пример очереди с приоритетом. Экстренные случаи получают высший приоритет и переходят непосредственно в начало очереди, тогда как незначительные добавляются в ее конец. Основные операции, реализуемые очередью с приоритетом, таковы:
• enqueue(e, p) — добавить элемент e в очередь согласно уровню приоритетности p;
• dequeue() — вернуть элемент, расположенный в начале очереди, и удалить его.
В компьютере, как правило, много рабочих процессов — и всего один или несколько ЦП, предназначенных для их выполнения. Операционная система ставит все процессы, ожидающие выполнения, в очередь с приоритетом. Каждый процесс получает свой уровень приоритетности. Операционная система исключает процесс из очереди и позволяет ему некоторое время поработать. Позднее, если процесс не завершился, он снова ставится в очередь. Операционная система раз за разом повторяет эту процедуру.
Некоторые процессы более важны и безотлагательно получают процессорное время, другие ожидают в очереди дольше. Процесс, который получает ввод с клавиатуры, как правило, получает самый высокий приоритет — ведь если компьютер не реагирует на нажатия клавиш, то пользователь может подумать, что он завис, и попробует сделать «холодный» перезапуск, что всегда вредно.
Список
При работе с группами элементов иногда требуется гибкость. Например, может понадобиться переупорядочить элементы или извлекать, вставлять и удалять их в произвольном порядке. В этих случаях удобно использовать список (list). Чаще всего АТД «Список» поддерживает следующие операции:
• insert(n, e) — вставить элемент e в позицию n;
• remove(n) — удалить элемент, находящийся в позиции n;
• get(n) — получить элемент, находящийся в позиции n;
• sort() — отсортировать элементы;
• slice(start, end) — вернуть фрагмент списка, начинающийся с позиции start и заканчивающийся в позиции end;
• reverse() — изменить порядок следования элементов на обратный.
Список — один из наиболее используемых АТД. Например, если вам нужно хранить ссылки на часто запрашиваемые файлы в системе, то список — идеальное решение: вы можете сортировать ссылки для отображения и удалять их, если к соответствующим файлам стали обращаться реже.
Стеку и очереди следует отдавать предпочтение, когда гибкость, предоставляемая списком, не нужна. Использование более простого АТД гарантирует, что данные будут обрабатываться строгим и предсказуемым образом (по принципу FIFO или LIFO). Это также делает код яснее: зная, что переменная представляет собой стек, легче понять характер потоков данных на входе и выходе.
Сортированный список
Сортированный список (sorted list) бывает полезен, когда нужна постоянная упорядоченность элементов. В этих случаях вместо поиска правильной позиции перед каждой вставкой в список (и периодической сортировки его вручную) мы используем сортированный список. Что бы в него ни помещали, элементы всегда будут стоять по порядку. Ни одна из операций этого АТД не позволяет переупорядочить его элементы. Сортированный список поддерживает меньше операций, чем обычный:
• insert(e) — вставить элемент e в автоматически определяемую позицию в списке;
• delete(n) — удалить элемент, находящийся в позиции n;
• get(n): получить элемент, находящийся в позиции n.
Словарь (map) используется для хранения соответствий между двумя объектами: ключом key и значением value. Вы можете осуществить поиск по ключу и получить связанное с ним значение. Словарь хорошо подходит, например, для хранения идентификационных номеров пользователей в качестве ключей и полных имен в качестве значений. Такой словарь по заданному идентификационному номеру вернет связанное с ним имя. Существуют следующие операции для словарей:
