Стеки и очереди.Работа со стеком

В гл.3 обсуждалось, как реализован стек в микропроцессоре 8088. Микропроцессор 8088 адресует стек с помощью регистровой пары SS:SP. Помещение объектов в стек приводит к тому, что он растет в сторону меньших адресов памяти. Стек, кроме всего прочего, служит и для запоминания адресов возврата из подпрограмм. В этом разделе рассматриваются некоторые команды, которые непосредственно работают со стеком.

Рисунок 4.7 иллюстрирует ассемблированные стековые команды. Мнемоника команд очевидна; за кодами операций PUSH и POP следует имя регистра для указания операнда. Единственным исключением является помещение и извлечение из стека регистра флагов, которые используют мнемонику PUSHF и POPF соответственно. Содержимое любой ячейки памяти, которую программа может адресовать, используя возможные способы адресации, также может быть помещено или извлечено из стека.

При любых действиях со стеком в микропроцессоре 8088 базовой единицей информации является 16-битовое слово. Длина любого объекта, помещаемого в стек либо извлекаемого из стека, составляет одно или несколько слов. Байтовых команд, связанных с засылкой данных или извлечением их из стека, не существует. Если, например, программе необходимо сохранить содержимое регистра AL в стеке, она должна поместить содержимое регистра AX, так как не существует способа сохранения только содержимого регистра AL.

Основное назначение стека - временное хранение информации. Как мы уже видели, стек используется для сохранения адреса возврата; программа также может сохранять данные. Если программа хочет использовать регистр, пусть даже сохранить текущие данные, она может послать значение этого регистра в стек. Эти данные сохраняются в стеке и позже могут быть восстановлены. Например, программе нужно ввести код из порта ввода-вывода 3DAH, а в регистре DX находятся важные данные. Следующая последовательность команд

Стеки и очереди.Работа с очередью

Для создания очереди и работы с ней необходимо иметь как минимум два указателя'

• на начало очереди (возьмем идентификатор BegQ),

• на конец очереди (возьмем идентификатор EndQ)

Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель (возьмем идентификатор Р) Дополнительный -указатель также часто используется р. других ситуациях для удобства работы с очередью Создание очереди

Связные списки

Связный список - это разновидность линейных структур данных, представляющая собой последовательность элементов, обычно отсортированную в соответствии с заданным правилом. Последовательность может содержать любое количество элементов, поскольку при создании списка используется динамическое распределение памяти.

Каждый элемент связного списка представляет собой отдельный объект, содержащий поле для хранения информации и указатель на следующий элемент списка (а в случае двусвязного списка в объекте хранится также указатель на предыдущий элемент).