Список
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 HeapReAllос, которая изменяет размер выделенного блока в сторону его увеличения или уменьшения. В принципе, полезной может оказаться операция определения объема стека, то есть количества элементов в нем. Попробуйте реализовать ее самостоятельно.
Очередь
Очередь [2, 10, 15] – последовательный список, в котором включение элементов производится на одном конце, а исключение на другом, то есть по принципу FIFO (First In First Out – первым пришел – первым ушел). Сторона очереди, на которой производится включение элементов, называется хвостом. Соответственно, противоположная сторона – голова очереди. Очередь описывается дескриптором, который может содержать поля: имя очереди, адреса верхней и нижней границ области памяти, выделенной для очереди, указатели на голову и хвост. Набор операций для очереди:
- создание очереди (create_que);
- включение элемента в очередь (push_que);
- исключение элемента из очереди (popque);
- проверка пустоты очереди (TestEmptyQue);
- очистка очереди без освобождения памяти для нее (initque);
- удаление очереди (delete_que).
При помощи очереди удобно моделировать некоторые обслуживающие действия, например это может быть некоторая очередь запросов к критическому ресурсу или очереди заданий на обработку. К очереди так же, как и стеку, применимы такие параметры, как емкость очереди и размер элемента очереди.
На практике используются очереди двух типов – простые и кольцевые. Очередь обслуживается двумя указателями – головы (Р,) и хвоста очереди (Р2). Указатель головы Р идентифицирует самый старый элемент очереди, указатель хвоста – первый свободный слот после последнего включенного в очередь элемента. Сами элементы физически по очереди не двигаются. Меняется лишь значение указателей. При включении в очередь новый элемент заносится в ячейку очереди, на которую указывает Р2. Операция исключения подразумевает извлечение элемента из ячейки очереди, указываемой Р.
Кроме извлечения элемента операция исключения производит корректировку указателя Р, так, чтобы он указывал на очередной самый старый элемент очереди. Таким образом, Указатель хвоста простой очереди всегда указывает на свободную ячейку очереди и рано или поздно он выйдет за границы блока, выделенного для очереди. И это случится несмотря на то, что в очереди могут быть свободные ячейки. Чтобы исключить это явление, очередь организуется по принципу кольца. В обоих способах организации очереди важно правильно определить ее емкость. Недостаточный объем очереди может привести в определенный момент к ее переполнению, что чревато потерей новых элементов, претендующих на включение в очередь.