[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 덱(Deque)
- STL deque
- Q&A
- 마치며
1. 덱(Deque)
- 덱(Deque, Double Ended Queue)
: 양쪽 끝에서 원소 넣거나 뺄 수 있는 자료구조
스택과 큐는 덱의 특수한 예시라고 볼 수도 있음.
1) 덱의 성질
(1) 원소의 추가 / 제거 O(1)
(2) 제일 앞 / 뒤의 원소 확인 O(1)
(3) 제일 앞 / 뒤가 아닌, 나머지 원소들의 확인 / 변경이 원칙적으로 불가능
단, STL deque는 인덱스로 원소에 접근 가능함.
2) 덱의 구현
const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;dat배열에는 덱 원소들의 값이 들어가고, head는 제일 앞의 원소를 가리키고, tail은 제일 뒤의 원소 + 1을 가리키고 있음.
그리고 dat[head]부터 dat[tail - 1]까지 큐의 원소들이 있는 자리임. 그리고 큐의 크기는 tail - head로 계산 가능.
단, head와 tail의 초기값이 0이 아닌, MX임.
덱은 원소를 양쪽 끝에서 추가할 수 있기 때문에, head를 0으로 했을 때 왼쪽으로 확장할 수 없음.
따라서 중간지점에서 양쪽 끝으로 확장해 나가야 함.
const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;
void push_front(int x){
dat[--head] = x;
}
void push_back(int x){
dat[tail++] = x;
}
void pop_front(){
head++;
}
void pop_back(){
tail--;
}
int front(){
return dat[head];
}
int back(){
return dat[tail - 1];
}3) 벡터와 덱
STL queue는 double ended queue보다는 vector의 느낌이 강함.
pop_front, push_front, pop_back, push_front는 그렇다 하지만,
insert, erase, 인덱스 접근도 가능.
(1) deque의 장점
(1.1) vector와 달리 push_front(), pop_front() 연산 제공
(1.2) capacity와 size가 같아지면 특정 크기의 chunk를 할당해서 크기를 늘려줌.
vector는 1.5 ~ 2배로 늘려서 전체를 재할당함.
따라서 vector에 비해 확장 비용을 줄여줌.
(2) deque의 단점
(2.1) 비연속적으로 메모리 상에 존재하기 때문에, cache hit rate가 떨어져 vector에 비해 느림.
(2.2) 비연속적으로 메모리 상에 존재하기 때문에, 원소들을 가리키는 포인터 간의 연산은 불가능.
단, iterator 간의 연산은 가능.
4) 덱과 스택, 큐
덱은 스택과 큐의 연산을 모두 지원.
따라서 스택과 큐는 덱으로 대체 가능.
그래도,
push_back, pop_back 연산만 사용하면 stack,
push_back, pop_front 연산만 사용하면 queue를 사용하는 것이 좋음.
이렇게 하면 해당 객체가 어떤 역할을 수행하는지 판단할 수 있으므로 가독성 향상!
단, 스택과 큐는 default container가 deque이기 때문에, 스택과 큐가 약간 느릴 수 있지만 큰 차이는 없음.
2. STL deque
1) 생성자
1. deque<int> DQ;
2. deque<int> DQ(n); 또는 deque<int> DQ(n, val);
3. deque<int> DQ(dq.begin(), dq.end());
4. deque<int> DQ{ 1, 2, 3}; 또는 deque<int> DQ = { 1, 2, 3 };- 비어있는 덱 생성
- n개의 원소를 갖는 덱 생성
후자는 n개의 원소를 val값으로 초기화 - 다른 컨테이너의 iterator를 받아온 뒤, 순회하며 덱에 해당 범위의 원소를 채워줌
- initializer_list를 인자로 받는 생성자
2) 멤버 함수
// DQ = { }
deque<int> DQ;
// DQ = { 1, 2, 3, 4, 5 }
for (int i = 1; i <= 5; i++) DQ.push_back(i);
// DQ = { 10, 9, 8, 7, 6, 1, 2, 3, 4, 5 }
for (int i = 6; i <= 10; i++) DQ.push_front(i);
// DQ = { 7, 6, 1, 2, 3, 4, 5 }
for (int i = 1; i <= 3; i++) DQ.pop_front();
// DQ = { 7, 6, 1, 2 }
for (int i = 1; i <= 3; i++) DQ.pop_back();(1) push_back / push_front
마지막 위치에 원소를 삽입. O(1)
시작 위치에 원소를 삭제. O(1)
emplace_back, emplace_front로 대체 가능.
(2) pop_back / pop_front
마지막 위치에 원소를 삭제. O(1)
시작 위치에 원소를 삭제. O(1)
반환값은 void.
(3) insert / erase
임의의 위치에 원소 삽입 / 삭제. O(n)
시간 복잡도가 O(n)이므로 deque는 n이 클 때 insert와 erase 연산을 여러번 하기 적합하지 않음.
// 4
cout << "DQ.size() : " << DQ.size() << '\n';
// 0
cout << "DQ.empty() : " << DQ.empty() << '\n' << '\n';
// DQ = { }
DQ.clear();
// DQ = { 0 }
DQ.resize(1);
// DQ = { 0, 2, 2 }
DQ.resize(3, 2);
// DQ = { 0, 1, 2 }
DQ[1] = 1;(4) size / empty
deque의 크기를 size_t 자료형으로 반환.
deque가 비어있는지 여부를 bool 자료형으로 반환.
(5) resize / clear
deque의 크기를 변경
deque의 모든 원소를 삭제
deque의 크기를 변경.
변경될 크기가 원래의 크기보다 작은 경우, 뒤의 원소부터 차례로 지워지고,
원래의 크기보다 큰 경우, 두 번째 인자가 없는 경우 초기값, 있는 경우는 해당 값으로 남은 칸이 채워짐.
// 0 1 2
for (auto it = DQ.begin(); it != DQ.end(); it++) cout << *it << ' '; cout << '\n';
// 2 1 0
for (auto it = DQ.rbegin(); it != DQ.rend(); it++) cout << *it << ' '; cout << '\n';
// 0
cout << "DQ.front() : " << DQ.front() << '\n';
// 2
cout << "DQ.end() : " << DQ.back() << '\n';(6) begin / end
deque의 첫번째 원소를 가리키는 iterator 반환
deque의 마지막 원소의 다음 칸을 가리키는 iterator 반환
(7) rbegin / rend
begin의 reserve_iterator 버전
end의 reserve_iterator 버전
(8) front / back
DQ[0]을 reference로 반환. O(1)
DQ[n-1]을 reference로 반환. O(1)
빈 vector에서 둘을 호출하는 것은 'UB(Undefined Behavior)'
3. Q&A
-
4. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
