큐(queue)

개요

• 헤더 파일: <queue>
• STL 컨테이너 어댑터(adapter container): 기본적으로 deque의 기능을 제한하여 만들어진 자료구조.
• 탐색 시간: $O(1)$ (Front 탐색)
• 요소 추가/삭제: $O(1)$ (Enqueue 및 Dequeue)

큐(Queue)는 선형 자료구조이면서 선입선출(First In First Out, FIFO) 특성을 가지는 자료구조입니다.

선입 선출이란, 먼저 넣은 것이 먼저 제거되는 특성을 말합니다.

큐는 Front와 Rear라는 위치의 데이터에만 접근할 수 있기 때문에, 중간 요소의 순서 변경이 없으므로, 순서를 보장합니다.

이러한 선입선출(FIFO)의 특성으로 인해 순차적인 작업 처리에 매우 유용합니다.

C++ 에서의 큐

C++의 <queue>는 기본적으로 <deque>의 기능을 제한하여 만들어진 컨테이너입니다.

(벡터, 덱, 리스트 등 다양한 컨테이너를 기반으로 만들 수 있습니다. 단, std::queue의 경우 front에서 동작되어야 하는 알고리즘이 존재하기 때문에, 컨테이너에 pop_front() 같은 함수가 존재해야 합니다.)

큐는 임의 접근을 허용하지 않으며, 이터레이터 또한 허용하지 않습니다. 이는 큐의 FIFO 특성을 유지하기 위함입니다.

큐의 활용

큐는 순서 보장의 특징으로 인해 다양한 알고리즘에서 효과적으로 활용됩니다.

예를 들어, 데이터 버퍼링(데이터가 순차적으로 처리되어야 할 때), 태스크 스케줄링(작업이 순차적으로 수행되어야 할 때), 네트워크 트래픽 관리, 등 많은 알고리즘에서 효과적으로 동작합니다.

음… 조금 더 쉽게 이해할 수 있도록 하자면, 멀티스레드 환경에서 데이터를 생성하는 스레드들과 데이터를 처리하는 스레드들이 있을 수 있습니다. 이때, 여러 스레드가 처리해야 할 작업들을 작업 대기열(Work Queue)에 넣고 데이터를 처리하는 스레드들이 큐에서 작업을 가져가 처리하게 하여 작업들을 순차적으로 처리하게끔 할 수 있습니다.

---

특징

1. Front에서 빠른 탐색 및 삭제가 가능하며 Rear를 통해 새로운 요소를 빠르게 추가할 수 있는 자료구조입니다.
2. 순서 보장: 큐는 데이터의 순서를 엄격하게 관리하며, 순차적으로 데이터를 처리할 수 있습니다.

장단점

장점

• 간단하고 효율적: 큐는 구현이 간단하며, 순차적인 데이터 처리를 효율적으로 수행할 수 있습니다.
• 빠른 연산: Front와 Rear에서의 요소 추가 및 삭제가 $O(1)$의 시간 복잡도를 가집니다.

단점

• 유연성 부족: 큐는 중간 요소에 대한 접근이나 수정이 불가능하여, 일부 알고리즘에는 적합하지 않을 수 있습니다.

(이 외에 큐를 구현한 컨테이너나 방식에 따라 세부적인 장단점이 추가될 수 있습니다.)

---

사용법

생성자

std::queue<typename _Ty, typename _Container> q(); // 기본 생성자. 컨테이너를 선택할 수 있습니다.
std::queue<typename _Ty, typename _Container> q(std::_Container<_Ty> _Cont); // 기존의 컨테이너 데이터로 큐를 만듭니다.
std::queue<typename _Ty, typename _Container> q(std::queue<_Container> _Right); // 기존의 큐를 복사합니다.

멤버 함수

멤버 함수	설명
q.push(x) / q.pop()	큐의 요소 x를 삽입하거나, Front 요소를 제거합니다.
q.front() / q.back()	큐의 Front 혹은 Rear 요소에 대한 참조를 반환합니다.
q.empty()	큐가 비어있으면 true를 반환합니다.
q.size()	큐에 저장된 요소의 수를 반환합니다.