[C++ STL] std::queue (컨테이너 어댑터)

std::queue

std::queue는 FIFO구조를 가지는 Queue 자료구조의 컨테이너

 -> FIFO(First In First Out) : 가장 처음에 삽입된 것이 가장 먼저 나온다.

std::queue는 내부적으로 deque, list를 기반으로 내부가 구현이 되어있으며 자료구조인 Queue의 기능을 제공한다.

 -> 디폴트로 deque기반으로 구현.

 -> std::vector의 경우에는 std::stack에서는 내부 컨테이너로 구현되어있었지만, std::queue의 경우에는 앞에서 제거하는 연산이 느린 vector를 사용하지 않는다. 

저장하는 컨테이너가 디폴트로 deque인 모습.

먼저 std::queue 컨테이너를 사용하기 위해서는 <queue> 헤더파일을 추가해야 한다.

기본적인 생성방법

// 기본 생성 방식.
std::queue<int> q;
// 내부 구현이 list로 생성하는 방식.
std::queue<int,std::list<int>> q2;
// 복사 생성자 지원
std::queue<int> q3(q);

내부 구현의 컨테이너를 넘기는 부분에 vector를 넘길 수는 있다. 다만 pop 함수를 호출할 때 런타임 에러가 발생한다.

 

이제 멤버 함수를 보자.

 -> stack과 마찬가지로 queue로 동작하는 인터페이스를 제공하기에 내부 멤버 함수는 많지 않다.

 -> 또한 stack과 겹치는 기능이 있으므로 ( empty, size 등) 해당 함수는 설명 x

 

1. push, pop

std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.push(50);
 
q.pop(); // 10이 제거된다.

 push함수는 인자로 넘긴 데이터를 queue에 저장하며, pop함수는 가장 처음에 들어간 원소를 제거한다.

stack함수에도 push, pop함수가 존재한다. 다만 데이터를 어떤 식으로 저장하는지가 조금 다르다.

 

출처 -&nbsp;https://iq.opengenus.org/stack-cpp-stl/

 

스택의 저장 방식이 위의 그림과 같다면

출처 -&nbsp;https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

queue는 위의 그림과 같이 데이터를 저장한다.

즉 stack에서는 하나의 통로에서만 데이터를 push, pop 했다면

queue의 경우에는 두 개의 통로에서 한쪽은 push 다른 한쪽은 pop을 하는 것. (각각 back에서 push, front에서 pop)

 

그렇기에 queue에서 데이터를 확인하는 방법이 2개가 존재하는데 각각 front와 back함수가 존재한다.

 

2. front, back 함수

std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.push(50);
 
// 각각 10과 50을 출력한다.
std::cout << q.front() << " " << q.back();

front함수는 가장 처음에 들어간 요소를 반환한다. back함수는 가장 마지막에 들어간 요소를 반환한다.

 

나머지는 std::stack과 동일하다.

 

정리.

std::queue는 앞에서 stack에서 설명한 것처럼 장단점을 논할 수 없다.

 -> queue를 사용하는 가장 대표적인 예로 그래프 알고리즘인 BFS(너비우선탐색)에서 FIFO구조를 사용.