Методы программирования. Громов Ю.Ю - 12 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

12
Обойти проблему выхода очереди за пределы памяти можно зафик-
сировав M узлов X [1], …, X [M] и неявно «замкнув» их в кольцо так, что
за X [M] следует X [1]. Тогда процессы (4), (5) преобразуются к виду:
если R = M, то R ← 1; иначе R ← R + 1; X [R] ← Y. (6)
если F = M, то F ← 1; иначе F ← F + 1; Y ← X [F ]. (7)
Очевидно, что в очереди при такой ситуации не может быть более
М узлов.
Представим действия с включением и исключением узлов для стека
(2), (3) и очереди (6), (7) с учётом того, что в результате включения узла
может возникнуть выход за отведённое место в памяти (ПЕРЕПОЛНЕ-
НИЕ) или при попытке исключения отсутствующего узла в списке (НЕ-
ХВАТКА):
X
⇐
Y
(включить в
стек);
←
>+←
.][
;ИЕПЕРЕПОЛНЕНто,если,1
YTX
MTTT
Y
⇐
X
(исключить из
стека);
−←←
=
.1],[
;НЕХВАТКАто,0если
TTTXY
T
X
⇐
Y
(включить в оче-
редь);
←
=
+←←=
.][
;ИЕПЕРЕПОЛНЕНто,если
;1иначе,1то,если
YRX
FR
RRRMR
X
⇐
Y
(исключить из
очереди);
←
+←←=
=
].[
;1иначе,1то,если
;НЕХВАТКАто,если
FXY
FFFMF
FR
Заметим, что ПЕРЕПОЛНЕНИЕ является критической ошибкой.
Рассмотрим случаи, когда программа работает не с единственным
списком. Если имеется всего два стека переменного размера, то они мо-
гут хорошо сосуществовать вместе, когда будут расти навстречу друг
другу:

Страницы