곽원영
가입: 2008년 9월 26일 올린 글: 8
|
올려짐: 2008년9월27일 22:20 주제: 2-6 에서 dequeue 에 대해 질문이 있습니다. |
|
|
| 인용: | 큐를 [a1,...,am,b1,...bn] 라고 합시다 (bn이 머리). 이 큐를 두개의 리스트 L과 R로 표현할 수 있습니다:
L = [a1,...,am], R = [bn,...,b1].
한 원소 x를 삼키면 새로운 큐는 다음이 됩니다:
[x,a1,...,am],[bn,...,b1].
원소를 하나 빼고 나면 새로운 큐는 다음이 됩니다:
[a1,...,am][bn-1,...,b1].
뺄때, 때때로 L 리스트를 뒤집어서 R로 같다 놔야하겠습니다. |
입니다.
결국에는 [a1,...,am,b1,..,bn] 에서 dequeue 시에 bn 을 뺀다는 이야기인것 같습니다.
그러기 위해서 때때로 들어간 x (와 L에 있는 element를 순차적으로) R로 옮겨줘야하는데 이 때때로가 언제인지 잘 모르겠습니다.
L의 element의 갯수가 일정이상을 넘었을때인지
아니면 dequeue가 이뤄질때인지
또 옮겨줄때 몇개나 옮겨줘야하는지
아니면 이 모든것이 자유롭게 구현되는지
궁금합니다. |
|