[자료 구조] 큐

큐(Queue)는 자료 구조의 하나로, 리스트, 배열, 스택과 마찬가지로 데이터를 1열로 나열한 구조입니다. 스택과 비슷하지만 큐는 추가하는 측과 삭제하는 측이 반대입니다. 큐는 '대기 행렬'이라고 불립니다. 명칭처럼 줄 서 있는 행렬을 생각하면 이해하기 쉽습니다. 행렬에서는 새롭게 온 사람이 가장 뒤에 서며, 가장 앞에 있는 사람부터 순서대로 처리됩니다. - 책 알고리즘 도감

 

큐의 개념도

 

 

 

큐에 데이터를 추가하는 작업을 '인큐(enqueue)'라고 합니다.

큐에 'Green'과 'Red'를 인큐했습니다.

 

 

 

큐에서 데이터를 꺼내는 작업을 '디큐(dequeue)'라고 합니다.

제일 아래에 Blue가 있었기 때문에 디큐를 하면 Blue가 나옵니다. 한 번더 디큐를 하면 Green이 나올 것입니다.

 

큐와 같이 먼저 넣은 것을 먼저 꺼내는 선입선출 구조를 'First In First Out'이라고 하며, 앞글자만 따서 'FIFO'라고도 합니다. 

 

스택과 마찬가지로 데이터를 조작할 수 있는 위치가 정해져 있습니다. 스택에서는 추가와 삭제를 같은 쪽에서 하지만, 큐에서는 추가하는 쪽과 삭제하는 쪽이 반대입니다. 스택과 마찬가지로 중간에 있는 데이터에 곧바로 접근할 수 없으며, 필요한 데이터가 나올 때까지 디큐를 해야 합니다.

 

참고 - 책 알고리즘 도감