Структура данных ОЧЕРЕДЬ
Очередь – упорядоченный набор данных (структура данных), в котором в отличие от стека извлечение данных происходит из начала цепочки, а добавление данных – в конец этой цепочки.
Очередь также называют структурой данных, организованной по принципу FIFO (First In, First Out) – первый вошел (первый созданный элемент очереди), первый вышел.
В языке Си работа с очередью, как и со стеком, реализуется при помощи структур, указателей на структуры и операций динамического выделения и освобождения памяти.
Пример очереди – некоторый механизм обслуживания, который может выполнять заказы только последовательно один за другим. Если при поступлении нового заказа данное устройство свободно, оно немедленно приступит к выполнению этого заказа, если же оно выполняет какой-то ранее полученный заказ, то новый заказ поступает в конец очереди из других ранее пришедших заказов. Когда устройство освобождается, оно приступает к выполнению заказа из начала очереди, т.е. этот заказ удаляется из очереди и первым в ней становится следующий за ним заказ.
Заказы, как правило, поступают нерегулярно и очередь то увеличивается, то укорачивается и даже может оказаться пустой.
При работе с очередью обычно помимо текущего указателя используют еще два указателя, первый указатель устанавливается на начало очереди, а второй – на ее конец.
Шаблон элемента структуры, информационной частью которого является целое число, может иметь следующий вид:
struct Spis {
int info;
Spis *Next;
};
При организации очереди обычно используют два указателя
Spis *begin, *end;
где begin и end – указатели на начало и конец очереди соответственно, т.е. при создании очереди мы организуем структуру данных следующего вида:
каждый элемент которой имеет информационную infо и адресную Next (A1, A2, ...) части.
Основные операции с очередью следующие:
– формирование очереди;
– добавление нового элемента в конец очереди;
– удаление элемента из начала очереди.
Дата добавления: 2014-12-30; просмотров: 834;