[자료구조 및 프로그래밍] 2. Queue (implement with Array) - 1

이번에는 큐를 배열을 통해 구현하는 과정을 정리하고자 한다.

구현에 앞서 '큐'의 개념을 살펴보자.

큐의 개념

이번에도 구글 번역기로한번 번역부터 해 보았다.

이번에는 번역기가 번역을 해준다!

번역의 결과가 큐를 말 그대로 설명해주고 있다.

 

큐는 '대기줄' 이다.

대기줄의 특성을 생각해보자.

식당에 (학교에서는 교수님이 '하카타분코' 라는 라멘집을 예시로 들어주신다 ㅋㅋ) 손님이 많아서 대기줄이 길게 있다고 할 때,

신규로 오는 손님은 대기줄의 '뒤'에 서게 되고, (push)

식당에 빈자리가 생기면 대기줄 맨 앞에 있던 사람이 들어가게 된다. (pop)

 

큐는 이를 그대로 표방하는 자료구조이다.

먼저 들어왔던 데이터가 먼저 나가는 First In First Out (FIFO) 방식의 자료구조이다.

 

큐는 보통 배열처럼 가로로 길게 늘어선 사각형의 모음으로 자주 표현한다.

데이터를 넣을 때마다 (PUSH) 오른쪽에 데이터가 추가된다.

이렇게 데이터가 추가되는 곳을 back, 또는 rear 라고 표현한다.

 

데이터를 뺄 때는 앞에서 부터 빠진다.

이렇게 데이터가 빠지는 곳을 front 라고 표현한다.

---

큐의 구현 (feat. Array)

이제 큐의 기본 구조를 이해하였으니, 큐를 배열을 이용해서 구현해보자.

스택에서는 데이터가 추가될 위치와, 데이터가 빠질 위치가 데이터가 추가될 위치 -1 로 표현되기 때문에,

데이터의 push, pop 위치를 관리할 변수가 1개만 있어도 괜찮았다.

 

그러나 큐는 데이터가 추가되는 위치와 데이터가 빠지는 위치가 스택과는 다르게 큐의 사이즈와 관련하여 표현되기 때문에,

변수가 반드시 2개 필요하다.

 

(변수를 1개만 이용하는 방법이 존재하지 않는 것은 아니다.

데이터가 빠지는 위치를 0번 인덱스로 고정하고, 데이터가 빠질 때마다 데이터를 한칸씩 앞으로 당겨주면, 데이터가 추가될 위치만 관맇함으로서 변수 하나로 큐를 구현할 수 있다.

그러나 이 경우, 데이터를 뺄 때마다 모든 데이터의 위치를 앞으로 당겨야 하므로, 큐에 담긴 데이터의 양이 많아질 수록 처리 시간이 증가한다. 이 포스팅에서는 변수를 2개 이용해 데이터의 추가와 삭제를 적은 연산으로 빠르게 처리하도록 구현해보도록 하겠다.)

 

우선 데이터가 빠지는 front 위치와 데이터가 추가되는 back 위치를 관리할 변수 2개를 선언하고,

큐 데이터를 담을 사이즈 N 짜리 배열을 선언하자.

Q[N]: Array of Size N;
init: front, back;

front 와 back 값을 어떻게 정의하는지에 따라 세부적인 구현에는 조금씩 차이가 생긴다.

 

front 와 back 을 다음과 같이 정의해보자.

front : 현재 존재하는 데이터의 가장 빠른 인덱스, 데이터를 뺄 때는 front 위치의 데이터를 뺀다.

back : 데이터가 추가될 인덱스. 즉, 현재 존재하는 데이터의 가장 마지막 인덱스 + 1, 데이터를 추가할 때는 back 위치에 데이터를 추가한다.

 

이제 이 정의를 토대로 일반적인 상황에서의 기능을 구현해보자.

push 는 현재 back 이 가리키는 위치에 데이터를 추가하고, back 변수의 값을 +1 하면 된다.

push(x) {
    Q[back] <- x;
    back++;
}

pop 은 현재 front 가 가리키는 위치의 데이터를 pop 하고 front 변수의 값을 +1 하면 된다.

pop() {
    x <- Q[front];
    front++;
    return x;
}

이제 특수한 상황을 생각해보자.

 

먼저 push 를 할 수 없는 overflow 상황을 생각해보면,

overflow 를 할 수 없는 상황은 back 이 가리키는 인덱스가 배열의 마지막까지 넘어가는 경우일 것이다.

이를 처리하면 아래와 같이 된다.

push(x) {
    if (back >= N) // back의 인덱스가 N 이상이라면, 더 이상 배열에 추가할 수 없다.
        OVERFLOW!
        
    Q[back] <- x;
    back++;
}

그리고 push 의 기능을 고려해볼 때, back 변수의 초기화를 어떻게 해야 할 지도 알 수 있다.

back 변수가 의미하는 것은 앞으로 데이터가 추가될 위치이고, 초기 아무 데이터가 없을 때는 0번 인덱스에 데이터를 넣는 것이 맞다.

따라서 back 변수는 0으로 초기화 되어야 한다.

init: front, back
back <- 0

 

다음으로 pop을 할 수 없는 상황을 생각해보자.

pop을 할 때는, 현재 front 가 가리키는 곳을 pop을 하는데, pop을 하고나서 front 의 값이 증가하는 것에 중점을 두고 생각해보자.

그렇다면 현재 push 한 횟수보다 더 많은 pop 을 하는 것이 안된다는 것을 알 수 있다.

push 한 횟수는 back 변수의 값과 같다. back 변수가 1 이면 1번 푸쉬해서 앞으로 1번 인덱스에 값을 넣겠다는 의미이다.

 

우선 front 변수는 현재 front 위치에 있는 값을 바로 꺼내오고, 그 다음에 front 값을 증가시키므로,

데이터가 반드시 존재하는 상황에서 pop 이 이루어짐을 고려하면 front 변수는 0으로 초기화 되는 것이 맞다.

만약 front 변수를 -1 로 초기화를 한다면 -1 인덱스에는 접근할 수 없으니, front 변수 값을 1 증가시킨 이후에 pop을 해야하는데,

이는 현재 구현한 pop의 기능과 맞지 않다.

init: front, back
back <- 0
front <- 0

이제 초기 상태에서는 pop을 할 수 없어야 한다는 것을 고려해보면, 언제 pop을 할 수 없는지 조건을 알 수 있다.

바로 front >= back 인 상황에서는 pop을 할 수 없다.

push 한 상황보다 더 많이 pop을 하는 상황은 큐가 비어있는데, pop을 하는 것과 같다. (underflow)

 

따라서 아래와 같이 처리하면 된다.

pop() {
    if (front >= back)
        UNDERFLOW!
        
    x <- Q[front];
    front++;
    return x;
}

이것으로 배열을 이용한 큐의 구현이 완료되었다.

만약 큐의 size가 필요하다면 큐의 size 는 back - front 로 알 수 있다.

 

하지만 이렇게 구현한 큐에는 한가지 문제점이 있다.

바로 n번 push 하고 나서, n 번 pop을 하면, 큐가 비어있음에도 더이상 push를 할 수 없기 때문이다.

즉, 배열 앞쪽의 메모리 공간이 비어있음에도 이를 전혀 활용하지 못하고 n번의 push 만 이루어지면 더 이상 push 를 하지 못한다.

 

다음 포스팅에서는 이 문제를 해결하기 위해 Circular Queue 를 배열로 구현 해볼 것이다.