3.3.2 · Указатели начала и конца

Очередь с прямым доступом к обоим концам

Связная очередь хранит указатель на следующий элемент для удаления и указатель на последнюю пару, поэтому операция меняет только свой конец.

Вопрос для размышления

Почему для локальной вставки за константное время требуется указатель rear так же, как и указатель front?

Представление очереди в виде связанных изменяемых пар
Отслеживание set-cdr! для позиции rear при вставке
Отслеживание указателя front при удалении
Определение случая, когда очередь из одного элемента разделяет оба указателя

Вставка создает одну пару. В пустой очереди оба указателя начинают указывать на эту пару. В непустой очереди cdr старой пары rear заменяется на новую пару, после чего указатель rear сдвигается вперед без поиска от front.

Удаление не перезаписывает связи. Оно сдвигает front к его текущему cdr. После вставки a, b и c и одного удаления front указывает на пару b, тогда как rear по-прежнему указывает на пару c.

Код SICP641 из 1,048,576 байт UTF-8

(let ((front '()) (rear '()))
  (let ((insert!
         (lambda (item)
           (let ((node (cons item '())))
             (if (null? front)
                 (begin (set! front node) (set! rear node))
                 (begin (set-cdr! rear node) (set! rear node)))
             front)))
        (delete!
         (lambda ()
           (if (null? front)
               'empty
               (begin
                 (set! front (cdr front))
                 (if (null? front) (set! rear '()) #f)
                 front)))))
    (insert! 'a)
    (insert! 'b)
    (insert! 'c)
    (delete!)
    (list (car front) (car rear) (eq? front rear))))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (b c #f). Вторая программа возвращает (solo solo #t).

На что обратить внимание в трассе

Найдите мутацию cdr, которая связывает каждую новую непустую вставку со старой парой rear. Затем отличите ее от присваивания связывания, которое сдвигает rear или front.

Попробуйте сами

Измените программу и сравните результат.

Выполните удаление из первой программы еще один раз. Предскажите значение front, значение rear и результат eq? перед запуском.

Показать подсказку

После второго удаления оба указателя указывают на одну оставшуюся пару c.

Завершить этот урок

В этой главе пройдено 0 из 21 урока0%