Основы теории. Очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (first-inОчередь — это линейный список информации, работа с которой происходит по принципу " первым пришел — первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO. Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается. Можно реализовать очередь в памяти компьютера в блоке смежных ячеек, схожим со стеком образом. Так как необходимо производить операции на обоих концах структуры, то, в отличие от стека, где требуется одна дополнительная ячейка, здесь отдельно заводятся еще две ячейки памяти для использования в качестве указателей. Один из них, называемый указателем головы, предназначен для отслеживания головы очереди; другой, указатель хвоста, предназначен для отслеживания хвоста очереди. Если очередь пуста, оба указателя указывают на одно и то же место в памяти (рис. 1). Новая запись помещается по адресу, содержащемуся в указателе хвоста, а затем значение этого указателя изменяется на адрес следующего свободного места в памяти. Таким образом, указатель хвоста всегда указывает на первое свободное место в очереди. Для удаления записи из очереди необходимо считать значение, на которое указывает указатель головы, а затем изменить его значение, чтобы он указывал на запись, следующую за удаленной.
Рисунок 1 - Очередь с указателями головы и хвоста: a – пустая очередь; б – после добавления записи А; в – после добавления записи В; г – после удаления записи А
Но с этой системой хранения связана серьезная проблема. Если не управлять очередью, она постепенно будет перемещаться по памяти, как ледник, разрушая остальные данные на своем пути (рис. 2). Это движение является результатом «эгоцентричного» правила добавления новых элементов путем размещения их рядом с предыдущим и соответствующего переопределения указателя хвоста. Если добавить достаточно записей, хвост очереди, в конце концов, доберется до конца машинной памяти. Причиной такого расходования памяти является не размер очереди, а недостаток ее реализации. Можно решить эту проблему, перемещая элементы очереди вперед при каждом удалении записей из ее начала, так же как в очереди к театральной кассе люди делают шаг вперед, как только первый человек приобретает свои билеты. Но этот подход не эффективен в компьютерной технологии, так как требует массовых перемещений данных.
Рисунок 2 – Очередь, «ползающая» по памяти: а – очередь с записями А, В и С; б – очереди после добавления D, E и F и удаления A и B; в – вид очереди после добавления G и H и удаления C и D
Наиболее распространенный способ управления очередью в памяти компьютера состоит в выделении блока памяти, с одного края которого очередь начинается и перемещается к концу блока. Затем, когда хвост очереди достигает конца блока, мы просто начинаем добавлять записи в начало этого блока, где к этому времени освобождается место. Когда последняя запись в блоке станет головой очереди и будет удалена, головной указатель переместится обратно к началу блока, куда были добавлены новые записи, ожидающие обработки. Таким образом, очередь как бы ходит по кругу внутри одного блока, а не перемещается по всей памяти компьютера. Этот способ реализации называется циклической очередью (circularqueue), так как образуется цикл из ячеек памяти, выделенных для очереди (рис. 3). С точки зрения этой очереди последняя ячейка в блоке соседствует с первой.
Рисунок 3 – Фактическое устройство циклической очереди, содержащей буквы от F до O (а) и ее абстрактное представление, где последняя ячейка блока «граничит» с первой (б)
Необходимо еще раз обратить внимание на разницу между абстрактной структурой, как ее представляет пользователь, и фактической циклической структурой, реализованной в памяти машины. Как и в случае с предыдущими структурами, программное обеспечение скрывает эти различия. То есть помимо набора ячеек памяти, в которых хранятся данные, реализация очереди должна включать в себя несколько процедур для добавления и удаления записей из очереди и определения, пуста очередь или заполнена. Тогда программист, работающий с другим программным модулем, сможет производить вставку и удаление записей при помощи этих процедур, не думая о деталях организации очереди в памяти. Создание очереди описано на псевдокоде 1. r = new (node); //создание нового узла очереди (*r).elem = Элем; // указатель на первый //элемент очереди (*r).sled = NULL; //указатель на следующий //пустой узел
Рисунок 4 - Первый элемент в очереди 2. no = r; // указатель на начало очереди ko = r; // указатель на конец очереди
Рисунок 5 - Настройка указателей начала и конца очереди Итак, мы образовали очередь, состоящую из одного звена. 3. Продолжим заполнение очереди: r = new (node); // создание еще одного узла (*r).elem = Элем1; // указатель на первый элемент (*r).sled = NULL; // указатель на //следующий(пустой) узел
Рисунок 6 - Создание нового элемента очереди 4. Настроим указатель на конец очереди: (*ko).sled = r; // указатель на второй узел ko = r; // указатель на конец очереди
Рисунок 7 – Настройка указателя на конец очереди Таким образом, очередь уже содержит два звена, таков принцип построения и далее. Представим описанный алгоритм в виде функции на языке C++: void POSTROENIE (node *no, node *ko) // Построение очереди на базе однонаправленного // линейного списка без заглавного звена: // *no - указатель на начало очереди, // *ko - указатель на конец очереди. { //открытие тела функции POSTROENIE node *r; // указатель начала очереди intel; // целочисленная переменная вводимых элементов // очереди cin> > el; // ввод элемента if (el! =0) // в случае если введено ‘0’ { // начало if r = new (node); // создание узла (*r).elem = el; // указатель на последний введенный // элемент (*r).sled = NULL; // указатель на пустой узел *no = r; //указатель начала очереди равен //последнему созданному узлу *ko = r; //указатель хвоста очереди равен последнему //созданному узлу cin> > el; // ввод следующего элемента while (el! =0) // пока он не равен нулю делаем
{ // открытие wile r = new (node); // создание узла (*r).elem = el; // указатель на последний введенный // элемент (*r).sled = NULL; // указатель на пустой узел (*ko).sled = r;; // присвоение указателя очереди началу // нового звена *ko = r; // конец очереди это созданное звено cin> > el; // ввод следующего элемента }// закрытие wile } // завершение if else // условный оператор иначе { r = NULL; *no = r; *ko = r; } // производим //обнуление указателей } //закрытие тела функции POSTROENIE Тут же приведем функцию для просмотра содержимого очереди: void VYVOD (node *no, node *ko) // Вывод содержимого очереди. // *no - указатель на начало очереди, // *ko - указатель на конец очереди. { //открытие тела функции VYVOD node *r; // указатель начала очереди cout< < " Очередь: "; // Вывод строки на дисплей r = *no; // узел очереди это ее начало while (r! =NULL) // делаем пока не дойдем до конца //очереди { // открытие wile cout< < (*r).elem< < " "; // вывод элементов очереди r = (*r).sled; //присвоение узлу очереди следующего //элемента } // закрытие wile cout< < endl; //возврат каретки }//закрытие тела функции VYVOD
Замечание. Очереди целесообразно хранить в памяти ЭВМ в виде кольцевого списка с двумя указателями (один - на начало, другой - на конец очереди):
Рисунок 8 - Представление очереди При исключении из очереди первого звена в первый указатель записывается ссылка на следующее звено списка, которая содержалась в поле указателя исключаемого звена, а при включении в очередь нового звена во второй указатель записывается ссылка на новое звено.
|
