[자료구조] Queue

 

큐는 First in , First out 구조를 가진 (선입선출) 자료구조이다.

선형적으로 뒤에서 데이터가 들어와 앞으로 빠져나간다.

 

핵심 특징

삽입(Enqueue)	뒤에서 데이터 추가
삭제(Dequeue)	앞에서 데이터 제거
선입선출(FIFO)	먼저 들어간 게 먼저 나옴
순서 유지	데이터 삽입 순서가 유지됨

 

주된 활용 예시

 

- 마우스 / 키보드 이벤트 큐 구현에 사용

- KafKa , RabbitMQ 등 메시지 브로커에서 주로 사용

- 작업을 순차적으로 처리하는 비동기 처리에서 사

 

 

배열 기반으로 구현된 큐

 

 

배열 기반 큐는 삭제시에는 앞에 공간이 비어버리기 때문에 앞에 불필요한 공간이 생기게 된다. 선입선출 구조이기 때문에

앞에 빈 공간을 활용하지 못하는 경우가 있다.

 

원형 큐

원형의 형태로 배열을 구성하는 방법이다.

위와 같이 배열이 꽉 차버리면 어디서 앞이고 어디가 뒤인지 구별할 수 없게 된다.

그래서 일반적으로 원형큐는 꽉 채워서 구현하지 않는다.

 

 

연결 리스트 큐

 

연결 리스트를 활용하여 구현한 큐는 선행 데이터가 삭제되면 그냥 데이터를 지우고 노드들에 포인터들의 값들을

변경 시켜주면 된다.

이 구조는 동적 메모리 관리에 유리하고, 삽입/삭제 시 메모리 이동이 필요 없어 성능이 안정적

 

하지만 인덱스를 사용하지 않기 때문에 임의 접근이 불가능하다.

 

 

덱(Deque, Double-ended queue)

 

덱은 큐와 달리 선형적인 자료구조이지만 앞과 뒤 둘다에서 데이터의 삽입 삭제가 가능하다.

 

pushFront	앞에서 삽입
popFront	앞에서 제거
pushBack	뒤에서 삽입
popBack	뒤에서 제거

 

 

큐와 덱의 시간복잡도

구현방식	자료구조	삽입	삭제
배열	큐	O(1) (push)	O(n) (shift)
배열	덱	O(1) (pushBack), O(n) (pushFront)	O(1) (popBack), O(n) (popFront)
연결 리스트	큐	O(1)	O(1)
연결 리스트	덱	O(1)	O(1)

 

연결 리스트 기반은 head, tail 포인터만 잘 관리하면 모든 삽입/삭제가 O(1) 로 가능하다.