Определение 4.3 Очередь FIFO - это А ТД, который содержит две базовых операции: вставить (put - занести) новый элемент и удалить (get - извлечь) элемент, который был вставлен раньше всех остальных.

Программа 4.13 является интерфейсом для АТД Очередь FIFO . Этот интерфейс отличается от интерфейса стека, рассмотренного в разделе 4.2, только спецификациями - для компилятора два интерфейса совершенно идентичны! Это подчеркивает тот факт, что сама абстракция, которую программисты обычно не определяют формально, является существенным компонентом абстрактного типа данных. Для больших приложений, которые могут содержать десятки АТД, проблема их точного определения является критически важной. В настоящей книге мы работаем с АТД, представляющими важнейшие понятия, которые определяются в тексте, но не при помощи формальных языков (разве что через конкретные реализации). Чтобы понять природу абстрактных типов данных, потребуется рассмотреть примеры их использования и конкретные реализации.

На рис. 4.6 показано, как очередь FIFO изменяется в ходе ряда последовательных операций извлечь и занести. Каждая операция извлечь уменьшает размер очереди на 1, а каждая операция занести увеличивает размер очереди на 1. Элементы очереди перечислены на рисунке в порядке их занесения в очередь, поэтому ясно, что первый элемент списка - это тот элемент, который будет возвращаться операцией извлечь. Опять-таки, в реализации можно организовать элементы любым требуемым способом при условии сохранения иллюзии того, что элементы организованы именно в соответствие с дисциплиной FIFO.

В случае реализации АТД Очередь FIFO с помощью связного списка, элементы списка хранятся в следующем порядке: от первого вставленного до последнего вставленного элемента (см. рис. 4.6). Такой порядок является обратным по отношению к порядку, который применяется в реализации стека, причем он позволяет создавать эффективные реализации операций над очередями. Как показано на рис. 4.7 и в программе 4.14 (реализации), поддерживаются два указателя на этот список: один на начало списка (чтобы можно было извлечь первый элемент) и второй на его конец (для занесения в очередь нового элемента).

т о и т

R S S

S т т

I N

I N N

F I I

I R S

и Т т

РИСУНОК 4.6 ПРИМЕР ОЧЕРЕДИ FIFO

На рисунке показан результат выполнения последовательности операций. Операции представ-пены в левом столбце (порядок выполнения - сверху вниз); здесь буква обозначает операцию put (занести), а звездочка - операцию get (извлечь). Каждая строка содержит операцию, букву, возвращаемую операцией get и содержимое очереди от первого занесенного элемента до последнего в направлении слева направо.

Программа 4.14 Реализация очереди FIFO на базе связного списка

Различие между очередью FIFO и стеком магазинного типа (программа 4.8) состоит в том, что новые элементы вставляются в конец списка, а не в его начало. Следовательно, в этом классе хранится указатель tail на последний узел списка, и, таким образом, функция put может добавлять в список новый узел, связывая его с узлом, на который ссылается указатель tail, а затем обновляя указатель tall так, чтобы он указывал уже на новый узел. Функции QUEUE, get и empty идентичны аналогичным функциям в реализации стека магазинного типа на базе связного списка из программы 4.8. Поскольку новые узлы всегда вставляются в конец списка, конструктор узлов может устанавливать в null поле указателя каждого нового узла и получать только один аргумент.

template <class Item> class QUEUE

0; }

private: struct node { Item item; node* next; node(Item x) { item = x; next =

typedef node *link; link head, tail; p\iblic:

QUEUE(int)

{ head =0; } int empty 0 const

{ re turn head == 0; } void put(Item x) { link t = tail;

tail = new node (x) ; if (head == 0) head = tail; else t->next = tail;

Item get() { Item V = head->item; link t = head->next; delete head; head = t; return v;

РИСУНОК 4.7 ОЧЕРЕДЬ НА БАЗЕ СВЯЗНОГО СПИСКА

В представлении очереди в виде связного списка новые элементы вставляются в конец списка, поэтому элементы связного списка от первого вставленного элемента до последнего располагаются от нача.ча к концу очереди. Очередь представляется двумя указателями: head (начало) и tail (конец), которые указывают, соответственно, на первый и посчедний элемент. Ляя извлечения элемента из очереди удаляется элемент в начале очереди так же, как это дело/юсь в случае стека (см. рис. 4.5). Чтобы занести в очередь новый элемент, поле связи узла, на который ссылается указатель tail, устанавливается так, чтобы оно указывало на новый элемент (середина рисунка), а затем обновляется указатель tail (нижняя часть рисунка)

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

бы предположить при буквальной интерпретации рис. 4.6. Следовательно, как и в реализации на базе связного списка, потребуется поддерживать два индекса в массиве: индекс начала очереди и индекс конца очереди. Содержимым очереди считаются элементы, индексы которых находятся в рамках упомянутых двух индексов. Чтобы извлечь элемент, он удаляется его из начала (head) очереди, после чего индекс head увеличивается на единицу; чтобы занести элемент, он добавляется в конец (tail) очереди, а индекс tail увеличивается на единицу. Как иллюстрирует рис. 4.8, последовательность операций занести и извлечь приводит к тому, что все выглядит так, будто очередь движется по массиву. Она устроена так, что при достижении конца массива осуществляется переход на его начало. С деталями реализации рассмотренного процесса можно ознакомиться в коде программы 4.15.

Программа 4.15 Реализация очереди FIFO на базе массива

к содержимому очереди относятся все элементы массива, расположенные между индексами head и tail; при этом учитывается переход с конца на начало массива. Если индексы head и tail равны, очередь считается пустой, однако если они стали равными в результате выполнения операции put, очередь считается полной. Как обычно, проверка на такие ошибочные ситуации не выполняется, но размер массива делается на 1 больше максимального количества элементов очереди, ожидаемое программой-клиентом. При необходимости программу можно расширить, включив в нее подобного рода проверки.

template <class Item> class QUEUE

private:

Item *q; int N, head, tail; public:

QUEUE(int maxN) { q = new Item[maxN+l] ;

N = maxN+1; head = N; tail = 0; } int empty 0 const

{ return head % N == tail; } void put (Item item)

{ q[tail++] = item; tail = tail % N; } Item getO

{ head = head % N; return q[head-l-l-] ; }

I R I R I Я I R R

РИСУНОК 4.8 ПРИМЕР ОЧЕРЕДИ FIFO, РЕАЛИЗОВАННОЙ НА БАЗЕ МАССИВА

Данная последовательность операций отображает манипуляции с данными, лежащие в основе абстрактного представления очереди из рис. 4.6. Эти манипуляции соответствуют случаю, когда очередь реализуется за счет запоминания ее элементов в массиве, сохранения индексов начала и конца очереди и обеспечения перехода индексов на начало массива, когда они достигают его конца. В данном примере индекс tail переходит на начало массива, когда вставляется второй символ Т, а индекс head - когда удаляется второй символ S.