[자료구조] 큐(queue)

이번 포스팅에서는 선형 자료구조인 큐에 대해서 알아보겠습니다. 큐는 스택, 데큐와 비슷한 점이 아주 많기 때문에 이들과 같이 비교하면서 보는게 좋습니다.

1. 큐

FIFO의 규칙을 가지는 자료구조입니다. 선입선출이라고도 합니다. 마치 놀이공원 대기줄을 연상시키죠.

 

2. 구현

배열을 이용해 구현할 수 있지만 head와 tail이 계속해서 밀리는 문제때문에 연결리스트를 이용한 원형 큐로 구현하는 것이 효율적입니다. 

하지만 C++의 STL에는 이미 선형 큐가 구현되어 있습니다. STL의 queue를 쓰는 것을 적극 추천합니다.

다음은 큐 구현을 연습하기에 좋은 기본적인 문제들입니다.

[백준 10845] 큐

[백준 18258] 큐2

[백준 2164] 카드2

 

3. 활용

큐는 주로 한 방향으로 처리되는 데이터들을 저장할 때 유용합니다. 큐를 사용하는 가장 대표적인 알고리즘으로는 너비 우선 탐색 알고리즘이 있습니다. 이 알고리즘에 대해서는 다른 포스팅에서 자세히 다루도록 하겠습니다. 

또한 큐는 힙 자료구조와 함께 우선순위 큐로 변형하여 사용되기도 합니다.  힙 자료구조는 이진 트리에서 자세히 다루었으니 참고해 주세요.

 

 

정리하자면 큐는 순차적으로 처리되는 데이터들을 저장한다는 특징을 가지고 있습니다. 따라서 문제 상황에서 순차적으로 무언가를 처리해야 한다는 느낌을 받으면 큐를 떠올려 볼 수 있습니다.