Теоретический минимум по Computer Science

Представьте стопку бумаги. Вы можете положить на нее еще один лист либо взять верхний. Лист, который добавили в стопку первым, всегда будет удален из стопки в последнюю очередь. Стек (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() — изменить порядок следования элементов на обратный.

Список — один из наиболее используемых АТД. Например, если вам нужно хранить ссылки на часто запрашиваемые файлы в системе, то список — идеальное решение: вы можете сортировать ссылки для отображения и удалять их, если к соответствующим файлам стали обращаться реже.