강의
https://www.youtube.com/watch?v=0mEzJ4S1d8o
특징
double-ended queue
원소의 추가 O(1)
원소의 제거 O(1)
STL dequeue은 인덱스로 접근이 가능하다. (STL queue는 인덱스로 접근 불가능!)
STL vector vs deque
https://velog.io/@nnnyeong/자료구조-스택-Stack-큐-Queue-덱-Deque
| vector | deque |
|---|---|
| 메모리에 연속적으로 배치 돼 있다 | 메모리에 연속적으로 배치 돼 있지 않다 |
| vector는 1차원 배열 형태로 관리된다. 추가 할당이 필요할 경우 기존 메모리의 2배만큼 메모리를 추가로 할당하고 기존 내용을 복사한다. | deque은 chunk로 관리된다. 연속된 메모리가 아니라 군데 군데 흩어져 있고, 기존 chunk가 다 찼다면 새로운 chunk를 하나 만들어서 메모리를 추가할당 한다. 따라서 vector보다 추가 메모리 할당이 훨씬 저렴하다. |
구현
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];
}덱에서는 양쪽으로 늘어나거나 줄어들 수 있기 때문에 초기 head tail 값을 MX(중간)로 둬야 함
문제
https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x07.md
10866
간단한 deque 문제. STL deque 말고 직접 구현해서 풀었다
1021
간단했던 문제. 왼쪽으로 회전 시키거나 오른쪽으로 회전 시키거나 연산은 둘 중 하나. 이 때 왼쪽으로 회전시킨 수가 n이라면 오른쪽으로 회전시키는 데 필요한 연산은 deque.size() - n. 무조건 왼쪽으로 회전시키고 그 수가 size / 2 + 1보다 크다면 오른쪽으로 연산시킨 횟수를 더해줌
5430
deque을 사용한다면 쉬운 문제. R이 입력으로 들어오면 front/back을 결정하는 flag를 반전시켜준다. D일 때는 flag에 따라서 pop_front()를 할지 pop_back()을 할지 결정해준다.
11003
대박 3일만에 맞힘;;
플래티넘 문제 첨 맞혀봐
생각보다 훨씬 간단한 거였음!!
point)
- 입력받을 값과 인덱스를 pair로 묶어서 덱에 저장한다.
- 덱이 오름차순으로 유지될 수 있게 한다.
- 덱에 있는 원소들의 범위는
(i- L + 1) ~ i가 되게 한다.
오름차순으로 유지되게 하는 법: dq.back()이 push_back() 할 값보다 크면 pop() 시킨다.
그리고 나서 dq.push(make_pair(x, i)) 를 한다.
그리고 res[i] = dq.front()를 한다.
그리고 dq.front().second가 (i- L + 1)이면 pop_front()를 한다. 덱의 범위를 (i - L + 1) ~ i 로 유지시키기 위해서.
