- TAOCP/InformationStructures
''새 원소 넣기(To place a new element Y on top)
''새 원소 넣기(inserting an element at the rear of the queue)
맨 앞 원소 빼기(removing the front node)
하지만 공간낭비가 무한할 수 있다.( F, R이 계속증가하기 때문이다.) 따라서 이런 문제(the problem of the queue overrunning memory)를 해결하려면, M개의 노드(X[1]...X[M])가 순환하도록 한다.
''if R = M then R ← 1, otherwise R ← R + 1; X[R] ← Y.
if F = M then F ← 1, otherwise F ← F + 1; Y ← X[F].''
AnswerMe 그렇다면 새 원소를 넣으면 X[2]부터 들어간다는 건가? --[Leonardong]
가능한 공간에 리스트가 두 개 있다면 (고정된)bottom을 같이 쓸 수 있다. (p.246 그림 참고) 이런 경우 두 리스트가 메모리를 모두 써버릴 때까지 오버플로우는 생기지 않는다. 이런 형태는 매우 자주 쓰인다.
하지만 리스트가 더 많으면 bottom이 움직일 수 있어야 한다.(we must allow the "bottom" elements of the lists to change therir positions.) MIX에서 I번째 한 WORD를 rA에 가져오는 코드는 다음과 같다.
여기서 i번째 스택에서 오버플로우가 생기면 메모리 재배치(repack memory)를 할 수 있다. 몇가지 방법이 있는데 지금부터 자세히 알아보자.
a) ''''위로 한칸씩 밀기(moving things up)'''
b) ''''아래로 한칸씩 밀기(moving things down)''' a)에 해당하는 k가 없을 경우
한 번 메모리 재배치를 할 때마다 공간을 적당히 마련하는 방법도 가능하다.( 그러나 이해하지 못했다.p.250에 중간에 보면 위 알고리즘(Algorithm G나 R)과 비슷한 동적 메모리 할당 알고리즘의 수학적 분석은 매우 어렵다고 나와있다. )
Found 1 matching page out of 7540 total pages
You can also click here to search title.
