Стек

Стек

Стек — последовательный список, в котором все включения и исключения элементов производятся на одном его конце — по принципу 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.<offset temp>

cmp temp." ("

jne mes_error

jmp r_next ml: cmp byte ptr [ebx],"]"

jnem2 извлекаем элемент из вершины стека и анализируем его

TestEmptyStk char_stk.mes_error

pop_stkchar_stk.<offset temp>

cmp temp," ["

jnemes_error

jmp r_next m2: cmp byte ptr [ebx],"}"

jnem3 ¦.извлекаем элемент из вершины стека и анализируем его

TestEmptyStk char_stk.mes_err6r

pop_stkchar_stk,<offset temp>

cmp temp."{"

jne mes_error

jmp r_next m3: cmp byte ptr [ebx],">"

jne rjiext извлекаем элемент из вершины стека и анализируем его

TestEmptyStk char_stk.mes_error

Содержание  Назад  Вперед