25. Queue

지난 시간에는 Stack에 대해 알아보았다.

 

이번에는 Stack과 같이 배열 기반의 자료구조 중 하나인 Queue에 대해 알아보자.

 

Queue역시 Stack과 마찬가지로 배열구조의 자료구조이다.

 

그러나, Queue는 Stack과는 다르게 먼저 넣으면 가장 먼저 나오게 되는 선입선출(First in First out)구조로 되어있다.

 

선입선출 구조는 가장먼저 넣은 값이 가장 먼저 나오게 되는 구조다.

 

우리가 은행에서 업무를 보기 위해 번호표를 뽑고 기다리는데, 나중에 번호표를 뽑은 사람이 나보다 먼저 업무를 보는 것은 굉장히 불합리하지 않은가?

 

Queue도 이와 같다. 몇몇 멀티플레이 게임에서 매칭 대기열을 얘기할 때, 큐를 돌린다. 큐를 잡는다. 라는 말을 쓰곤 하는데, 이를 떠올리면 좋을 것 같다.

 

 

 

 

 

그런데 생각해보자. Queue는 배열 기반의 자료구조이고, 배열은 선형구조로 되어있다.

 

그런데 선입선출을 구현하려면, 가장 처음으로 입력했던 데이터를 내보내야하고, 그렇게 되면 맨 첫 자리가 남기 때문에, 뒤에있는 모든 데이터가 한 칸씩 앞으로 이동해야한다.

 

그래야 내보낸 데이터의 빈자리를 채울 새로운 데이터를 저장할 자리가 마련되기 때문이다.

 

크기가 작지 않은 배열이라면, 데이터를 삽입하고 사출할 때 마다 어마어마한 연산을 감당해야 할 것이다.

 

Queue는 이러한 선형적 구조가 갖는 문제점을 보완하기 위해 순차열로 구현되어있다.

 

 

 

 

 

 

 

 

 

순차열은 무엇일까?

 

순차열은 순환형 구조로 되어있는 배열로, 선형. 즉, 일직선으로 늘어놓은 것이 아닌 서로를 마주보며 빙글빙글 돌아갈 수 있게 만들어져 있는 배열이다.

 

혹시 비즈 목걸이나 비즈 팔찌등을 만들어본 적이 있는가?

 

우리가 비즈 목걸이나 비즈 팔찌를 만들기 위해선 일단 목걸이 줄에 순서대로 비즈를 끼워 넣어야 했다.

 

하나씩 하나씩 순서대로 비즈를 끼워 넣으면, 결국 맨 첫번째 넣은 비즈와 맨 마지막에 넣은 비즈가 만나 예쁜 비즈 목걸이가 되지 않는가?

 

이러한 구조로 되어있는 것이 바로 순차열, Queue다.

 

 

 

 

 

 

비즈의 예시를 다시 가져오자면, 비즈 목걸이에 비즈를 끼울 때 마다 앞으로 넣을 비즈들의 위치가 점점 뒤로 밀려나지 않는가?

 

Queue도 마찬가지이다.

 

Queue의 이해를 돕기 위해, 머리와 꼬리라는 말을 채택하겠다.

 

Queue에 저장되어있는 데이터가 나오는 곳이 머리고, Queue에 새로운 데이터를 집어넣는 곳이 꼬리라고 가정해보자.

 

맨 처음에는, 머리와 꼬리의 위치가 서로 같다. 마치 꼬리를 문 뱀의 형상처럼 말이다.

 

Queue가 생성될 때, 생성자를 통해 머리와 꼬리의 위치가 서로 같게끔 초기화된다.

 

그 후 Queue에 데이터를 삽입하려고 하면, 현재 꼬리위치에 새 데이터값을 집어넣고, 꼬리는 그보다 한 칸 더 뒤로 가서 다음 자료가 들어갈 빈 자리를 가리킨다.

 

 

 

 

 

 

삽입할때와 반대로, 데이터를 내보낼 때는 머리가 움직인다.

 

머리에서 현재 머리가 가리키고 있는 값을 내보낸 후, 머리의 위치도 꼬리 쪽으로 한 칸 이동한다.

 

이러한 방식으로 비즈 목걸이에 비즈를 끼워 넣듯 계속해서 데이터가 저장되게된다.

 

 

 

 

 

 

 

 

 

 

 

이 후, 데이터의 삽입과 사출이 반복되면서 머리와 꼬리의 위치는 서로 이동하며 빙글빙글 데이터의 삽입 사출이 진행된다.

 

그런데 이렇게 머리와 꼬리가 움직이면, 배열의 구조적 특성상 마지막 인덱스나 첫번째 인덱스에 도달하게 될 것이다.

 

이런 상황에서는, 머리와 꼬리가 반대편으로 이동하여 데이터 삽입 및 사출을 계속 진행하게된다.

 

 

 

 

 

예를들어, 배열의 크기가 10인 배열이 있다고 가정해보자.

 

꼬리는 계속해서 데이터를 삽입하면서 끝내 10번째 인덱스에 도달했다. 더 이상 갈 곳이 없다!

 

그런데 마침, 머리가 맨 첫번째 인덱스에 저장되어있는 데이터를 뱉어낸 적이 있었기 때문에 그 자리가 비었다.

 

그래서 꼬리는 그곳으로 돌아가 다시 거기서부터 데이터 삽입을 시작하게 되는 것이다.

 

 

 

 

 

이런 식으로 데이터 삽입과 사출을 진행하다가 머리가 꼬리와 부딪히기 직전에. 그러니까 넣을 수 있는 데이터 공간이 한 칸 뿐일 때에, Queue가 가득 찼다고 알린다.

 

비즈 목걸이를 만들 때도, 비즈 목걸이의 실을 묶을 자리를 남겨두지 않으면 묶을 수 없듯, Queue 역시 머리와 꼬리가 서로 붙어버리면 어디가 시작이고 어디가 끝인지를 알 수 없게 되버리기 때문이다.

 

이렇듯 머리와 꼬리는 Queue가 비어있는지, 가득 차있는 지를 알려준다.

 

 

 

 

Queue의 개념에 대해선 모두 다루었으니, 이제 직접 사용해보자.

 

 

 

static void Main(string[] args)
{
    Queue<int> q = new Queue<int>();

    q.Enqueue(1);
    q.Enqueue(2);
    q.Enqueue(3);
    q.Enqueue(4);
    
    Console.WriteLine(q.Dequeue());
    Console.WriteLine(q.Dequeue());
    Console.WriteLine(q.Dequeue());
    Console.WriteLine(q.Dequeue());
    
    // 출력값 : 1 2 3 4
}

 

위 처럼 가장 먼저 저장된 값이 가장 먼저 나오게 된다.

 

Enqueue는 Queue에 해당 값을 등록하는 기능이다. 대기열에 새 대기자를 등록시키는 것이다.

 

Dequeue는 Queue에 가장 먼저 등록된 데이터를 사출하고 반환하는 기능이다. 다음 손님!

 

Queue에는 기본적인 Enqueue와 Dequeue이외에도 여러가지 빌트인 메서드들이 있지만, 그 수가 많아 여기서는 다루지 않겠다.