큐 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

큐 ADT

터널에서 차가 들어가고 빠져나가는 것 처럼,

먼저 삽입한 데이터가 먼저 빠져나오는 자료구조 인터페이스.

First-In  First-Out  (FIFO)

Last-In  Last-Out   (LILO)

큐 ADT의 특성

• 먼저 삽입한 데이터가 먼저 빠져나옴.  (FIFO or LILO)
• 큐의 First에서만 조회/삭제가 일어남.
• 큐의 Last에서만 삽입이 일어남.

구현에 따른 큐의 성능

큐의 First에서만 조회/삭제가 일어나고, Last에서만 삽입이 일어나기 때문에.

한 쪽에서는 조회/삭제 성능이 좋고, 반대쪽은 삽입 성능이 좋은 구현을 사용하는 것이 효율적이다.

• 배열?

어느쪽을 First로 잡든,  O(n)을 피해가지 못한다.

성능상 이점을 얻기힘든 구현방법.

• 단일 연결 리스트?

첫 지점을 First로 잡고,  반대편을 Last로 잡으면  O(1)의 성능을 보인다.

포인터 관리비용이 있으나,  적은편이며,  O(n)보단 낫다.

• 이중 연결 리스트?

포인터 관리비용이 좀 더 증가하나,  (포인터가 노드당 2개!)

봐줄만한 편.

중간 노드를 조회해야 한다면 이것을 사용해야 하나,

이런 경우에는 굳이? 큐를 사용해야할지 다시 살펴볼 것.

• 벡터?

수용량이 유동적이라는 것만 다를 뿐,  기본적으로 배열과 동일하다.

어느쪽을 First로 잡든,  O(n)을 피해가지 못한다.

• 스킵 리스트?

어느쪽을 First로 잡든,  O(log n)을 피해가지 못하며.

다른 구현을 사용한다면 O(1)로 동작할 수 있다는 것을 상기시키자.

레벨 관리를 위해 메모리도 더 잡아먹으며,

스킵 리스트는 이분검색을 사용하기 위한 구현임을 생각한다면,

큐의 구현으로 사용하는 것은 옳지 못하다.

• 환형 배열?

어느쪽을 First로 잡아도 성능이 좋다.

Front,  Rear 관리비용이 있긴 하나,  없는것과 마찬가지.  (단일 연결 리스트는 노드당 1개)

중간 지점에서의 조회성능도 나쁘지 않으나,

큐의 특성상 굳이 어필되지 않는 장점.

큐의 일반적인 구현으로 사용됨.

• 덱 (데크)?

벡터에서 첫 지점의 삽입/삭제 성능을 개선하여,

어느쪽을 First로 잡아도 성능이 좋다.

큐를 적용하면 좋은 문제

• 트리에서 너비우선 순회
• 대기열 관리
• ...