자료구조 | 큐(Queue)

큐(Queue)는 무엇인가?

큐의 사전적 의미는 일렬로 늘어선 사람들로 이루어진 줄을 말한다.

의미 그대로 차례대로 먼저 집어 넣은 데이터가 먼저 나오는 선형 자료구조이다.

 

큐의 특징

먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First In First Out) 형태.

삽입(Insert)과 삭제(Delete) 연산은 각각 다른 곳에서 이루어진다.

먼저 들어간 데이터가 삭제(Delete)되는 연산은 디큐(Dequeue)라고 하며 연산이 일어나는 곳을 front라고 한다.

데이터를 삽입(Insert)하는 연산을 인큐(Enqueue)라고 하며 연산이 이루어 지는곳을 rear라고 한다.

 

큐의 사용 사례

은행에 가면 번호표를 받은 순서대로 업무를 보는 경우.

너비 우선 탐색(BFS) 구현.

프린트 출력.

 

큐의 시간복잡도

Insert : O(1)

Delete : O(1)