Проверка переполнения

Состояние переполнение стека возникает всякий раз, когда указатель U указывает на последний элемент вектора S, а мы пытаемся добавить в стек новый элемент.

Функция Переполнение()

  • 1. Переполнение = Ложь
  • 2. Если U - п, то Переполнение = Истина

Включение элемента

При занесении элемента в стек сначала необходимо проверить переполнение стека. Если переполнение, то выход из процедуры включения. Иначе необходимо модифицируется указатель V таким образом, чтобы он указывал на следующий свободный элемент, и элемент записывается на место, определяемое указателем стека.

Процедура Включение(Х)

  • 1. Если Переполнение(), то выход.
  • 2. U = U + 1
  • 3. S(U) = X

Проверка пустоты

Стек пуст, если значение указателя U равно нулю. На этом основана следующая функция.

Функция Пусто()

  • 1. Пусто - Ложь
  • 2. Если U = 0, Пусто = Истина.

Исключение элемента

Операция исключения элемента начинается с проверки наличия элементов в стеке. Если стек пуст, то процедура исключения завершается. Иначе выбирается значение, на которое указывает указатель U, после чего указатель модифицируется.

Процедура Исключение(Уаг X)

1. Если Пусто() - стек пуст. Выход.

  • 2. Х- S(U)
  • 3. U=U-1

Неразрушающее чтение элемента из вершины стека

Данная операция выполняется аналогично операции исключения элемента из стека, однако значение указателя при этом не изменяется.

Процедура Прочитатъ(Уаг X)

  • 1. Если Пусто() - стек пуст. Выход.
  • 2. X = S(U)

Очистка стека

Операция очистки стека сводится к записи в указатель стека начального значения - адреса начала выделенной области памяти.

Процедура Очистить

1. U = О

Определение текущего числа элементов в стеке

Определение размера стека сводится к вычислению значения указателя U.

Функция Количество()

1. Количество = U.

Использование стеков

После того как мы определили стек и выполняемые над ним операции, мы можем использовать его для решения различных задач.

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Рассмотрим некоторые из них.

Обеспечение вложенных вызовов процедур

Предположим, имеется процедура А, которая вызывает процедуру В, а та в свою очередь - процедуру С. Когда выполнение процедуры А дойдет до вызова В, процедура А приостанавливается и управление передается на входную точку процедуры В.

Когда В доходит до вызова С, приостанавливается В и управление передается на процедуру С. Когда заканчивается выполнение процедуры С, управление должно быть возвращено в В, причем в точку, следующую за вызовом С. При завершении В управление должно возвращаться в Л, в точку, следующую за вызовом В.

Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. Так, когда процедура А вызывает процедуру В, в стек заносится адрес возврата в А; когда В

вызывает С, в стек заносится адрес возврата в В. Когда С заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в В. Когда заканчивается В, в вершине стека находится адрес возврата в Л, и возврат из В произойдет в А.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >