3.3.2 キューの表現
キューの実装
(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))) (define (make-queue) (cons '() '())) (define (front-queue queue) (if (empty-queue? queue) (error "FRONT called with an empty queue" queue) (car (front-ptr queue)))) (define (insert-queue! queue item) (let ((new-pair (cons item '()))) (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)) ) ) (define (delete-queue! queue) (cond ( (empty-queue? queue) (error "DELETE! called with an empty queue" queue)) (else (set-front-ptr! queue (cdr (front-ptr queue))) queue)))
演習問題
Exercise 3.21
実際のQueueの状態をみるためのprint-queueの実装
二つ目のやつは、O(1)で最後のポインタにアクセスするためにあるやつ
(define q1 (make-queue)) (print q1) (insert-queue! q1 'a) (print q1) (insert-queue! q1 'b) (print q1) (delete-queue! q1) (print q1) ;(()) ;((a) a) ;((a b) b) ;((b) b) (define (print-queue queue) (print (front-ptr queue)) )
テスト
(define q1 (make-queue)) (print-queue q1) (insert-queue! q1 'a) (print-queue q1) (insert-queue! q1 'b) (print-queue q1) (delete-queue! q1) (print-queue q1) ;() ;(a) ;(a b) ;(b)
consを使ってキューを表現しているため、 queueオブジェクトをprintすると、先頭ポインタ + 最後のポインタが表示されてしまう。 キューの状態だけみたいのであれば、先頭ポインタからの後続データ構造だけを表示すれば良い。
Exercise 3.22
キューは、ポインタのペアとして表現する以外に、 局所状態を持つ⼿続きとして構築することもできる。 局所状態は通常のリストの先端と終端へのポインタからなる。 make-queue の定義を完成させ、この表現によるキューの演算を実装せよ。
(define (make-queue) (let ( (front-ptr '()) (rear-ptr '()) ) (define (set-front-ptr! item) (set! front-ptr item)) (define (set-rear-ptr! item) (set! rear-ptr item)) (define (empty-queue?) (null? front-ptr)) (define (front-queue) (if (empty-queue?) (error "FRONT called with an empty queue" queue) (car front-ptr)) ) (define (insert-queue! item) (let ((new-pair (cons item '()))) (cond ( (empty-queue?) (set-front-ptr! new-pair) (set-rear-ptr! new-pair) ) (else (set-cdr! rear-ptr new-pair) (set-rear-ptr! new-pair) queue)) ) ) (define (delete-queue!) (cond ( (empty-queue?) (error "DELETE! called with an empty queue" queue)) (else (set-front-ptr! (cdr front-ptr))))) (define (print-queue) (print front-ptr)) (define (dispatch m) (cond ((eq? m 'front-queue) front-queue) ((eq? m 'empty-queue?) empty-queue?) ((eq? m 'insert-queue!) insert-queue!) ((eq? m 'delete-queue!) delete-queue!) ((eq? m 'print-queue) print-queue) )) dispatch))
テスト
(define queue (make-queue)) ((queue 'insert-queue!) 'a) ((queue 'print-queue)) ((queue 'insert-queue!) 'b) ((queue 'print-queue)) (print ((queue 'front-queue))) ((queue 'delete-queue!)) ((queue 'print-queue)) ((queue 'delete-queue!)) ((queue 'print-queue)) ;((queue 'delete-queue!)) ;((queue 'print-queue)) ;(a) ;(a b) ;a ;(b) ;() ;*** ERROR: DELETE! called with an empty queue #<closure ((make-queue dispatch) m)> ; While loading "./3.3.2.scm" at line 138 ;Stack Trace:
Execise 3.23
両端キュー (deque)(“double-ended queue”) は、先端と終端のどちらに対しても項⽬の挿⼊と削除が⾏える列である。 deque に対する演算は、 コンストラクタ make-deque、述語 empty-deque?、 セレクタ front-deque、rear-deque、 ミューテータ front-insert-deque!,rear-insert-deque!, front-deletedeque!, rear-delete-deque! である。 ペアによって deque を表現するやり⽅を⽰せ。また、演算を実装せよ。 全ての演算は Θ(1)ステップで完了しなければならない。
Schemeでかく能力がなかったのでPythonで書いた(´・ω・｀)
def ex_3_23(): class Item: def __init__(self, value): self.value = value self.prev = None self.next = None def __repr__(self): return '<Item {}>'.format(self.value) class Deque: def __init__(self): self.front = None self.rear = None def empty_queue(self): return self.front is None # Selector def front_deque(self): return self.front.value def rear_deque(self): return self.rear.value # Mutator def front_insert_deque(self, value): item = Item(value) if self.front: item.next = self.front self.front.prev = item else: self.rear = item self.front = item def rear_insert_deque(self, value): item = Item(value) if self.rear: item.prev = self.rear self.rear.next = item else: self.front = item self.rear = item def front_delete_queue(self): if self.front is None: raise Exception('Queue is empty.') if self.front is self.rear: self.rear = None self.front = self.front.next if self.front: self.front.prev = None def rear_delete_queue(self): if self.rear is None: raise Exception('Queue is empty.') if self.front is self.rear: self.front = None self.rear = self.rear.prev if self.rear: self.rear.next = None def print_queue(self): q = self.front a = [] while q is not None: a.append(q.value) q = q.next print(a) deque = Deque() deque.front_insert_deque(1) deque.front_insert_deque(2) deque.print_queue() # [2, 1] deque.rear_insert_deque(3) deque.print_queue() # [2, 1, 3] deque.front_delete_queue() deque.print_queue() # [1, 3] deque.rear_delete_queue() deque.print_queue() # [1] deque.rear_delete_queue() # deque.rear_delete_queue() # Exception: Queue is empty. ex_3_23()
