[코테를 위한 압축 개념] C++ STL 벡터(vector), 큐(queue), 스택(stack), 덱(deque)

[코테를 위한 압축 개념] C++ STL 벡터(vector), 큐(queue), 스택(stack), 덱(deque)

 

 Vector

 

C언어에서 사용하는 Array와 비슷한 기능을 하지만 훨씬 유용하게 쓰일 수 있습니다.

#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<int> temp;
    return 0;
}

위와 같이 vector를 include해주어야 하고, vector<type> name 의 형식으로 벡터를 만들 수 있습니다.

 

 

 

 Vector의 사용법

 

 push_back()

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_back('a');

    return 0;
}

 push_back()을 통해 벡터에 원소를 넣을 수 있습니다. 맨 뒤에 원소를 추가하게 되며 이 작업은 일반적으로 O(1)의 시간복잡도를 갖습니다. 벡터를 선언하면 공간이 할당되고 해당 공간에 원소를 하나씩 추가하다가 가득 차게 되면 전체 원소를 복사하여 새로운 곳에 더 큰 공간을 할당 받기 때문에 이 때는 O(n)의 시간복잡도를 갖습니다. 하지만 이 경우는 매우 드물기 때문에 전체적인 평균을 보았을 때 push_back()을 통해 원소를 추가하는 작업은 O(1) 입니다.

 

 

 size()

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_back('a');

    cout<< temp.size() << '\n';
    return 0;
}

size()를 통해 벡터에 들어있는 원소의 개수를 확인 할 수 있습니다.

 

 

 at(), []

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_back('a');

    for(int i=0;i<temp.size();i++){
        cout << temp[i] << '\n';
    }
    return 0;
}

벡터의 원소에 접근하는 방법은 at(), []이 있습니다. 배열처럼 []을 사용하면 편리합니다.

 

 

 pop_back()

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_back('a');
	
    temp.pop_back();
    
    cout<<temp.size()<<'\n'
    return 0;
}

 pop_back()을 통해 벡터의 제일 마지막에 있는 원소를 제거할 수 있습니다. 위 코드 실행결과는 2가 출력됩니다. 시간 복잡도는 push_back()과 같이 O(1)입니다. 알고리즘 문제를 풀면서 자주 쓰지는 않는 것 같습니다.

 

 

 pair와 함께 사용하기

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<pair<int, int>> temp;
    vector<pair<int, pair<int, char>>> test;
    
    temp.push_back(make_pair(1,11));
    temp.push_back(make_pair(2,22));

    for(int i=0;i<temp.size();i++){
    cout<<temp[i].first<<' ';
    cout<<temp[i].second<<'\n';
    }

    return 0;
}

 문제를 풀다보면 pair와 함께 벡터를 사용하는 것이 편할 때가 많습니다. 벡터를 선언할 때부터 pair로 선언하며 pair가 다중으로 되어도 상관없고 자료형이 달라도 상관없습니다. 다만 push_back()할 때에 make_pair()를 잘해주어야 하고 값에 접근할때 first, second로 접근해야 합니다.

 

 

 기타

 1. 반복자(iterator)라는 개념이 있지만 저는 문제를 풀면서 사용해본 적이 없습니다. 굳이 사용을 안해도 무방합니다. 

 2. 임의의 위치에 원소를 추가하거나 제거하는 작업( insert(), erase() )은 O(n)의 시간 복잡도를 갖습니다. 지금까지 문제를 풀면서 사용해본 적은 없는것 같습니다.

 

 

 

 

 Stack과 Queue

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> temp;
    temp.push(1);
    temp.push(2);
    temp.push(3);

    int k = temp.size();
    for(int i=0;i<k;i++){
    	cout << temp.front() << '\n';
    	temp.pop();
    }
    return 0;
}

 스택과 큐는 벡터를 응용한 개념입니다. push_back() 대신에 push()를 쓰고, pop_back() 대신에 pop()을 씁니다. 스택과 큐 모두 push()는 맨 뒤에 원소를 추가하지만 pop()에서 큐는 제일 앞의 원소를 제거하고, 스택은 맨 뒤의 원소를 제거합니다. 벡터와 달리 []을 통한 원소의 접근이 불가능하고 큐는 front()를 통해 맨 앞의 원소를, back()을 통해 맨 뒤의 원소를 접근할 수 있습니다. 위 코드를 실행하면 1, 2, 3의 결과를 얻을 수 있습니다.

 

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> temp;
    temp.push(1);
    temp.push(2);
    temp.push(3);

    int k = temp.size();
    for(int i=0;i<k;i++){
        cout << temp.top() << '\n';
        temp.pop();
    }
    return 0;
}

 스택도 큐와 같이 []을 통한 원소의 접근이 불가능하고 top()을 통해 제일 마지막에 있는 (위에 있는) 원소를 접근 할 수 있습니다.

 

 

 

 Deque

 

 많이 써보진 못했지만 알고 있으면 좋은 Deque입니다. 큐에서 조금 더 나아가 앞뒤로 원소를 추가, 제거가 가능한 큐라고 이해하면 됩니다.

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> temp;
    temp.push_back(1);
    temp.push_back(2);
    temp.push_front(3);
    temp.push_front(4);

    int k = temp.size();
    for(int i=0;i<k;i++){
    	cout << temp[i] << '\n';
    }
    return 0;
}

위 코드를 실행하면 4, 3, 1, 2 의 결과를 확인할 수 있습니다.