Стек — последовательный список, в котором все включения и исключения элементов производятся на одном его конце — по принципу LIFO (Last In First Out — последним — пришел первым ушел). Для стека определены следующие операции:
- создание стека;
- включение элемента в стек;
- исключение элемента из стека;
- очистка стека;
- проверка объема стека (числа элементов в стеке);
- удаление стека.
Создание стека должно сопровождаться
инициализацией специального дескриптора стека, который может содержать
следующие поля: имя стека, адреса нижней и верхней границ стека,
указатель на вершину стека.
Иллюстрацию организации и работы стека произведем на примере
задачи, анализирующей правильность согласования скобок в некотором
тексте. Причем условимся, что скобки могут быть нескольких видов: (),
{}, [], <>. Программа реализована в виде приложения Win32 с
использованием функций API Win32 для работы с кучей (из нее выделяется
память для стека).
mov ecx,l_string
lea ebx.string
jmp cycl
e_xit: jmp exit cycl: jcxz e_xit
cmp byte ptr [ebx]."("
je m_push
cmp byte ptr [ebx],"["
je m_push
cmp byte ptr [ebx],"{"
je m_push
cmp byte ptr [ebx]."<"
je m_push
cmp byte ptr [ebx],")"
jneml извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.
cmp temp." ("
jne mes_error
jmp r_next ml: cmp byte ptr [ebx],"]"
jnem2 извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.
cmp temp," ["
jnemes_error
jmp r_next m2: cmp byte ptr [ebx],"}"
jnem3 ¦.извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_err6r
pop_stkchar_stk,
cmp temp."{"
jne mes_error
jmp r_next m3: cmp byte ptr [ebx],">"
jne rjiext извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.
cmp temp,"<"
jne mes__error
jmp r_next m_push: включение скобки в стек
pushstk char_stk.ebx r_next:add ebx,char_stk.si ze_i tern
dec ecx
jmp cycl mes_error: :вывод на экран сообщения об ошибке mes_e
jmp exitexit
exit:
определяем стек на пустоту
pop_stkchar_stk,
exit_exit: :выход из приложения
delete_stk char_stk :удаляем блок памяти со стеком
Код, выполняющий работу со стеком, оформлен в виде макрокоманд. При необходимости код можно сделать еще более гибким. Для этого нужно использовать функцию API Win32 HeapReAl 1 ос, которая изменяет размер выделенного блока в сторону его увеличения или уменьшения. В принципе, полезной может оказаться операция определения объема стека, то есть количества элементов в нем. Попробуйте реализовать ее самостоятельно.