4. Queue

진짜 마지막

큐 (Queue)는 FIFO(First Input First Out) 입출력 구조를 가진 선형 자료구조로서, 큐의 Rear에서 Enqueue, 큐의 Front에서 Dequeue되는 구조이다.

큐 자료구조의 예시

선형큐 (Linear Queue)

선형큐는 두 가지 구조로 구현이 가능한데, 먼저 배열로 표현 가능하다. 한정된 배열 사이즈에 Enqueue, Dequeue를 반복적으로 실행하면 배열이 가득차 더이상 추가할 수 없는 문제가 발생한다. 자바스크립트에서는 동적으로 배열 사이즈가 할당되기 때문에 한정된 사이즈에 대한 이슈에서는 자유롭지만, Front와 Rear의 인덱스가 무한정 커질 수 있다는 문제가 있다.

Front, Rear의 인덱스가 무한정 커지는 이슈를 해결하기 위해 Dequeue가 발생하면 배열 안의 요소들을 앞당기는 작업이 필요한데, 이때 선형 시간이 소요되는 단점이 있다.

배열을 통한 선형큐 구현의 단점을 보완한 구조가 연결 리스트(Linked List) 이다. 연결 리스트로 선형큐를 구현하면 인덱스에 대한 고민을 하지 않아도 된다. 여기서 Head는 Front, Tail은 Rear가 된다.

연결 리스트 자료구조의 예시

다음은 배열로 구현한 큐의 예시 코드이다.

배열로 구현된 선형큐 예시 코드

연결 리스트를 통해 구현한 큐의 예시 코드이다. 배열로 구현된 큐보다 조금 복잡해 요소 갯수가 어느정도 한정되어 있다면 배열로 구현하는 것을 추천한다.

연결리스트로 구현된 선형큐 예시 코드

환영큐 (Circular Queue)

환영큐는 Front, Rear가 이어져있는 구조의 큐이다. 환영큐는 한정된 사이즈의 공간을 효율적으로 사용하기 위한 구조로서 연결 리스트로 구현해도 문제는 없지만, 이점 또한 크게 없다. 환영큐의 경우 코딩테스트에서 직접 구현해서 써야하는 경우가 드물다.

배열로 구현된 선형큐 예시 코드