Семинар 6
Стековая сортировка потоков данных.
Стек (stack) это абстрактная структура данных для хранения набора элементов, обработка которого допустима только с одного конца, называемого вершиной стека. Положение вершины в стеке отображает указатель стека sp (stack pointer). Через вершину в стеке можно добавить (протолкнуть) новый элемент или извлечь (вытолкнуть) последний добавленный элемент, изменяя при этом соответствующим образом указатель стека. Извлекать элементы из стека и добавлять элементы в стек можно неоднократно, пока стек не пуст и не переполнен, соответственно. Реализуемая стеком дисциплина обслуживания набора данных называется LIFO (LastInput, FirstOutput - последним пришел, первым обслужен). Для хранения данных в стеке выделяется специальный буфер sbuf (stack buffer). В простейшем случае буфер стека реализуется одномерным массивом, длина которого априори устанавливает предельный размер стека ssize (stack size), задаваемый при создании стека. Такая организация стека называется стеком с фиксированным буфером (FixStack). Указатель стека sp интерпретируется как целочисленный индекс массива, представляющего текущий размер буфера стека. Логическую структуру стека с фиксированным буфером, в котором содержатся 3 элемента: A, B, C отображает следующий рисунок.
Рис. Логическая структура стека с фиксированным буфером.
Для работы со стеком используются 3 примитивные процедуры: PUSH, POP и STATE, которые обеспечивают загрузку (проталкивание) данных в стек, извлечение (выстреливание) данных из стека, и оценку состояния стека, соответственно. Примитив PUSH загружает (проталкивает) новый элемент в вершину стека и увеличивает на 1 значение указателя стека. Псевдокод процедуры PUSH выражают следующие операторы:
Sbuf[sp] <- V; sp <- sp+1; RETURN;
где V обозначает элемент данных, добавляемый в стек. Работу примитива PUSH отображает следующая диаграмма загрузки данных в стек.
Рис. Диаграмма загрузки в стек.
Примитив POP уменьшает на 1 величину указателя стека и возвращает значение текущего элемента из вершины стека. Результат возврата примитива POP может быть присвоен соответствующей по типу переменной программы, использующей стек. Псевдокод примитива POP выражают следующие операнды:
sp <- sp-1; RETURN (Sbuf[sp]);
Работу примитива POP иллюстрирует следующая диаграмма извлечения (выталкивания) данных из стека.
Рис. Диаграмма выталкивания данных из стека.
Для стека с фиксированным буфером процедура извлечения данных необязательно является деструктивной операцией, т.е. вытолкнутые элементы не уничтожаются в буфере стека, по крайней мере, до загрузки новых данных. Очевидно, что процедура проталкивания данных в стек имеет деструктивный эффект, модифицируя содержания буфера стека. Рассмотренные примитивы PUSH и POP обеспечивают желаемую обработку стека с фиксированным буфером, когда он не переполнен (sp < ssize) и не пуст (sp=0), соответственно. Для оценки текущего состояния стека используется примитив STATE. Он обеспечивает оценку состояния стека по возвращаемому значению его указателя. Целесообразной представляется следующая кодировка возврата примитива STATE. Если при оценке в буфере стека нет свободного места для размещения новых данных, т.е. буфер заполнен полностью, возвращается отрицательный код. В противном случае, когда в буфере стека есть свободное пространство для размещения новых элементов, при оценке стека примитивом STATE возвращается текущее значение указателя стека. Очевидно, когда стек пуст примитив STATE будет возвращать нулевое значение. Псевдокод примитива STATE выражают следующие операторы:
IF sp<ssize THEN RETURN(sp); ELSE RETURN(-sp);
На следующем рисунке представлены 3 диаграммы состояний для пустого, допустимо заполненного и переполненного стека, которые иллюстрируют принятую кодировку возврата примитива STATE.
Рис. Диаграмма состояний стека.
Примитив STATE следует использовать в сочетании с примитивами PUSH и POP, чтобы избежать потери значимости при переполнении стека и попытке извлечь данные из пустого стека. Следующий псевдокод блокирует потерю значимости в случае пустого стека (underflow) при использовании примитива POP для извлечения данных в переменную W:
IF STATE() > 0 THEN W <- POP(); ELSE UNDERFLOW();
где процедура UNDERFLOW реализует желаемую в программе последовательность обработки состояния пустого стека при попытке извлечь данные. Исключение потери значимости в случае переполнения стека (overflow) при попытке протолкнуть в стек новый элемент V, используя примитив PUSH, демонстрирует следующий псевдокод:
IF STATE() < 0 THEN OVERFLOW(); PUSH(V);
где процедура OVERFLOW содержит желаемую в программе последовательность обработки состояния переполнения стека, например, аварийное завершение, расширение буфера стека или переход к резервным буферам.
//------Основные операции со стеком
#define SIZE 100 // Размерность стека
int Stack[SIZE]; // Массив для размещения стека
int SP; // Указатель стека
void Init() // Очистка стека
{ SP=-1; } // Стек пуст
void Push(int val) // Запись в стек
{ SP++; // Указатель к следующему элементу
Stack[SP]=val; // Запись по указателю стека
}
int Pop() // Исключение из стека
{
if (SP < 0 ) return(0); // Стек пуст
return ( Stack[SP--]); // Возвратить элемент по указателю
} // Указатель к предыдущему
В архитектуре практически всех компьютеров используется аппаратный стек. Он представляет из себя обычную область внутренней (оперативной) памяти компьютера, с которой работает специальный регистр - указатель стека. С его помощью процессор может выполнять операции Push и Pop по сохранению и восстановлению из стека байтов и машинных слов различной размерности. Единственным отличием апаратного стека от рассмотренной модели является его расположение "вверх дном", то есть его заполнение от старших адресов к младшим. Большинство трансляторов используют стек (в том смысле, что генерируют команды, работающие со стеком) для реализации механизма вызова функций, где речь
идет о вложенности процессов, структур, определений. Для элемента, сохраненного в стеке, важно не его абсолютное положение в последовательности (массиве), а положение относительно вершины стека или его указателя.