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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

8
Рис. 3. Три важных класса линейных списков
При непустом стеке А его верхний элемент можно обозначить через
top (A).
Упражнения
1. Дек с ограниченным входом является линейным списком, в кото-
ром элементы могут включаться только с одного конца, а исключаться с
любого конца. Очевидно, что дек с ограниченным входом может работать
либо как стек, либо как очередь, если всегда будем удалять элементы с
одного из двух концов.
Может ли дек с ограниченным выходом работать либо как стек, ли-
бо как очередь?
2. Представьте себе, что четыре железнодорожных вагона находят-
ся на входном пути железнодорожного разъезда, иллюстрирующего стек,
и пронумерованы соответственно 1, 2, 3 и 4 (1234). Предположим, что мы
выполняем некоторую последовательность операций, которые согласу-
ются с направлением стрелок на рисунке при условии, что вагоны не мо-
гут «перепрыгивать» друг через друга. Отправьте: (а) вагон 1 в стек;
(b) вагон 2 в стек; (c) вагон 2 на выход; (d) вагон 3 в стек; (e) вагон 4 в
стек; (f) вагон 4 на выход; (g) вагон 3 на выход; (h) вагон 1 на выход.
В результате этих операций первоначальный порядок вагонов 1234
изменился на 2431.
Заметим, что (a) – (h) можно описать короче и выразительнее, ис-
пользуя код SSXSSXXX, где S обозначает фразу «отправить вагон из
входа в стек», а X − фразу «отправить вагон из стека на выход».

Страницы