Для описания алгоритмов обработки этих структур обычно используется специальная терминология. Например, объект кладут на верх стека или снимают верхний элемент стека (рис. 3, (а)). Доступ к элементу, находящемуся внизу стека, наиболее затруднителен; и его нельзя удалить до тех пор, пока не будут удалены все остальные элементы стека. (Часто говорят, что объект проталкивается (push) вниз стека и выталкивается (pop) на верх стека при удалении самого верхнего элемента. Эта терминология возникла от аналогии со стопкой тарелок в кафе. Краткость английского написания слов "протолкнуть" (push) и "вытолкнуть" (pop) обладает определенными преимуществами, но эти термины часто неверно трактуются, как движение всего списка целиком в памяти компьютера. На самом деле физически ничто никуда не проталкивается, а объекты всего лишь добавляются сверху стека точно так, как при укладке сена в стоге или коробок в стопке.) По отношению к очередям применяют понятия начало (front) и конец (rear) очереди. Объекты вставляются в конце очереди и проталкиваются по ней до тех пор, пока не достигнут начала очереди (рис. 3, (Ь)). При работе с деками используют понятия левый (left) и правый (right) концы (рис. 3, (с)). Концепции верха, низа, начала и конца иногда применяют по отношению к декам, которые используются в качестве стеков или очередей, но нет никаких стандартных соглашений в отношении того конца, с которого они должны располагаться: с правого или левого.

Таким образом, мы выяснили, что при создании алгоритмов достаточно удобно применять все богатое разнообразие языка: "верх-низ" (up-down) - для стеков, "ожидание в очереди" (waiting in Ипе) -для очередей и "слева-справа" (left-right) - для деков.

При работе со стеками и очередями удобно использовать некоторые дополнительные обозначения. Например, обозначение

А<=х (1)

указывает, что элемент х вставлен сверху стека А (если А - это стек) или элемент X вставлен в конце очереди (если А-это очередь). Аналогично

хА (2)

используется для обозначения того, что переменная х приравнивается к значению верхнего элемента стека А или начального элемента очереди А, т. е. это значение, которое удаляется из А. Обозначение (2) не имеет смысла, если А пусто, т. е. когда А не содержит значений.

Если А - непустой стек, то

top(A) (3)

можно использовать для обозначения самого верхнего его элемента.

УПРАЖНЕНИЯ

1. [06] Дек с ограниченным вводом является линейным списком, в котором элементы могут вставляться на одном конце, а удаляться - с любого конца. Очевидно, что дек может функционировать, как стек или очередь, если его элементы всегда будут удаляться с одного из двух его концов. Может ли дек с ограниченным выводом функционировать, как стек или очередь?

► 2. [15] Допустим, что четыре вагона с номерами 1, 2, 3 и 4 (слева направо) расположены со стороны ввода-вагонов железнодорожных путей (см. рис. 1). Предположим, что выполняется такая последовательность действий (которая совпадает с направлением стрелок на этой схеме и не дбпускает "перепрыгивания" через вагоны): (i) поместить вагон 1 в стек; (ii) поместить вагон 2 в стек; (iii) вывести вагон 2 из стека; (iv) поместить вагон 3 в стек; (v) поместить вагон 4 в стек; (vi) вывести вагон 4 из стека; (vii) вывести вагон 3 из стека; (viii) вывести вагон 1 из стека.

После выполнения этих действий исходный порядок вагонов, 1234, станет иным, 2431. Делью этого и следующих упражнений является выяснение, какие перестановки допустимы в стеках, очередях и деках.

Можно ли выполнить такую перестановку шестц пронумерованных вагонов, чтобы из исходного порядка 123456 получить порядок 325641? Можно ли поменять порядок вагонов так, чтобы он был равен 154623? (Если можно, то как именно?)

3. [25] Действия (i)-(viii) в предыдущем упражнении можно записать в более кратком виде с помощью кода SSXSSXXX, где S обозначает "ввести вагон в стек", а X- "вывести вагон из стека". Некоторые последовательности действий S и X бессмысленны, поскольку на соответствующих путях может совсем не быть вагонов. Например, последовательность действий SXXSSXXS не может быть выполнена, так как предполагается, что в исходном состоянии стек пуст.

Назовем последовательность действий S и X допустимой, если она содержит п действий S и п действий X и если в ней нет никаких бессмысленных действий. Сформулируйте правило, с помощью которого было бы легко различать допустимые и недопустимые последовательности действий. Покажите, что различные допустимые последовательности действий приводят к разным перестановкам.

4. [М34] Найдите простую формулу для а„, т. е. для количества перестановок среди п элементов, которые могут быть получены с помощью стека из упр. 2.

► 5. Покажите, что с помощью стека можно получить перестановку рхрг Рп исходной последовательности 12... п только в случае, если не существует таких индексов i <j<k, что pj <рк <pi.

6. [00] Рассмотрим задачу из упр. 2, в которой очередь используется вместо стека. Какие перестановки 12 ... п можно получить с помощью очереди?

► 7. [25] Рассмотрим задачу из упр. 2, в которой вместо стека используется дек. (а) Найдите такую перестановку последовательности 1234, которая может быть получена с помощью дека с ограниченным вводом, но не может быть пол5ена с помощью дека с ограниченным выводом. (Ь) Найдите такую перестановку последовательности 1234, которая может быть получена с помощью дека с ограниченным выводом, но не может быть получена с помощью дека с ограниченным вводом. [Как следствие из (а) и (Ь) между деками с ограниченным вводом и выводом существует определенная разница.] (с) Найдите такую перестановку последовательности 1234, которая не может быть получена ни с помощью дека с ограниченным вводом, ни с помощью дека с ограниченным выводом.

8. [22] Существуют ли какие-либо перестановки 12 ... п, которые не могут быть получены с помощью дека, не имеющего ни ограниченного ввода, ни ограниченного вывода?

9. [МйО] Пусть Ьп - количество перестановок среди п элементов, которые могут быть получены с помощью дека с ограниченным вводом, (Обратите внимание, что 64 = 22, как показано в упр, 7.) Покажите, что Ь„ также является количеством перестановок среди п элементов, которые могут быть получены с помощью дека с ограниченным выводом.

10. [М25] (См. упр. 3.) Пусть S, Q и X обозначают соответственно операции ввод;а элемента слева, ввода элемента справа и вывода элемента слева в деке с ограниченным выводом.

Например, применив последовательность действий QQXSXSXX к исходной последовательности символов 1234, йолучим 1342. Последовательность действий SXQSXSXX приведет к такому же результату.

Найдите такое опрёделение понятия допустимой последовательности символов S, Q и X, чтобы выполнялось следующее требование: каждая перестановка п элементов, которую можно получить с помощью дека с ограниченным выводом, должна соответствовать только одной допустимой последовательности.

► 11. [М40] Из упр. 9 и 10 получаем, что Ь„ является количеством допустимых последовательностей длины 2п. Найдите производящую функцию Х]„>оЬпг" в "замкнутом виде".

12. 1НМ34] Вычислите асимптотические значения величин а„ и Ь„ из упр. 4 и 11.

13. [М48] Сколько перестановок среди п элементов можнЗ получить с помощью дека? [В статье Розенстиля и Таржана, J. Algorithms 5 (1984), 389-390, приводится алгоритм, в котором за 0{п) шагов выясняется допустимость данной перестановки.]

► 14. [26] Предположим, что в качестве структур данных используются только стеки. Как наиболее эффективным образом воплотить очередь с помощью двух стеков?

2.2.2. Последовательное распределение

Наиболее простой и естественный способ хранения линейного списка в памяти компьютера заключается в расположении элементов в последовательных ячейках, при котором один узел списка следует сразу же за другим. Тогда

LOC(X[j + l]) =LOC(X[j])+c,

где с - количество слов в одном узле. (Обычно с = 1. Если с > 1, то в некоторых случайх удобнее разбить единый список на с "параллельных" списков таким образом, чтобы к-е слово узла X[j] хранилось на фиксированном расстоянии от первого слова X [j], которое зависит от к. Однако в дальнейшем предположим, что смежные группы по с слов образуют единый узел.) Вообще,

LOC(X[j]) =Lo + cj, (1)

где Lo-константа, которая называется базовым адресом (base address), т. е. является адресом некоего узла X [0].

Такой способ представления линейного списка настолько очевиден и хорошо известен, что его более глубокое изучение может показаться вовсе ненужным. Однако, как будет показано в данной главе, существует несколько других, более "изощренных" методов представления списков. Поэтому, прежде чем рассматривать более сложные случаи, было бы разумно изучить возможности этого простого способа. Очень важно ясно представлять себе как его недостатки, так и преимущества.

Последовательное распределение очень удобно при работе со стеком. Для этого достаточно иметь переменную Т, которая называется указателем стека {stack pointer). Если стек пуст, то Т = 0. Для ввода нового элемента Y в стек следует выполнить такие действия:

Т-(-Т--1; Х[Т]-(-У. (2)

А если стек не пуст, можем положить Y равным верхнему узлу и удалить этот узел, выполнив действия, обратные действиям (2):

Y-(-X[T]; Tf-T-l. (3)