3.3. Моде лирование при помощи изменяемых данных
251
• конструктор (make-queue) возвращает пустую очередь (очередь, в которой нет
ни одного элемента).
• два селектора: (empty-queue? hочередьi) проверяет, пуста ли очередь,
(front-queue hочередьi) возвращает объект, находящийся в голове очереди. Если
очередь пуста, он сообщает об ошибке. Очередь не модифицируется.
• Два мутатора: (insert-queue! hочередьi hэлементi) вставляет элемент в
хвост очереди и возвращает в качестве значения измененную очередь; (delete-queue!
hочередьi) удаляет элемент в голове очереди и возвращает в качестве значения изме-
ненную очередь. Если перед уничтожением элемента очередь оказывается пустой, выво-
дится сообщение об ошибке.
Поскольку очередь есть последовательность элементов, ее, разумеется, можно было
бы представить как обыкновенный список ; головой очереди был бы car этого спис-
ка, вставка элемента в очередь сводилась бы к добавлению нового элемента в конец
списк а, а уничтожение элемента из очереди состояло бы просто во взятии cdr списка.
Однако такая реализация неэффективна, поскольку для вставки элемента нам пришлось
бы просматривать весь список до конца. Поскольку единственный доступный нам ме-
тод просмотра списка — это последовательное применение cdr, такой просмотр требует
Θ(n) шагов для очереди с n членами. Простое видоизменение спискового представлени я
преодолевает э тот недостаток, позволяя нам реализовать операции с очередью так, что-
бы все они требовали Θ(1) шагов; то есть, чтобы число шагов алгоритма не зависело от
длины очереди.
Сложность со списковым представлением возникает из-за необходимости искать ко-
нец списка. Искать приходится потому, что, хотя стандартный способ представления
списк а в виде цепочки пар дает нам указатель на начало списка, легкодоступного ука-
зателя на конец он не дает. Модификация, обходящая этот недостаток, состоит в том,
чтобы представлять очередь в виде списка, и держать еще дополните льный указатель
на его последнюю пару. В таком случае, когда требуется вставить элемент, мы можем
просто посмотреть на этот указатель и избежать за счет этого просмотра всего списка.
Очередь, таким образом, представляется в виде пары указателей, frontptr и rear-
ptr, которые обознач ают, соответственно, первую и последнюю пару обыкновенного
списк а. Поскольку нам хочется, чтобы очередь была объектом с собственной инди ви-
дуальностью, соединить эти два указателя можно с помощью cons, так ч то собствен-
но очередь будет результатом cons двух указателей. Такое представление показано на
рис. 3.19.
Во время определения операций над очередью мы пользуемся следующими процеду-
рами, которые позволяют нам читать и записывать указ атели на начало и конец очереди:
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
Теперь можно реализовать сами операции над очередью. Очередь будет считаться