Студопедия

КАТЕГОРИИ:

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


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




Искл. (“голова”)  
Очередь – последовательность, в которую включают элементы с одной стороны, а исключают – с другой. Структура функционирует по принципу 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; просмотров: 82; Мы поможем в написании вашей работы!; Нарушение авторских прав





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