[C++] 벡터(vector) 를 활용하여 큐(queue) 자료구조 구현하기

배열과 다르게 크기를 동적으로 조절할 수 있어 유용한 C++의 vector를 사용하여 FIFO 자료구조 queue를 구현해 보겠습니다.

 

선언

vector를 사용하기 위해 아래와 같이 선언할 수 있습니다.

#include<vector>

...

vector< int > queue_v;

 

값 마지막에 추가하기

push_back 함수를 사용하여 vector의 끝에 원소를 추가할 수 있습니다.

int i=2;
queue_v.push_back(i);

 

첫 번째 값 제거하기

vector의 erase 함수를 사용하여 vector의 가장 첫 원소의 인덱스를 제거할 수 있습니다.

queue_v.erase(queue_v.begin());

 

첫 번째 값 저장 후 제거하기

값을 빼기 전에 뺄 값을 다른 곳에 활용해야 할 경우가 빈번한데, front 함수를 사용해야 합니다. 아래와 같이 코드를 작성할 수 있습니다.

int i;
i = queue_v.front();
queue_v.erase(queue_v.begin())

 

값 모두 지우기

queue_v.clear();

 

정리

queue 자료구조를 vector로 만들어 사용하는 경우,

• push : queue_v.pop_back(데이터);
• pop : queue_v.erase(queue_v.begin());

이렇게 기억하면 됩니다.

 

한계

지나치게 느립니다. 특히 vector의 erase 함수는 첫 번째 원소를 제거하고 다른 원소를 하나 하나 앞으로 이동시키는 연산이므로 매우 느립니다. 따라서 특별한 제약이 없는 상황에서 queue 또는 stack을 구현하고 싶은 경우 C++ queue 또는 stack 라이브러리를 사용하는 것을 추천드립니다.

알고리즘 문제를 풀 때 억지로 자료구조를 벡터로 구현하려 하면 시간초과날 수 있습니다. 저처럼...