2009/05/17

[scheme]queue(キュー:待ち行列)

WS0797

追記



schemeによる記号処理入門」 P.40

大域変数を使用するもの

(define *queue*
  '())

(define *last*
  '())

(define enqueue
  (lambda (data)
    (cond
     ((null? *queue*)
      (set! *queue* (list data))
      (set! *last* *queue*))
     (else (set-cdr! *last* (list data))
           (set! *last* (cdr *last*))))
  *queue*))

(define dequeue
  (lambda ()
    (cond
     ((null? *queue*) 'empty)
     (else ((lambda (x)
              (set! x (car *queue*))
              (set! *queue* (cdr *queue*))
              x) '())))))
(enqueue 'one)
;; => (one)

(enqueue 'two)
;; => (one two)

(enqueue 'three)
;; => (one two three)

(dequeue)
;; => one

 

大域変数を使用しない(クロージャ)

;; queue with closure
(define make-queue
  (lambda ()
    (let ((queue '())
          (last '()))
    (lambda (msg . args)
          (cond
           ((eq? msg 'enqueue)
            (cond
             ((null? queue)
              (set! queue (list (car args)))
              (set! last queue))
             (else (set-cdr! last (list (car args)))
                   (set! last (cdr last))))
            queue)
           ((eq? msg 'dequeue)
            (cond
             ((null? queue) 'empty)
             (else ((lambda (x)
                     (set! x (car queue))
                     (set! queue (cdr queue))
                     x) '()))))
           ((eq? msg 'len)
            (length queue))
           ((eq? msg 'clear)
            (set! queue '()))
           ((eq? msg 'each)
            (cond
             ((null? args) queue)
             (else (map (car args) queue))))
           (else #f))))))
(define q (make-queue))
;; => q

(q 'enqueue 'one)
;; => (one)

(q 'enqueue 'two)
;; => (one two)

(q 'enqueue 'three)
;; => (one two three)

(q 'enqueue 'four)
;; => (one two three four)

(q 'enqueue 'five)
;; => (one two three four five)

(q 'dequeue)
;; => one

(q 'len)
;; => 4

(q 'each)
;; => (two three four five)

(q 'each (lambda (n)(print n)))
;; => two
;; => three
;; => four
;; => five
;; => (#<undef> #<undef> #<undef> #<undef>)

 

参考



Schemeによる記号処理入門
Schemeによる記号処理入門
posted with amazlet at 09.05.10
猪股 俊光 益崎 真治
森北出版
売り上げランキング: 305671
Amazon.co.jp で詳細を見る

0 件のコメント:

コメントを投稿