Динамические структуры данных. Алексеев А.Ю - 39 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

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

Рубрика: 

Mem:
n 3 2 1
Верх
x x x x x x . . .
Рис. 2.2. Непрерывное представление стека в векторе
Для пустого стека Верх = 0, для целиком заполненного стека Верх = n.
Вершина стека доступна как Mem [ Верх ], операция Pop реализуется как
Верх:= Верх − 1, а операция Push ( p , s ) как begin Верх:= Верх + 1;
Mem [ Верх ]:=p end при 0≤Верх<n.
На базе одного вектора можно реализовать два стека, ограниченных в со-
вокупности. Такую реализацию иллюстрирует рис. 2.3.
39
Рис. 2.3. Непрерывное представление двух стеков,
ограниченных в совокупности
Рассмотрим основные идеи непрерывной реализации ограниченной очере-
ди на базе вектора. На рис.2.4 изображен вектор Mem [ 1 .. n ] и переменные
Начало, Конец: 1..n, идентифицирующие начало и конец очереди при ее не-
прерывном размещении в векторе Mem.
Рис. 2.4. Непрерывное представление очереди в векторе
Особенностью такого представления является наличие ситуации, когда по-
следовательность элементов очереди по мере их добавления может выходить
Mem:
n
3 2
1
Начало
x x x x x x x x
Конец
Mem:
n 1 2 3
x x x x x x . . . x x x x
Верх1
Стек1
Верх2
Стек2 
                1     2       3                                                                                       n

     Mem:       x x           x       x       x       x                         ...


                                                  Верх


                    Рис. 2.2. Непрерывное представление стека в векторе

   Для пустого стека Верх = 0, для целиком заполненного стека Верх = n.
Вершина стека доступна как Mem [ Верх ], операция Pop реализуется как
Верх:= Верх − 1, а операция Push ( p , s ) как begin Верх:= Верх + 1;
Mem [ Верх ]:=p end при 0≤Верх

Страницы