ВУЗ:
Составители:
11
X[0] X[1] X[2] X[3] X[4] Y T
3 4
0 1 2 3 4 5 6 …
Чтобы переменной Y дать значение верхнего узла непустого стека и
исключить этот узел из списка, требуется
Y ← X [T] ; T ← T – 1. (3)
X[0] X[1] X[2] X[3] X[4] Y T
4 3
0 1 2 3 4 5 6 …
Представление очереди или, более того, дека общего вида требует
некоторых ухищрений. Выберем две переменные: указатель F для начала
очереди и указатель R для конца очереди. Тогда включение элемента в
конец очереди осуществляется следующим образом:
R ← R + 1; X [R] ← Y, (4)
X[0] X[1] X[2] X[3] X[4] Y F R
0 3 4
0 1 2 3 4 5 6 …
а исключение начального узла (F указывает на место, непосредственно
перед началом очереди) так:
F ← F + 1; Y ← X [F ]; если F = R, то F ← R ← 0. (5)
X[0] X[1] X[2] X[3] X[4] Y F R
0 1 4
0 1 2 3 4 5 6 …
Заметим, что в такой ситуации (когда в очереди есть по крайней ме-
ре один узел) R и F растут, причём R > F. В результате последовательно
занимаются ячейки X [1], X [2], … до бесконечности, что свидетельствует
о чрезмерно расточительном использовании памяти. Следовательно, про-
стой метод (4), (5) должен использоваться в такой ситуации, когда из-
вестно, что указатель F довольно регулярно догоняет указатель R (оче-
редь опустошается).
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
