Операция (define

q (make-queue)

(insert-queue! q a) (insert-queue! q b) (delete-queue! q) (insert-queue! q c) (insert-queue! q d) (delete-queue! q)

Результат a

ab b

bc

bcd

cd

Рис. 3.18: Операции над очередью.

•конструктор (make-queue) возвращает пустую очередь (очередь, в которой нет ни одного элемента).

•два селектора: (empty-queue? (очередь)) проверяет, пуста ли очередь, (front-queue (очередь)) возвращает объект, находящийся в голове очереди. Если очередь пуста, он сообщает об ошибке. Очередь не модифицируется.

•Два мутатора: (insert-queue! (очередь) (элемент)) вставляет элемент в хвост очереди и возвращает в качестве значения измененную очередь; (delete-queue! (очередь)) удаляет элемент в голове очереди и возвращает в качестве значения измененную очередь. Если перед уничтожением элемента очередь оказывается пустой, выводится сообщение об ошибке.

Поскольку очередь есть последовательность элементов, ее, разумеется, можно было бы представить как обыкновенный список; головой очереди был бы car этого списка, вставка элемента в очередь сводилась бы к добавлению нового элемента в конец списка, а уничтожение элемента из очереди состояло бы просто во взятии cdr списка. Однако такая реализация неэффективна, поскольку для вставки элемента нам пришлось бы просматривать весь список до конца. Поскольку единственный доступный нам метод просмотра списка - это последовательное применение cdr, такой просмотр требует 0(n) шагов для очереди с n членами. Простое видоизменение спискового представления преодолевает этот недостаток, позволяя нам реализовать операции с очередью так, чтобы все они требовали 0(1) шагов; то есть, чтобы число шагов алгоритма не зависело от длины очереди.

Сложность со списковым представлением возникает из-за необходимости искать конец списка. Искать приходится потому, что, хотя стандартный способ представления списка в виде цепочки пар дает нам указатель на начало списка, легкодоступного указателя на конец он не дает. Модификация, обходящая этот недостаток, состоит в том, чтобы представлять очередь в виде списка, и держать еще дополнительный указатель на его последнюю пару. В таком случае, когда требуется вставить элемент, мы можем просто посмотреть на этот указатель и избежать за счет этого просмотра всего списка.

Очередь, таким образом, представляется в виде пары указателей, front-ptr и rear-ptr, которые обозначают, соответственно, первую и последнюю пару обыкновенного списка. Поскольку нам хочется, чтобы очередь была объектом с собственной индивидуальностью, соединить эти два указателя можно с помощью cons, так что собственно очередь будет результатом cons двух

front-ptr

rear-ptr

Т •--* t

Рис. 3.19: Реализация очереди в виде списка с указателями на начало и конец.

q

b

a

c

указателей. Такое представление показано на рис. 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))

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

(define (empty-queue? queue) (null? (front-ptr queue)))

Конструктор make-queue возвращает в качестве исходно пустой очереди пару, в которой и car, и cdr являются пустыми списками:

(define (make-queue) (cons () ()))

При обращении к элементу в голове очереди мы возвращаем car пары, на которую указывает головной указатель:

(define (front-queue queue) (if (empty-queue? queue)

(error "FRONT вызвана с пустой очередью" queue) (car (front-ptr queue))))

Чтобы вставить элемент в конец очереди, мы используем метод, результат которого показан на рисунке 3.20. Первым делом мы создаем новую пару, car которой содержит вставляемый элемент, а cdr - пустой список. Если очередь была пуста, мы перенаправляем на эту пару и головной, и хвостовой указатели. В противном случае, мы изменяем последнюю пару очереди так, чтобы следующей была новая пара, и хвостовой указатель тоже перенаправляем на нее же.

(define (insert-queue! queue item) (let ((new-pair (cons item ())))

front-ptr

rear-ptr

Т •--* ?

b

Рис. 3.20: Результат применения (insert-queue! q d) к очереди с рисунка 3.19

q

d

a

c

front-ptr

T •--* t

b

rear-ptr

Рис. 3.21: Результат применения (delete-queue! q) к очереди с рис. 3.20.

q

d

a

c

(cond ((empty-queue? queue)

(set-front-ptr! queue new-pair) (set-rear-ptr! queue new-pair) queue)

(else

(set-cdr! (rear-ptr queue) new-pair) (set-rear-ptr! queue new-pair)

queue))))

Чтобы уничтожить элемент в голове очереди, мы просто переставляем головной указатель на второй элемент очереди, а его можно найти в cdr первого элемента (см. рис. 3.21):22

(define (delete-queue! queue) (cond ((empty-queue? queue)

(error "DELETE! вызвана с пустой очередью" queue))

(else

(set-front-ptr! queue (cdr (front-ptr queue))) queue)))

Упражнение 3.21.

Бен Битобор решает протестировать вышеописанную реализацию. Он вводит процедуры в интерпретаторе Лиспа и тестирует их:

22В случае, если первый элемент - одновременно и последний, после его уничтожения головной указатель окажется пустым списком, и это будет означать, что очередь пуста; нам незачем заботиться о хвостовом указателе, который по-прежнему будет указывать на уничтоженный элемент, поскольку empty-queue? смотрит только на голову.