Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица
Страница 2. Структура данных \"Очередь\"

Структура данных "Очередь": обработка по принципу "Первым пришел, первым обслужен"

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

• Обработка по принципу "Первым пришел, первым обслужен" (First come, first served; FCFS)
• Обработка, основанная на приоритетах

С обработкой запросов по принципу FCFS мы сталкиваемся в магазине, банке и т.п. Люди, ожидающие момента, когда их обслужат, становятся в очередь. Те, кто стоят перед вами, обслуживаются раньше вас, а те, кто стоят после, будут обслужены позднее вас. При приоритезированной обработке те, у кого приоритет больше будут обслужены перед теми, у кого приоритет меньше. Например, служба скорой помощи в больнице обслужит сначала пациентов с потенциально смертельным ранением, а не тех пациентов, состояние которых менее критично, независимо от того, кто прибыл первым.

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

Возможное решение - использовать ArrayList и целочисленную переменную nextJobPos, в которой будет храниться индекс следующей задачи, которая должна быть отправлена на обработку. С приходом нового задания мы попросту будем использовать метод Add() для добавления задачи в конец ArrayList-а. Как только мы готовы обработать очередную задачу, находящуюся в буфере, мы берем это задание из nextJobPos-ого элемента ArrayList-а и увеличиваем nextJobPos на 1. Следующая программа описывает этот алгоритм:

using System;
using System.Collections;
public class JobProcessing
{
 private static ArrayList jobs = new ArrayList();
 private static int nextJobPos = 0;
 public static void AddJob(string jobName)
 {
 jobs.Add(jobName);
 }
 public static string GetNextJob()
 {
 if (nextJobPos > jobs.Count - 1)
 return "NO JOBS IN BUFFER";
 else
 {
 string jobName = (string) jobs[nextJobPos];
 nextJobPos++;
 return jobName;
 }
 }
 public static void Main()
 { 
 AddJob("1");
 AddJob("2");
 Console.WriteLine(GetNextJob());
 AddJob("3");
 Console.WriteLine(GetNextJob());
 Console.WriteLine(GetNextJob());
 Console.WriteLine(GetNextJob());
 Console.WriteLine(GetNextJob());
 AddJob("4");
 AddJob("5");
 Console.WriteLine(GetNextJob());
 }
}

Вывод программы таков:

1
2
3
NO JOBS IN BUFFER
NO JOBS IN BUFFER
4

Притом, что такой подход исключительно прост и прямолинеен, он ужасно неэффективен. Для новичков поясняем: ArrayList будет неограниченно расти с каждым добавлением новой задачи в буфер. Это будет происходить даже в том случае, когда запросы обрабатываются немедленно после помещения их в буфер. Рассмотрим пример, когда каждую секунду в буфер добавляется задача и из буфера удаляется задача. Это означает, что раз в секунду вызывается метод AddJob(), который в свою очередь вызывает метод Add() ArrayList-а. При непрерывном вызове метода Add(), размер внутреннего массива ArrayList-а постоянно удваивается по мере необходимости. После 5 минут (300 секунд) размер внутреннего массива ArrayList-а достигнет 512 элементов, несмотря на то, что в буфере никогда не находилось более 1 задачи одновременно! Размер массива будет, конечно же, продолжать расти в процессе работы программы и с приходом новых задач.

Причина того, что ArrayList разрастается до таких невероятных размеров в том, что память буфера, использовавшаяся для старых запросов, не используется повторно. Ведь когда мы добавляем первое задание в буфер, а потом удаляем его из буфера после отправки на обработку, первая позиция ArrayList-а может быть использована повторно для размещения в ней нового запроса. Рассмотрим процесс диспетчеризации задач, представленный в программе, написанной выше. После исполнения первых двух строк -AddJob("1") и AddJob("2")-содержимое ArrayList-а будет выглядеть так (рис. 1):

Рисунок 1. ArrayList после исполнения первых двух строчек кода

Заметьте, что ArrayList на этот момент содержит 16 элементов потому, что при создании ArrayList-а по умолчанию создается внутренний массив из 16 элементов типа object. После этого вызывается метод GetNextJob(), который удаляет первую задачу из буфера. В результате мы получаем ситуацию, показанную на рис. 2.

Рисунок 2. Программа после вызова метода GetNextJob()

Когда выполняется AddJob("3"),нам нужно добавить очередную задачу в буфер. Очевидно, что первый элемент ArrayList-а (с индексом 0) можно использовать повторно. Изначально, возможно, и есть некий смысл поместить третью задачу в нулевой элемент. Однако, мы вынуждены отвергнуть такой подход, рассмотрев, что же получится если после выполнения AddJob("3") мы вызовем AddJob("4"), а затем два вызова метода GetNextJob(). Если бы мы поместили третью задачу по нулевому индексу, а четвертую - в элемент с индексом 2, мы бы получили следующую неприятную ситуацию, показанную на рисунке 3.

Рисунок 3. Что получится при помещении третьей задачи по нулевому индексу

Теперь если мы вызовем GetNextJob() из буфера будет удалена вторая задача, значение nextJobPos будет увеличено на 1 и станет равным 2. Таким образом, при повторном вызове GetNextJob(), из буфера будет удалена четвертая задача, которая в результате будет обработана раньше третьей. Мы получаем, что нарушается порядок "Первым пришел, первым обслужен", который мы договорились поддерживать.

Суть наших проблем состоит в том, что ArrayList представляет собой список задач в линейном порядке. Это означает, что мы всегда должны добавлять новые задачи в буфер правее старых задач, чтобы гарантировать корректный порядок обработки запросов. Каждый раз, когда мы натыкаемся на конец ArrayList-а, его размер удваивается даже в том случае, если существуют пустые элементы, образовавшиеся из-за вызовов GetNextJob().

Чтобы исправить это, нам придется сделать ArrayList циклическим (сircular). Циклический массив не имеет определенного начала или конца. Точнее, конец и начало массива хранятся в определенных переменных. Графическое представление циклического массива показано на Рисунке 4.

Рисунок 4. Пример циклического массива

При работе с циклическим массивом, метод AddJob() помещает новую задачу в элемент с индексом endPos, а затем "инкрементирует" endPos. Метод GetNextJob() забирает задачу из элемента с индексом startPos, присваивает элементу с индексом startPos значение null, а затем "инкрементирует" startPos. Слово "инкрементировать" (increment) значит увеличивать на единицу. Оно было помещено в кавычки, потому что в данном случае под "инкрементацией" подразумеваются чуть более сложные действия, нежели простое прибавление единицы к целочисленному значению переменной. Чтобы понять, почему мы не можем просто взять и прибавить 1, рассмотрим случай, когда endPos равняется 15. Если мы прибавим к endPos единицу, значение endPos станет равным 16. При следующем вызове AddJob() мы попытаемся получить доступ к элементу с номером 16, что приведет к исключению IndexOutOfRangeException.

Вместо этого, когда endPos равен 15, нам хотелось бы "инкрементировать" endPos так, чтобы его значение стало равным 0. Мы можем сделать это, написав функцию increment(variable), которая бы проверяла, что значение фактического входного параметра равно размеру массива, и в этом случае сбрасывала это значение в 0. Альтернативный вариант - это прибавлять единицу, однако сложение выполнять по модулю размера массива. В этом случае, код функции increment() будет таким:

int increment(int variable)
{
 return (variable + 1) % theArray.Length;
}

Примечание Бинарный оператор % в выражении x % y вычисляет остаток от деления x на y. Остаток всегда будет в пределах между 0 и y - 1.

Этот подход отлично работает, если наш буфер никогда не будет содержать более 16 элементов. А что будет, если мы захотим добавить новую задачу в буфер, в котором уже есть 16 задач? Like Подобно методу Add() ArrayList-a, нам придется соответствующим образом изменить размер циклического массива, например, удвоив размер массива.