[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 덱(Deque)
- STL deque
- Q&A
- 마치며
- 덱(Deque, Double Ended Queue)
: 양쪽 끝에서 원소 넣거나 뺄 수 있는 자료구조
스택과 큐는 덱의 특수한 예시라고 볼 수도 있음.
단, STL deque는 인덱스로 원소에 접근 가능함.
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];
}
STL queue는 double ended queue보다는 vector의 느낌이 강함.
pop_front, push_front, pop_back, push_front는 그렇다 하지만,
insert, erase, 인덱스 접근도 가능.
vector는 1.5 ~ 2배로 늘려서 전체를 재할당함.
따라서 vector에 비해 확장 비용을 줄여줌.
단, iterator 간의 연산은 가능.
덱은 스택과 큐의 연산을 모두 지원.
따라서 스택과 큐는 덱으로 대체 가능.
그래도,
push_back, pop_back 연산만 사용하면 stack,
push_back, pop_front 연산만 사용하면 queue를 사용하는 것이 좋음.
이렇게 하면 해당 객체가 어떤 역할을 수행하는지 판단할 수 있으므로 가독성 향상!
단, 스택과 큐는 default container가 deque이기 때문에, 스택과 큐가 약간 느릴 수 있지만 큰 차이는 없음.
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 };
// 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();
마지막 위치에 원소를 삽입. O(1)
시작 위치에 원소를 삭제. O(1)
emplace_back, emplace_front로 대체 가능.
마지막 위치에 원소를 삭제. O(1)
시작 위치에 원소를 삭제. O(1)
반환값은 void.
임의의 위치에 원소 삽입 / 삭제. 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;
deque의 크기를 size_t 자료형으로 반환.
deque가 비어있는지 여부를 bool 자료형으로 반환.
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';
deque의 첫번째 원소를 가리키는 iterator 반환
deque의 마지막 원소의 다음 칸을 가리키는 iterator 반환
begin의 reserve_iterator 버전
end의 reserve_iterator 버전
DQ[0]을 reference로 반환. O(1)
DQ[n-1]을 reference로 반환. O(1)
빈 vector에서 둘을 호출하는 것은 'UB(Undefined Behavior)'
-
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.