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

UptoLike

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

Рубрика:

Рис. 1. Стек, представленный в виде железнодорожного разъезда

Рис. 2. Дек, представленный в виде железнодорожного разъезда

Среди деков имеются так называемые деки с ограниченным выходом

и деки с ограниченным входом, в которых соответственно исключение и

включение допускаются только на одном конце списка.

При описании алгоритмов, использующих такие списки, принята

специальная терминология. Так, мы помещаем элемент на верх стека или

снимаем верхний элемент (рис. 3, а). Внизу стека находится наименее

доступный элемент, который не удаляется до тех пор, пока не будут ис-

ключены все другие элементы. Применительно к очередям мы говорим о

начале и конце очереди: объекты встают в конец очереди и удаляются

тогда, когда достигают её начала (рис. 3, б). Говоря о деках, мы указыва-

ем левый и правый концы (рис. 3, в).

Приведём несколько дополнительных способов описания операций,

выполняемых над стеками и очередями. Будем писать А ⇐ x, указывая

(если А – стек), что значение x помещается на верх стека или (если А –

очередь) что x включается в конец очереди. Подобным же образом запись

x ⇐ А будет обозначать, что переменная x принимает значение верхнего

элемента стека А или начального элемента очереди А, и это значение ис-

ключается из А.