闲来无事，用Scheme实现一个FIFO队列，数据从末端插入，从前端删除或者查询。
队列可以看成是由下面一组操作定义的结构：
- 构造函数
(make-queue) 返回一个空队列
- 选择函数
(empty-queue? <queue> ) 检查队列是否为空 (front-queue <queue> ) 返回最早进入队列的数据，其不会修改队列 (length-queue <queue> ) 返回队列长度
- 改变函数
(insert-queue! <queue> <item> ) 将数据插入末端 (delete-queue! <queue> ) 删除列头的数据
- 打印函数
(print-queue <queue>)
(module FIFO-QUEUE
(make-queue empty-queue? front-queue insert-queue! delete-queue! length-queue print-queue)
(define front-ptr (lambda (q) (caar q)))
(define set-front-ptr! (lambda (q item) (set-car! (car q) item)))
(define rear-ptr (lambda (q) (cdar q)))
(define set-rear-ptr! (lambda (q item) (set-cdr! (car q) item)))
(define make-queue (lambda () (cons (cons '() '()) 0)))
(define empty-queue? (lambda (q) (null? (front-ptr q))))
(define front-queue (lambda (q) (if (empty-queue? q) (error "FRONT called with an empty queue" q) (car (front-ptr q)))))
(define (insert-queue! q item)
(let ((new-pair (cons item '())))
(if
(empty-queue? q)
(begin (set-front-ptr! q new-pair) (set-rear-ptr! q new-pair) (set-cdr! q (+ 1 (cdr q))) q)
(begin (set-cdr! (rear-ptr q) new-pair) (set-rear-ptr! q new-pair) (set-cdr! q ( + 1 (cdr q))) q)
)
)
)
(define delete-queue!
(lambda (q)
(if
(empty-queue? q)
(error "DELETE! called with an empty queue" q)
(begin (set-front-ptr! q (cdr (front-ptr q))) (set-cdr! q (- (cdr q) 1)) q)
)
)
)
(define length-queue (lambda (q) (cdr q)))
(define print-queue (lambda (q)
(if (empty-queue? q) '() (front-ptr q))
))
)
前4个过程是用于内部的帮助函数，队列维护两个指针，一个指向列头（front-ptr）,一个指向列尾（rear-ptr），这样可以弥补原生的set-car!和set-cdr!的不足。
> (load "/path/to/FIFO-QUEUE.scm") ;;加载FIFO-QUEUE模块
> (import FIFO-QUEUE)
> (define q (make-queue))
> (insert-queue! q 1) ;; (((1) 1) . 1), 最后一个数字1表示队列长度, 在队列有删除或者插入时，及时修改该值，为了在取队列长度时减小开销，否则要遍历一次才行
> (insert-queue! q 2) ;; (((1 2) 2) . 2)
> (insert-queue! q 3) ;; (((1 2 3) 3) . 3)
> (insert-queue! q 4) ;; (((1 2 3 4) 4) . 4)
> (delete-queue! q) ;; (((2 3 4) 4) . 3)
> (delete-queue! q) ;; (((3 4) 4) . 2)
> (front-queue q) ;; 3
> (length-queue q) ;; 2
