자료구조 / 큐(Queue)

큐 (Queue)

선입선출 FIFO(First In First Out)의 자료구조이다.

데이터가 들어오는 위치는 가장 뒤에 있고, 나가는 위치는 가장 앞에 있어서, 선입선출의 구조를 갖게된다.

즉, 먼저 들어온 데이터가 먼저 제거된다.

 

 

큐의 동작

1️⃣ Enqueue : 큐에 데이터를 추가한다. 큐가 꽉 차있을 때 Overfolw condition이 된다.

2️⃣ Dequeue : 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 빠져나온다.
                        큐가 비어져 있을 때는 Underflow condition이 된다.

3️⃣ Front : 큐의 앞부분의 데이터를 가진다.

4️⃣ Rear : 큐의 뒷부분의 데이터를 가진다.

 

 

큐의 종류

큐를 구현하기에 front(머리)와 rear(꼬리) 두가지 지표를 추적해야 한다.

rear에 데이터를 추가하고(enqueue), front에 데이터를 빼낸다(dequeue).

 

만약, front와 rear의 지표를 증가시키면 문제가 될 수 있다.

▶front가 rear에 (배열의 끝)에 도달할 수 있기 때문이다.

 

위와 같은 문제를 아래와 같은 방법으로 해결할 수 있다.

1. 순환 큐

front와 rear가 연결되어 있는데 1, 2, 3의 큐에서는 3에서 끝나지만,

순환 큐는 rear인 3에서 다시 front인 1로 넘어간다.

 

순환 큐가 사용되는 이유는 메모리 관리 측면인데,

JS에서는 메모리를 알아서 정리해주기에 효용성이 떨어진다.

순환 큐 예시

 

2. 우선순위 큐

우선순위 큐는 enqueue와 dequeue는 같지만,

enqueue 할 때, 제일 뒤에 넣는 것이 아닌, 우선순위를 따져 데이터를 넣습니다.

우선쉰위는 프로그래머가 직접 정해주면 됩니다.

 

단, 우선순위 큐의 문제로, 보통 큐와 같이 구현하면 데이터를 삽입하기 힘들다는 단점이 있다.

주로 힙이라는 자료구조를 사용해 구한다.

 

큐의 예시

큐는 즉시 처리될 필요가 없을 경우 사용되지만,

Breadth First Search(너비 우선 탐색)처럼 First In First Out 순서처럼 처리되어야 합니다.

또한, 큐의 속성은 아래와 같은 시나리오에도 유용합니다.

 

1) 여러 소비자 사이에서 자원이 공유될 경우
ex) Disk Scheduling, CPU Scheduling

 

2) 두 프로세스 사이에서 비동기적으로 데이터를 받을 경우
ex)  IO Buffers, pipes, file IO, etc.

2-1)  IO Buffers 예시 : 프린터 - 인쇄를 요청한 순서대로 큐에 들어가, 순서대로 인쇄물이 출력

컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때,
각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해
임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)라고 합니다.

 

큐의 시간 복잡도

Enqueue (insertion) : O(1)

Dequeue (deletion) : O(1)

Front (Get front) : O(1)

Rear (Get Rear) : O(1)

 

보조 공간: input size를 고려하여 알고리즘이 문제를 해결하기 위해 임시로 사용하는 공간 : O(N)

 

배열로 큐를 구현할 때의 장단점

장점: 구현하기 쉽다.

단점: 사이즈가 고정되어 있다 (정적인 데이터 구조)

 

만약에 enqueue와 dequeue로 큐가 큰 숫자를 가졌다면,

큐가 비어있더라도 큐에 요소를 삽입하지 못할 수 있다. (순환 큐로 대처할 수 있다)

 

링크드리스트로 큐를 구현하는 게 더 쉽다.