Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Очередь

Стек

Общая характеристика

Стеки, очереди, деки и операции в них

Рассматриваемые в данном разделе структуры данных характеризуются ограниченным доступом к своим элементам для операций включения и исключения. До относительно недавнего времени такие структуры находили применение в основном при выполнении операций, организуемых на аппаратном уровне. При таком подходе элементы структуры располагаются последовательно, занимая непрерывный участок памяти. Примеры последовательной структуры с ограниченным доступом дают стеки оперативной памяти и буферные области, используемые в операциях обмена с внешними устройствами.

Со временем выяснилось, что структуры с ограниченным доступом весьма удобны для процедур, не требующих последовательного размещения элементов (проверка скобочной структуры различных выражений и последовательностей операторов, операции по преобразованию строк и т. п.). Были разработаны и нашли применение разнообразные основанные на связных структурах классы, в которых методы ограничивают доступ по вставке и удалению.

Ниже приводится «классическое» описание, основанное на следующих постулатах:

1) структура существует и изменяется в пределах ограниченной области заранее отводимой памяти, в общем случае элементами занята только часть ячеек, отведенных для структуры;

2) элементы структуры в каждый текущий момент времени занимают сплошной участок памяти, т. е. структура является последовательной структурой;

3) для операций включения и исключения доступны только концевые элементы структуры, иными словами, внутренние части участка памяти, содержащего «полезные» элементы е1, е2, …, еn, для этих операций недоступны.

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

Стек (stack) - это такой последовательный список е1, е2, …, еn с переменной длиной n, включение в который нового элемента и исключение из него выполняется только с одной стороны. Говорят, что стек функционирует по принципу LIFO (Last In - First Out, т. е. «последним пришел - первым вышел»). Примером стековой организации является винтовочный магазин: патрон, вставленный в него последним, при стрельбе «выйдет» первым.

Логическая структура стека представлена на рисунке 7.1. Элементы стека могут иметь как одинаковые, так и различные размеры. Последний добавленный в стек элемент еn, называется вершиной стека (top of stack). Важной составляющей структуры стека является указатель, направленный к вершине, - этот указатель называется указателем стека (stack pointer). Элемент, непосредственно примыкающий к нижней границе, называется дном стека (bottom of stack).

 

 

Рисунок 7.1 – Логическая структура стека

 

Для хранения стека в памяти отводится сплошная область памяти, называемая сегментом стека. Граничные адреса этой области памяти являются параметрами физической структуры стека. Физическая структура стека, показанная на рисунке 7.2, обычно дополняется дескриптором.

Важнейшие операции в стеке – включение и исключение. Применительно к стеку операцию включения обычно называют заталкиванием (push) элемента, а операцию исключения - выталкиванием (pop). Процедура заталкивания в стек нового элемента организуется как последовательность следующих действий: указатель стека сначала перемещается «вверх» (по рисунку 7.1) к слоту включаемого элемента, а затем по новому значению указателя помещается содержимое включаемого элемента. При выталкиваниииз стека сначала извлекается содержимое элемента еn, а затем указатель стека перемещается «вниз» на длину слота исключаемого элемента. Таким образом указатель стека обслуживает динамику изменения стека.

 

Рисунок 7.2 – Физическая структура стека

 

Если в процессе заполнения отведенной области указатель стека, перемещаясь к верхней границе, выходит за эту границу, то происходит переполнение стека (stack overflow). Попытка выполнить исключение элемента из пустого стека приводит к ошибке опустошения (underflow). Переполнение и опустошение стека рассматривается как исключительные ситуации, требующие (либо от пользователя, либо от логики аппаратуры) выполнения некоторых действий по их ликвидации.

Сегмент стека - важная область памяти, которую, наряду с сегментами кода и данных, создает компилятор, реализуя программу в виде исполняемого приложения. При работе в реальном режиме сегмент стека ограничивается 64 Кбайт, тогда как в защищенном режиме этот сегмент может занимать до 4 Гбайт. Сегмент стека можно увеличить или уменьшить до определенного размера, но он есть всегда.

Типичным применением стека является запись в него параметров, передаваемых в подпрограмму при ее вызове, и освобождение памяти стека от этих параметров после завершения работы подпрограммы.

Очередь (queue) – это такой последовательный список с переменной длиной, в который включение элементов происходит с одной стороны, а исключение – с другой стороны. Она функционирует по принципу FIFO (First In - First Out, т.е. «первым пришел - первым вышел»). Та сторона, с которой осуществляется добавление элементов, называется хвостом (tail) или концом очереди, другая сторона, из которой выполняется удаление, – головой (head). Для индикации хвоста и головы организуется два указателя: указатель хвоста (tail pointer) и указатель головы (head pointer). Логическая структура очереди, которую принято изображать в горизонтальной «ориентации», показана на рисунке 7.3. Обратите внимание, что указатель хвоста ссылается на свободную ячейку, следующую за элементом еn, включенным в очередь последним.

 

 

Рисунок 7.3 – Логическая структура очереди

 

Для очереди выделяется конечная последовательность ячеек, из которых в каждый текущий момент времени элементами очереди занята лишь часть последовательных ячеек. Каждый элемент очереди обычно представляет запись с одинаковой для всех элементов организацией.

Основные операции в очереди - включение и исключение элемента. При включении новый элемент заносится в ячейку, адресуемую указателем хвоста, после чего указатель хвоста «перемещается» к следующему свободному элементу. При исключении из очереди извлекается элемент е1, адресуемый указателем головы, и этот указатель «передвигается» к элементу е2, который становится головным элементом. Признаком пустой очереди является равенство указателей хвоста и головы.

В процессе выполнения неоднократных включений и исключений наблюдается перемещение всей очереди к границе хвоста, причем это происходит независимо от того, исключаются элементы или не исключаются. В отличие от стека, скорость перемещения к той границе, откуда включаются элементы, не зависит от интенсивности операций исключения. Состояние переполнения возникает при выходе указателя хвоста за пределы отведенного участка памяти. Этот недостаток устранен в кольцевой очереди, логическая структура которой показана на рисунке 7.4.

В кольцевой очереди соблюдается дисциплина FIFO. В отличие от обычной очереди включение в кольцевую очередь организовано следующим образом: сразу после выхода указателя хвоста за пределы его границы он переводится на слот, расположенный «вплотную» к границе, расположенной со стороны головы и, если этот слот пуст, то в него включается новый элемент. На рисунке 7.4 показана ситуация, когда перемещение указателя хвоста к начальному слоту происходит при включении элемента е4, а затем элемента е5. Очевидно, в кольцевой очереди возможно любое соотношение между указателями головы и хвоста.

 

 

Рисунок 7.4 – Логическая структура кольцевой очереди

 

Очереди находят интенсивное применение в вычислительной технике, например, при буферизации данных в устройствах. Буфер представляет собой набор внутренних ячеек памяти с определенными правилами доступа как со стороны устройства, так и со стороны компьютерного «центра» (программы, исполняемой процессором).

Для устройств с потоковой передачей данных (принтеры, сканеры) буфер ставится между «центром» и устройством, с одной стороны он наполняется, с противоположной - опорожняется. Тем самым реализуется принцип обычной очереди. Опорожняющая сторона может извлекать данные из буфера, лишь когда наполняющая сторона их туда «положит». Логика буфера следит за степенью заполнения буфера и сообщает процессору о критических ситуациях, препятствуя переполнению или опустошению.

По принципу кольцевой очереди функционируют, например, буферы некоторых устройств с блочным обменом данными (диски, адаптеры локальных сетей). Наиболее известным примером кольцевой очереди является структура, называемая буфером клавиатуры (буфер BIOS для записи кодов нажимаемых клавиш).

<== предыдущая лекция | следующая лекция ==>
Функциональные и свободные списки | Общая характеристика. Динамические множества и словари
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 287; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.