3.3.2 · 앞과 뒤 포인터

큐는 양 끝을 모두 손에 쥔다.

연결된 가변 큐는 다음에 뺄 항목과 마지막 순서쌍을 각각 가리켜 필요한 끝만 바꿉니다. 양쪽 끝 포인터를 갱신하며 삽입과 삭제가 어떻게 이루어지는지 살펴봅니다.

생각해 볼 질문

삽입을 지역적인 변경으로 만들려면 앞 포인터뿐 아니라 뒤 포인터도 필요한 이유는 무엇일까요?

큐를 연결된 가변 쌍으로 표현하기
삽입할 때 rear에서의 set-cdr! 따라가기
삭제할 때 front 포인터 따라가기
항목이 하나인 큐가 두 포인터를 공유하는 경우 알아보기

삽입은 쌍 하나를 만듭니다. 빈 큐에서는 두 포인터가 모두 그 쌍을 가리킵니다. 비어 있지 않은 큐는 front부터 탐색하지 않고 기존 rear의 cdr을 새 쌍으로 바꾼 다음 rear를 전진시킵니다.

삭제는 연결을 다시 쓰지 않습니다. front를 현재 cdr로 전진시킬 뿐입니다. a, b, c를 삽입하고 한 번 삭제하면 front는 b가 든 쌍을 가리키고 rear는 여전히 c가 든 쌍을 가리킵니다.

SICP 코드UTF-8 641 / 1,048,576바이트

(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))))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

첫 프로그램은 (b c #f)를 반환합니다. 두 번째 프로그램은 (solo solo #t)를 반환합니다.

실행 추적에서 볼 점

비어 있지 않은 각 삽입을 기존 rear가 가리키는 쌍에 연결하는 cdr 변경을 찾으세요. 그런 다음 rear나 front를 전진시키는 바인딩 대입과 이를 구분하세요.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

첫 프로그램에서 한 번 더 삭제하세요. 실행하기 전에 front 값과 rear 값, eq? 결과를 예측하세요.

힌트 보기

두 번째 삭제 후에는 두 포인터가 모두 유일하게 남은 c가 든 쌍을 가리킵니다.

이 수업 완료하기

이 장의 총 21개 수업 중 0개 완료0%