큐

큐Queue는 먼저 들어온 데이터를 먼저 처리FIFO, First In First Out하는 데 사용하는 자료 구조다. 큐는 사람들이 차례로 줄을 서 있고, 줄의 제일 앞에 서 있는 사람부터 자기 일을 처리하는 모습을 연상하면 된다. 새로 도착한 사람은 줄의 맨 뒤에 서서 기다린다.

큐는 다음 세 가지 함수로 구현한다.

• Enqueue : 줄의 맨 뒤에 데이터를 추가한다.

• Dequeue : 줄의 맨 앞에 있는 데이터를 가져온다. 가져온 데이터는 줄에서 빠진다.

• Size : 줄의 길이, 즉 자료 구조 내에 저장된 데이터의 수를 반환한다.

이 세 가지 함수를 지원하는 큐를 작성해보자.

> q <- c()
> q_size <- 0
> enqueue <- function(data) {
+ q <<- c(q, data)
+ q_size <<- q_size + 1
+ }
> dequeue <- function() {
+ first <- q[1]
+ q <<- q[-1]
+ q_size <<- q_size - 1
+ return(first)
+ }
> size <- function() {
+ return(q_size)
+ }

위 코드에서 큐에 저장될 데이터는 벡터 q를 사용해 저장하고 있다. q_size는 큐에 저장된 데이터 수를 기록하는 목적으로 사용한다.

함수 enqueue( )는 q에 이미 저장되어 있는 데이터에 인자로 받은 데이터를 추가하여 다시 변수 q에 할당한다. 이때 <<-를 사용해 전역 변수에 있는 q를 직접 접근하게 했다. 마지막으로 q_size의 값을 1 증가시킨다.

함수 dequeue( )는 q에 저장된 데이터 중 첫 번째 요소를 first에 저장하고, q에는 이 데이터를 제외한 데이터를 저장한 다음 first를 반환한다. 이때 q_size가 1 감소한다.

함수 size( )는 q의 길이인 q_size를 반환한다.

위 코드는 다음과 같이 사용할 수 있다.

> enqueue(1)        # 1이 줄의 끝에 선다.
> enqueue(3)        # 3이 줄의 끝에 선다.
> enqueue(5)        # 5가 줄의 끝에 선다.
> print(size())     # 줄의 길이는 3이다.
[1] 3
> print(dequeue())  # 첫 번째로 대기 중인 데이터인 1을 가져온다.
[1] 1
> print(dequeue())  # 두 번째로 대기 중인 데이터인 3을 가져온다.
[1] 3
> print(dequeue())  # 세 번째로 대기 중인 데이터인 5를 가져온다.
[1] 5
> print(size())     # 데이터가 없어 크기가 0이다.
[1] 0