큐는 양 끝을 모두 손에 쥔다.
연결된 가변 큐는 다음에 뺄 항목과 마지막 순서쌍을 각각 가리켜 필요한 끝만 바꿉니다.
삽입을 지역적인 변경으로 만들려면 앞 포인터뿐 아니라 뒤 포인터도 필요한 이유는 무엇일까요?
- Represent a queue as linked mutable pairs
- Follow set-cdr! at the rear during insertion
- Follow the front pointer during deletion
- Recognize when a one-item queue shares both pointers
Insertion creates one pair. An empty queue makes both pointers name that pair. A nonempty queue changes the old rear cdr to the new pair and then advances rear, without searching from front.
Deletion does not rewrite the links. It advances front to its current cdr. After inserting a, b, and c and deleting once, front names the b pair while rear still names the c pair.
(let ((front '()) (rear '()))
(let ((insert!
(lambda (item)
(let ((node (cons item '())))
(if (null? front)
(begin (set! front node) (set! rear node))
(begin (set-cdr! rear node) (set! rear node)))
front)))
(delete!
(lambda ()
(if (null? front)
'empty
(begin
(set! front (cdr front))
(if (null? front) (set! rear '()) #f)
front)))))
(insert! 'a)
(insert! 'b)
(insert! 'c)
(delete!)
(list (car front) (car rear) (eq? front rear))))- 출력
- —
- 값
- —
- 진단
- —
The first program returns (b c #f). The second returns (solo solo #t).
Find the cdr mutation that links each new nonempty insertion to the old rear pair. Then distinguish it from the binding assignment that advances rear or front.
힌트를 보기 전에 프로그램을 바꿔 보세요.
Delete once more from the first program. Predict the front value, rear value, and eq? result before running it.
힌트 하나 보기
After the second deletion, both pointers name the one remaining c pair.