[C++ STL] Queue(큐)

개요

큐란 먼저 들어온 데이터가 먼저 나가는 선입 선출(First In First Out: FIFO) 구조를 뜻한다. FIFO 구조를 구현하기 위해선 데이터의 한쪽 끝(back)에선 삽입(push), 다른 쪽(front)에선 삭제(pop)이 이루어져야 한다.

 

기존 C에선 직접 구현이 필요했지만 C++은 STL에서 제공해준다.

 

헤더

# include <queue>

 

생성 및 초기화

큐에는 특별한 생성자가 존재하지 않는다. 즉, 벡터처럼 배열로 큐를 초기화 할 수 없다.

queue<int> q1;
queue<int> q2 = {1, 2, 3}; // Error

 

메소드

queue<int> q;

q.push(i): 큐에 원소 i 삽입 (front 쪽으로) - 리턴값 없음

q.pop(i): 큐에서 원소 제거 (back 쪽으로) - 리턴값 없음

q.front(i): front에 있는 원소 리턴

q.back(i): back에 있는 원소 리턴

q.push(0); 
q.push(1);
q.push(2);
cout << q.front() << endl; // 0
q.pop();
cout << q.front() << endl; // 1
q.pop();
cout << q.front() << endl; // 2

push()와 pop()은 리턴값이 없이 그냥 원소를 삽입하고 제거만 하는 메소드이다. 따라서 원소를 밖으로 꺼내서 쓸려 하면 위의 예시처럼 pop()과 front()를 조합하여 써야 한다. (당연히 pop 하기전에 front에 있는 원소를 뽑아내야한다...)

 

q.empty(): 큐가 비어있는지 판단 - Bool 리턴

q.size(): 큐에 들어있는 원소의 수 리턴

queue<int> q;
q.push(0); 
q.push(1);
q.push(2);
while (!q.empty()) {
    cout << q.front() << endl;
    cout << "Queue Size: " << q.size() << endl;
    q.pop();
}

// 0
// Queue Size: 3
// 1
// Queue Size: 2
// 2
// Queue Size: 1

 

etc

큐는 iterator를 사용하지 못하므로 내부의 원소들을 인덱스나 for(:)꼴로 조작하거나 탐색하기가 불가능하다.

큐는 큐가 쓰일 곳에서만 쓰자.