implement queue by mit-scheme

這是 sicp 3.3.2 節的程式碼

queue.scm

 1 (define (front-ptr queue) (car queue))
 2 (define (rear-ptr queue) (cdr queue))
 3 (define (set-front-ptr! queue item) (set-car! queue item))
 4 (define (set-rear-ptr! queue item) (set-cdr! queue item))
 5 (define (empty-queue? queue) (null? (front-ptr queue)))
 6 (define (make-queue) (cons '() '()))
 7 (define (front-queue queue)
 8   (if (empty-queue? queue)
 9     (error "FRONT called with an empty queue" queue)
10     (car (front-ptr queue))))
11 
12 (define (insert-queue! queue item)
13   (let ((new-pair (cons item '())))
14     (cond ((empty-queue? queue)
15            (set-front-ptr! queue new-pair)
16            (set-rear-ptr! queue new-pair)
17            queue)
18           (else
19             (set-cdr! (rear-ptr queue) new-pair)
20             (set-rear-ptr! queue new-pair)
21             queue))))
22             
23 (define (delete-queue! queue)
24   (cond ((empty-queue? queue)
25          (error "DELETE! called with an empty queue" queue))
26         (else
27           (set-front-ptr! queue (cdr (front-ptr queue)))
28           queue)))
29 
30 (define q1 (make-queue))
31 (insert-queue! q1 5)
32 (insert-queue! q1 6)
33 (insert-queue! q1 7)

我被 cons 的 pair 搞亂, 花了一天才看懂這程式碼。而且很難得的畫了一些圖來說明 (畫這些圖形還真是難倒我, 醜了些, 大家將就看些)。



這是所使用的資料結構, cons 會建立一個 pair, 像上圖的長方形, 有兩個點, 指向另外的 pair。

(define q1 (make-queue))




(insert-queue! q1 5)




(insert-queue! q1 6)

寄件者 sicp-queue

(insert-queue! q1 7)



經過每個圖片與程式碼的對照, 應該可以理解為什麼程式會寫成這個樣子。

L23 的 delete-queue 相對也就很好理解了。

使用這樣的寫法是因為效率的因素, 不需要一次又一次的呼叫 cdr 來取最後的元素, 就算使用 scheme 還是可以兼顧效率的。

若在面試上考 queue 並且不限制語言的話, 用 lisp 系寫出來, 面試官會對你印象深刻吧!