deque는 시작 위치와 마지막 위치의 삽입, 삭제를 O(1)에 처리할 수 있는 stack과 queue를 합쳐놓은 느낌의 자료구조이다.
또한 std::deque는 [] 연산자를 쓸 수 있기 때문에 임의 위치의 원소를 O(1)에 접근 및 수정할 수 있다.
따라서 deque는 일반적으로 연속된 자료에서 front(), back() 위치의 삽입, 삭제가 여러 번 일어날 때 사용된다.
deque은 double ended queue의 줄임말로 front(), back() 위치에 원소의 삽입, 삭제를 O(1)에 처리할 수 있는 자료구조이다.
따라서 덱은 필요시 스택으로 이용할 수 있고, 큐로도 이용할 수 있습니다.
여기에 추가로 c++의 deque는 vector처럼 임의 위치의 원소를 [] 연산자를 이용해 O(1)에 접근할 수 있다.
따라서 덱은 vector 대신 이용할 수도 있다.
정리해보면 덱은 지금까지 배운 stack, queue, vector의 기능을 모두 제공하는 컨테이너이다.
deque vs vector
1. deque의 장점
- vector와 달리 push_front(), pop_front() 연산을 제공한다.
- capacity와 size가 같아지면 특정 크기의 chunk를 할당해서 크기를 늘린다.
이는 capacity를 1.5 ~ 2배로 늘려서 전체를 재할당하는 vector에 비해 확장 비용을 줄여준다.
2. deque의 단점
- 연속된 메모리 상에 존재하지 않기 때문에 cache hit rate가 떨어져 vector에 비해 느리다.
- 연속된 메모리 상에 존재하지 않기 때문에 원소들을 가리키는 포인터 간의 연산이 불가능하다.
(단, iterator 간의 연산은 가능하다)
결론)
deque는 chunk 단위로 확장을 하는 특징 때문에 장단점이 있으므로,
push_front(), pop_front() 연산이 필요한 경우가 아니라면 vector를 이용하는게 좋다.
deque vs stack, queue
덱은 stack, queue의 연산을 모두 지원한다. 그렇다면 std::stack, std::queue는 전부 std::deque로 대체할 수 있을까?
정답은 yes이다. 하지만 push_back, pop_back 연산만 사용하는 경우엔 stack을, push_back, pop_front 연산만 사용하는 경우엔 queue를 사용하는 것이 좋다. 이렇게 하면 자료형으로 해당 객체가 어떤 역할을 수행하는지 판단할 수 있기 때문에 가독성이 좋아진다는 장점이 있다.
deque와 stack, queue의 성능은 stack, queue의 default container가 deque이기 때문에
stack, queue가 약간 느릴 수 있지만, 유의미한 차이는 없다.
deque _ 생성자
1. deque<int> DQ; // 비어있는 덱을 생성
2. deque<int> DQ(n); 또는 deque<int> DQ(n, val); // n개의 원소를 갖는 deque를 생성한다.
이때 두 번째 인자(val)가 없는 경우는 자료형의 초기값으로, 인자가 있는 경우는 해당 값으로 n개의 원소가 채워진다.
3. deque<int> DQ(dq.begin(), dq.end()); // 다른 컨테이너의 iterator를 받아온 뒤, 순회하며 deque에 해당 범위의 원소를 채운다.
4. deque<int> DQ{ 1, 2, 3 }; 또는 deque<int> DQ = { 1, 2, 3 }; // initializer_list를 인자로 받는 생성자이다.
deque 멤버 함수
int main() {
fastio;
deque<int> DQ; // DQ = { }
for (int i = 1; i <= 5; i++) DQ.push_back(i); // DQ = { 1, 2, 3, 4, 5 }
for (int i = 6; i <= 10; i++) DQ.push_front(i); // DQ = { 10, 9, 8, 7, 6, 1, 2, 3, 4, 5 }
for (int i = 1; i <= 3; i++) DQ.pop_front(); // DQ = { 7, 6, 1, 2, 3, 4, 5 }
for (int i = 1; i <= 3; i++) DQ.pop_back(); // DQ = { 7, 6, 1, 2 }
cout << "DQ.size() : " << DQ.size() << '\n'; // 4
cout << "DQ.empty() : " << DQ.empty() << '\n' << '\n'; // 0
DQ.clear(); // DQ = { }
DQ.resize(1); // DQ = { 0 }
DQ.resize(3, 2); // DQ = { 0, 2, 2 }
DQ[1] = 1; // DQ = { 0, 1, 2 }
for (auto it = DQ.begin(); it != DQ.end(); it++) cout << *it << ' '; cout << '\n'; // 0 1 2
for (auto it = DQ.rbegin(); it != DQ.rend(); it++) cout << *it << ' '; cout << '\n'; // 2 1 0
cout << "DQ.front() : " << DQ.front() << '\n'; // 0
cout << "DQ.end() : " << DQ.back() << '\n'; // 2
}
- push_back : 마지막 위치에 원소를 삽입. O(1)
- push_front : 시작 위치에 원소를 삽입. O(1)
<pop_back, pop_front>: 반환값은 void이다
- pop_back : 마지막 위치의 원소를 삭제. O(1)
- pop_front : 시작 위치의 원소를 삭제. O(1)
<insert, erase>: 시간복잡도는 O(n)이기 때문에 deque는 n이 클 때 insert, erase 연산을 여러 번 적용하기에 적합하지 않다.
- insert : 임의의 위치에 원소를 삽입. O(n)
- erase : 임의의 위치의 원소를 삭제. O(n)
- size : deque의 크기를 size_t 자료형으로 반환.
- empty : deque가 비어있는지 여부를 bool 자료형으로 반환.
<resize>: 변경된 크기가 원래 크기보다 작은 경우는 뒤의 원소부터 차례로 지워지고, 큰 경우엔 두 번째가 인자가 없는 경우 초기값으로, 있는 경우 해당 값으로 남는 칸이 채워진다.
- resize : deque의 크기를 변경.
- clear : deque의 모든 원소를 삭제.
- begin : deque의 첫 번째 원소를 가리키는 iterator를 반환.
- end : deque의 마지막 원소의 다음 칸을 가리키는 iterator를 반환.
- rbegin : begin의 reverse_iterator 버전.
- rend : end의 reverse_iterator 버전.
- front : DQ[0]을 reference로 반환. O(1)
- back : DQ[n - 1]을 reference로 반환. O(1)
백준)
10866번
int main(){
fastio;
int N,T;
cin>>N;
deque<int> DQ;
while(N--){
string s; cin>>s;
int F;
if(s=="push_front") {cin>>T; DQ.push_front(T);}
else if (s=="push_back"){cin>>T; DQ.push_back(T);}
else if(s=="pop_front") {
if(DQ.empty()) cout<<"-1"<< '\n';
else{
F=DQ.front(); DQ.pop_front(); cout<<F<< '\n';} }
else if(s=="pop_back"){
if(DQ.empty()) cout<<"-1"<< '\n';
else{
F=DQ.back(); DQ.pop_back(); cout<<F<< '\n';}
}
else if(s=="size"){
cout<<DQ.size()<< '\n';
}
else if(s=="empty"){
cout<<(DQ.empty()? 1:0)<< '\n';
}
else if(s=="front"){
cout<<(DQ.empty()?-1:DQ.front())<< '\n';
}
else if(s=="back"){
cout<<(DQ.empty()?-1:DQ.back())<< '\n';
}
}
}
핳 너무 더럽다
int main() {
fastio;
int n, t; cin >> n;
deque<int> DQ;
while (n--) {
string s; cin >> s;
if (s == "push_front") cin >> t, DQ.push_front(t);
else if (s == "push_back") cin >> t, DQ.push_back(t);
else if (s == "pop_front") cout << (DQ.empty() ? -1 : DQ.front()) << '\n', DQ.size() ? DQ.pop_front() : void();
else if (s == "pop_back") cout << (DQ.empty() ? -1 : DQ.back()) << '\n', DQ.size() ? DQ.pop_back() : void();
else if (s == "size") cout << DQ.size() << '\n';
else if (s == "empty") cout << DQ.empty() << '\n';
else if (s == "front") cout << (DQ.empty() ? -1 : DQ.front()) << '\n';
else if (s == "back") cout << (DQ.empty() ? -1 : DQ.back()) << '\n';
}
}
이것처럼 코드를 바꾸자
1021번) 회전하는 큐
int main(){
fastio;
int n,t,count=0;
cin>>n>>t;
deque<int> DQ;
for(int i=1; i<=n; i++) {DQ.push_back(i);}
while(t--){
int in,idx;
cin>>in;
for(int i=0; i<DQ.size(); i++){
if(DQ.front() == in) {idx=i; break;} // idx는 in의 위치
DQ.push_back(DQ.front()); DQ.pop_front();
}
count += min<int>(idx, DQ.size()-idx); // min을 쓰기위해 자료형 <int>로 명시
DQ.pop_front(); //정상 처리 완료 시 pop_front() 해줘서 빼줘야 함
}
cout<<count;
}
이것도 블로그 코드를 참고했다. idx에 위치를 기록한다는 개념과 min으로 처리해서 중앙값보다 클때 작을때를 처리해줬다.
if 문으로 DQ.size()/2 로 처리하려 했지만 안되었고 for 문써서 숫자를 돌리는 게 나을 거 같다 (ㅜㅜ)
9935) 문자열 폭발
//spc문자열을 돌면서 bomb의 마지막 원소와 일치한지 확인
-> 문장길이가 더 길게 되면 bomb가 spc에 있는지 확인해서 있으면 flag true하고 erase까지 해준다.
int main(){
fastio;
string str,bomb,spc="";
cin>>str>>bomb;
for(int i=0; i<str.length(); i++){
spc+=str[i];
if(spc.length()>=bomb.length()){
bool flag=true;
for(int j=0; j<bomb.length(); j++){
if(spc[spc.length()-bomb.length()+j] != bomb[j]){
flag=false;
break;
}
}
if(flag){
spc.erase(spc.end()-bomb.length(), spc.end()); }
}
}
if(spc.empty()) cout<<"FRULA"<<'\n';
else cout<<spc<<'\n';
return 0;
}
3111) 9935번을 기반으로 도전
'백준일지' 카테고리의 다른 글
| [C++] STL 자료구조: List (0) | 2024.05.02 |
|---|---|
| [C++] STL 자료구조: Priority queue (0) | 2024.04.29 |
| [C++] STL 자료구조: Queue (0) | 2024.04.03 |
| [C++] STL 자료구조: stack (0) | 2024.03.31 |
| [C++] STL 자료구조: string (0) | 2024.03.28 |
