Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Структуры данных типа очередь. Реализация очереди как отображение на массив и односвязный список. Примеры применения.




Читайте также:
  1. A) обработки данных, вводимых в ЭВМ
  2. A) Правила организация передачи данных в сети
  3. A) прикладная программа, предназначенная для обработки структурированных в виде таблицы данных
  4. A) прикладная программа, предназначенная для обработки структурированных в виде таблицы данных
  5. A) Результат вычисления формулы на основе имеющихся данных
  6. A) Совокупность программных средств, с помощью которых создается база данных и поддерживается в процессе эксплуатации
  7. A) сочетание жилищ, городской инфраструктуры и зеленых насаждений
  8. Bonpoс 19 Сплавы на основе алюминия и магния. Свойства и области применения.
  9. D-триггеры. Реализация. Режим работы.
  10. Quot;Бостонская резня", "Бостонское чаепитие", акция "Паблиус" -роль данных исторических событий в истории PR.

Искл. (“голова”)  
Очередь – последовательность, в которую включают элементы с одной стороны, а исключают – с другой. Структура функционирует по принципу FIFO (поступивший первым обслуживается первым). Условные обозначения очереди:

 
 

 


При реализации очереди рассматриваются очередь как отображение на массив (полустатическая реализация) и очередь как отображение на список.

Совокупность операций, определяющих структуру типа очередь:

· Операция инициализации.

· Операция включения элемента в очередь.

· Операция исключения элемента из очереди.

· Операция проверки: очередь пуста / очередь не пуста.

· Операция проверки: очередь переполнена / очередь не переполнена.

 

В последовательной памяти очередь имеет следующий вид:

 
 

 


Здесь: Uk 1 – указатель на “голову” (начало) очереди, Uk 2 – указатель на “хвост” (конец) очереди.

Чтобы избежать переполнения, рациональней использовать кольцевую очередь. При этом Uk 1 > Uk 2 или Uk 2 > Uk 1. В случае же если очередь не кольцевая, то всегда Uk 2 > Uk 1. Если очередь пуста или переполнена, то Uk 1 = Uk 2.

Пусть n – текущее состояние очереди, а N – количество элементов в очереди, тогда имеем условие 0 £ n £ N и значение n может являться условием проверки состояния очереди. Операция включения возможна, если n < N, а операция исключения, если n > 0. В случае кольцевой очереди при операции модуля указатели будут меняться следующим образом: Uk 1 = Uk 1 mod N + 1, Uk 2 = Uk 2 mod N + 1.

Схема на физическом уровне СД типа очередь выглядит следующим образом:

Дескриптор:


Дата добавления: 2015-04-18; просмотров: 16; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты