Сборник по задачам и примерам Assembler
       

Стек



Стек

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


    pop_stkchar_stk.<offset temp>

    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,<offset temp> jncmes_error :стек не пуст :вывод на экран сообщения mes_ok

    exit_exit: :выход из приложения

    delete_stk char_stk :удаляем блок памяти со стеком

    Код, выполняющий работу со стеком, оформлен в виде макрокоманд. При необходимости код можно сделать еще более гибким. Для этого нужно использовать функцию API Win32 HeapReAl 1 ос, которая изменяет размер выделенного блока в сторону его увеличения или уменьшения. В принципе, полезной может оказаться операция определения объема стека, то есть количества элементов в нем. Попробуйте реализовать ее самостоятельно.


    Содержание раздела