큐(Queue)란?
First In First Out 이라는 개념을 가진 선형 자료구조이다. 먼저 들어간 것이 먼저 나오는, 나중에 들어간 것이 나중에 나오는 개념이라고 보면 된다. 큐의 맨 앞을 front 라고 한다. 큐의 맨 뒤를 rear 라고 부르고 큐에 요소를 추가하는 것을 EnQueue, DeQueue 라고 한다. 그리고 큐의 종류에는 선형 큐(Linear Queue) 와 환형 큐(Circular Queue)가 있다.
큐를 현실에 비유하자면 놀이 공원에서 사람들이 기구를 타기 위해 일렬로 줄을 선 대기열이라고 볼 수 있다. 대기줄을 큐라고 볼 수 있고 맨 앞에 줄을 선 사람이 front, 마지막 사람이 rear 이다.놀이 기구를 타러 가는 사람은 DeQueue 된 요소라고 볼 수 있고, 이제 줄 서려고 하는 사람은 EnQueue 할 요소라고 할 수 있다.
선형 큐(Linear Queue)
선형 큐는 두가지 방식으로 구현할 수 있다.
먼저 선형 큐는 배열로 표현할 수 있다. 하지만 스택과는 다르게 큐는 배열에서 사용하는 것이 조금 어렵습니다. 먼저 스택처럼 큐도 배열에 값을 순차적으로 담을 수 있습니다. 이때 0번 index 가 front , 3번 index 가 rear 이다. 만약 여기서 DeQuque 를 한다면, front 부터 하나씩 사라진다. 배열이기 때문에 빈 공간은 메꿔지지 않습니다. EnQuque 를 한다면 rear 뒤로 차례로 추가가 된다. 여기서 EnQuque 가 여러 번 반복되어 한정된 공간이 전부 꽉 찬다면 더 이상 Queue 값을 추가하는 것이 불가능하다. 자바스크립트에서는 배열이 자유롭게 증감되기 때문에 이런 문제는 없겠지만 front 나 rear index 값이 무한정 커질 수 있는 문제가 있다. 따라서 배열에서 공간을 더 쓰기 위해 앞당기는 작업이 필요한데 이 작업을 수행하면 선형시간이 소요된다.
이런 문제를 해결하는 방법은 연결리스트로 큐를 구현하는 방법이다. 큐를 연결 리스트로 구현하면 head 는 front 가 되고 Tail 은 Rear 가 된다. 연결 리스트를 사용하면 배열과 다르게 index 에 대한 고민은 하지 않아도 괜찮다.
자바스크립트에서 큐를 사용하는 방법
먼저 배열로 구현하는 방법이 있다. 이 구현은 구현이 간단하기 때문에 코딩테스트에서 큐를 사용할 떄 좋다.
대신 앞선 내용에서와 같이 front 와 rear 가 무한정 커질 수 있는 단점이 있다. 큐를 배열로 구현할 때 사용되는 메서드는 enqueue(value), dequeue(), peek(), size(), 가 있다. 이처럼 큐 구현은 생각보다 어렵지 않다. 자바스크립트에서 기본적으로 큐가 제공되지 않는 것은 아쉽지만, 구현이 어렵지 않기 때문에 한번 직접 구현 해보면 코딩테스트에 많은 도움이 된다.
그 다음에 연결 리스트(Linked List)로 큐 구현이다. 배열을 이용하는 방법보다 조금 더 복잡하지만 이미 연결 리스트를 구현하였다면 그렇게 어렵진 않다. 큐를 연결 리스트로 구현할 사용되는 메서드는 enqueue(newValue), dequeue(), peek() 이 있다.
큐를 구현 하기 전 팁!
간혹 자바스크립트 큐 구현을 검색해서 나오는 자료에 shift 함수로 구현할 수 있다고 나와 있는 경우가 있다.
그런데 이 정보는 잘못된 정보이다. 자바스크립트 배열에서 shift 함수는 선형 시간이 걸리기 때문에 queue 에서 기대하는 로직이 수행되지 않는다.
환형 큐(Circular Queue)
Front 와 Rear 가 이어져있는 Queue 로써, Circular Queue 는 Linked List 로 구현 했을 때 이점이 없다.
환형 큐는 한정된 공간을 효율적으로 사용하기 위해 만들어진 자료구조이기 때문에 연결 리스트로 구현해도 상관은 없지만
크게 이점이 없다. 배열로 구현해도 큰 차이가 없지만 maxSize 를 받아 큐의 크기를 제한한다. 그리고 front 나 rear 가 크기를 벗어 날 경우 다시 0번 index 부터 시작되도록 코드를 작성할 수 있다.
