@ Queue - in Ruby일반 큐를 배열로 구현하면 자료가 들어가고 나감에 따라 앞부분의 공간을 못쓰게 되는 단점이 있다. 이를 개선한 게 원형(환형) 큐이다.
환형 큐는 큐의 맨 앞과 맨 끝이 붙어 있는 모양이며, 맨 끝에서 맨 앞으로 가는 경우의 인덱스를 계산하기 위해 front / rear 전진 시에 mod(나머지) 를 사용한다.
특이사항은, 큐가 빈 상태와 꽉 찬 상태를 구분하기 위해 front 가 가리키는 자리를 비워놓고 쓴다는 것이다. 이렇게 함으로써 front 와 rear 가 같을 경우 빈 상태, rear 바로 앞에 front 가 있으면 꽉 찬 상태로 인식할 수 있다.
# Circular Queue Implementation
# Jungtaek Lim(Heart), 2009-03-03
class CircularQueue
def initialize(size)
@memory = []
@front = 0
@rear = 0
@queue_size = size
end
def is_empty
return @front == @rear
end
def is_full
return ((@rear + 1) % @queue_size) == @front
end
def enqueue(data)
return nil if is_full
@rear = (@rear + 1) % @queue_size
@memory[@rear] = data
end
def dequeue
return nil if is_empty
@front = (@front + 1) % @queue_size
return @memory[@front]
end
end
queue = CircularQueue.new(4)
puts queue.enqueue("Data1")
puts queue.enqueue("Data2")
puts queue.enqueue("Data3")
puts queue.enqueue("Data4")
puts queue.dequeue
puts queue.dequeue
puts queue.dequeue
puts queue.dequeue
|
결과>
Data1
Data2
Data3
nil
Data1
Data2
Data3
nil
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Binary Tree - in Ruby (0) | 2009/03/04 |
|---|---|
| Deck(Deque, Double-ended Queue) - in Ruby (0) | 2009/03/04 |
| Circular Queue - in Ruby (0) | 2009/03/04 |
| Queue - in Ruby (4) | 2009/03/04 |
| Stack - in Ruby (0) | 2009/03/03 |
| 간단한 문제...(연속된 숫자 그룹 맺어주기) (0) | 2008/09/23 |
