배열과 다르게 크기를 동적으로 조절할 수 있어 유용한 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 라이브러리를 사용하는 것을 추천드립니다.
알고리즘 문제를 풀 때 억지로 자료구조를 벡터로 구현하려 하면 시간초과날 수 있습니다. 저처럼...
'프로그래밍 > 기타 프로그래밍' 카테고리의 다른 글
[C++] 우선순위 큐 priority_queue (1) | 2023.10.11 |
---|---|
[npm] link를 사용하여 개발중인 라이브러리 로컬에서 테스트하기 (0) | 2023.09.05 |
[Python3] 백준 문제 풀이에 사용되는 입력 코드 (0) | 2023.06.25 |
[Python3] input 입력 받기 (0) | 2023.04.04 |
[Python3] 큰 따옴표(")와 작은 따옴표(') (0) | 2023.03.26 |