Д. Кнут - Искусство программирования том 1 (1119450), страница 66
Текст из файла (страница 66)
Стеки особенно полезны при обработке языков с вложенной структурой, например для языков программирования, арифметических выражений и конструкций "БсЬасЬсе1эагэе" немецкого языка. Вообще, стеки чаще всего встречаются при работе с явными и неявными рекурсивными алгоритмами, которые более подробно рассматриваются в главе 8.
Для описания алгоритмов обработки этих структур обычно используется специальная терминология. Например, объект кладут на верх стека или снимают верхний элемент стека (рис. 3, (а)). Доступ к элементу, находящемуся внизу стека, наиболее затруднителен"; и его нельзя удалить до тех пор, пока не будут удалены все остальные элементы стека. (Часто говорят, что объект прогаалкиваетсл (рива) вниз стека и выталкиваетсл (рор) на верх стека при удалении самого верхнего элемента. Эта терминология возникла от аналогии со стопкой тарелок в кафе. Краткость английского написания слов "протолкнуть" (рцэЬ) и "вытолкнуть" (рор) обладает определенными преимуществами, но зти термины часто неверно трактуются, как движение всего списка целиком в памяти компьютера.
На самом деле физически ничто никуда не проталкивается, а объекты всего лишь добавляются сверху стека точно так, как при укладке сена в стоге или коробок в стопке.) По отношению к очередям применяют понятия начало (~гоп1) и конец (геаг) очереди. Объекты вставляются в конце очереди и проталкиваются по ней до тех пор, пока не достигнут начала очереди (рис.
3, (Ь)). При работе с деками используют понятия левый (1еуг) и правый (г1дЫ) концы (рис. 3, (с)). Концепции верха, низа, начала и конца иногда применяют по отношению к декам, которые используются в качестве стеков или очередей, но нет никаких стандартных соглашений в отношении того конца, с которого они должны располагаться: с правого или левого.
Таким образом, мы выяснили, что при создании алгоритмов достаточно удобно применять все богатое разнообразие языка: "верх-низ" (цр-Йояп) — для стеков, "ожидание в очереди" (яаЖпй 1и 11пе) — для очередей и "слева-справа" (1ей-г13Ьг)— для деков. При работе со стеками и очередями удобно использовать некоторые дополнительные обозначения. Например, обозначение А сх указывает, что элемент х вставлен сверху стека А (если А — это стек) или элемент х вставлен в конце очереди (если А — это очередь). Аналогично (2) хс А используется для обозначения того, что переменная х приравнивается к значению верхнего элемента стека А или начального элемента очереди А, т. е.
это значение, которое удаллетсл из А. Обозначение (2) не имеет смысла, если А пусто, т. е, когда А не содержит значений. Если А †непуст стек, то (3) 1ор(А) можно использовать для обозначения самого верхнего его элемента. УПРАЖНЕНИЯ 1. [06) Дек с ограниченным вводом является линейным спискам, в котором элементы могут вставляться на одном конце, а удаляться — с любого конца, Очевидно, что дек может функционировать, как стек нлн очередь, если его элементы всегда будут удаляться с одного вз двух его концов.
Может ли дек с ограниченным выводом функционировать, как стек иля очередь? 2. [15) Допустим, что четыре вагана с номерами 1, 2, 3 и 4 (слева направо) расположены со стороны ввода вагонов железнодорожных путей (см. рис. 1). Предположим, что выполняется такая последовательность действий (которая совпадает с направлением стрелок на этой схеме и не дбпускает "перепрыгивания" через вагоны): (л) поместить вагон 1 в стек; (й) поместить вагон 2 в стек;(1й) вывести вагон 2 из стека;(1 )поместить вагон 3 в стек; (ч) поместить вагон 4 в стек;(ч1) вывести нагон 4 из стека;(чй) вывести вагон 3 из стека; (чш) вывести вагон 1 из стека.
После выполнения этих действий исходный порядок вагонов, 1234, станет иным, 2431. Целью этого и след ющих упражнений является выяснение, какие перестановки допустимы в стеках, очередях и деках. Можно ли выполнить такую перестановку шестл7 пронумерованных вагонов, чтобы из исходного порядка 123456 получить порядок 325641? Можно ли поменять порядок вагонов так, чтобы он был равен 154623? (Если можно, то как именно?) 3. [25] Действия (!) — (чш) в предыдущем упражнении можно записать в более кратком виде с помощью кода ЯЯХЯЯХХХ, где Я обозначает "ввести вагон в стек", а Х вЂ” "вывести вагон из стека".
Некоторые последовательности действий Я и Х бессмысленны, поскольку на соответствующих путях может совсем не быть вагонов. Например, последовательность действий ЯХХЯЯХХЯ не может быть выполнена, так как предполагается, что в исходном состоянии стек пуст. Назовем последовательность действий Я и Х двпусоламоа, если она содержит и действий Я и н действий Х и если в ней нет никаких бессмысленных действий, Сформулируйте правило, с помощью которого было бы легка различать допустимые и недопустимые последовательности действий. Покажите, что различные допустимые последовательности действий приводят к разным перестановкам. 4. [МЦ] Найдите простую формулу для а, т.
е. для количества перестановок среди и элементов, которые могут быть получены с помощью стека из упр. 2. б. [М20) Покажите, что с помощью стека можно получить перестановку рлрэ... р„исходной последовательности 12... и только в случае, если не существует таких индексов э<у<6,чтор <рл<рь 6. [00) Рассмотрим задачу из упр, 2, в которой очередь используется вместо стека. Какие перестановки 12...
и можно получить с помощью очереди? 7. [25] Рассмотрим задачу из упр. 2, в которой вместо стека используется дек. (а) Наидите такую перестановку последовательности 1234, которая может быть получена с помощью дека с ограниченным вводом, но не может быть получена с помощью дека с ограниченным выводом. (Ь) Найдите такую перестановку последовательности 1234, которая может быть получена с помощью дека с ограниченным выводом, но не может быть получена с помощью дека с ограниченным вводом, [Как следствие из (а) и (Ь) между деками с ограниченным вводом и выводом существует определенная разница.] (с) Найдите такую перестановку последовательности 1234, которая не может быть получена ни с помощью дека с ограниченным вводом, ни с помощью дека с ограниченным выводом.
8. [22] Существуют ли какие-либо перестановки 12... и, которые не могут быть пачучены с помощью дека, не имеющего ни ограниченного ввода, ни ограниченного вывода? 9. [М20] Пусть 6„— количество перестановок среди и элементов, которые могут быть получены с помощью дека с ограниченным вводом. (Обратите внимание, что 6л = 22, как показано в упр. 7.) Покажите, что 6„также является количеством перестановок среди н элементов, которые могут быть получены с помощью дека с ограниченным выводом. 10. [М25] (См. упр. 3.) Пусть Я, ле и Х обозначают соответственно операции ввода элемента слева, ввода элемента справа и вывода элемента слева в деке с ограниченным выводом. Например, применив последовательность действий О()ХЯХЯХХ к исходной последовательности символов 1234, получим 1342.
Последовательность действий ЯХ()ЯХЯХХ приведет к такому же результату. Найдите такое опрйделепие понятия дооусгпимой последовательности символов Я, (4 я Х, чтобы выполнялось следующее требование: каждая перестановка п элемеятов, которую можно получить с помощью дека с ограниченным выводом, должна соответствовать только одной допустимой последовательности. ь 11. [М40) Из упр.
9 я 10 получаем, что Ь„является количеством допустимых последовательностей длины 2п. Найдите производящую фуякцяю 2 „о 6„з" в "замкнутом вппе". 12. [НМ34) Вычислите эсимптотические значения величин а„и 6„яз упр. 4 и 11. 13. [М48] Сколько перестановок среди и элементов можнЗ получить с помощью дека? [В статье Розенстиля и Таржана, 3. А!бопеЬпм 5 (1984), 389-390, приводится алгоритм, в котором за 0(п) шагов выясняется допустимость данной перестановки.) ь 14. [йб) Предположим, что в качестве структур данных используются только стеки.
Как наиболее эффективным образом воплотить очередь с помощью двух стеков? 2.2.2. Последовательное распределение Наиболее простой и естественный способ хранения линейного списка в памяти компьютера заключается в расположении элементов в последовательных ячейках, при котором один узел списка следует сразу же за другим. Тогда АТОС(Х [у + 13 ) = 1ОС(Х(у) ) + с, где с — количество слов в одном узле. (Обычно с = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
