Очередь

Стек

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

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

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

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

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

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

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

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

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

Стек (stack) - это такой последовательный список е₁, е₂, …, е_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 – Логическая структура очереди

 

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

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

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

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

 

 

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

 

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

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

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