덱
📢 큐와 동일한 형태를 가지지만 앞, 뒤에서 자료를 삽입 또는 제거할 수 있는 컨테이너
Double-Ended Queue
덱은 앞 뒤로 제거 및 삽입이 가능한 큐 라고 생각하면 됩니다. 위의 그림처럼 A를 앞에서 넣든 뒤에서 넣든 모두 가능해요. 또한 C를 앞과 뒤 어느 쪽에서든 제거가 가능합니다.
🎨 내부 메서드 (C++)
양 쪽으로 사용이 가능하므로 매서드도 일반 큐에 비해 많은 메서드를 가지고 있어요.
그리고 C++ STL에 정의되어 있어서 헤더에 #include <deque>를 선언하면 됩니다.
deque 생성방법
-
deque<int> deque1;
비어있는 deque 생성 -
deque<int> deque1(5);
5개의 0를 가진 deque 생성 -
deque<int> deque1(3, 10);
3개의 10을 가진 deque 생성 -
deque<int> deque2(deque1);
deque1의 값을 이용해 deque2 생성
| 메서드 이름 | 역할 |
|---|---|
| empty | 덱 내부가 비어있는지 알려줌 |
| size | 덱 크기 반환 |
| front | 덱 가장 위의 요소 반환 |
| back | 덱 가장 뒤 요소 반환 |
| push_front | 덱 앞에서 요소 삽입 |
| push_back | 덱 뒤에서 요소 삽입 |
| pop_front | 덱 앞에서 요소 제거 |
| pop_back | 덱 뒤에서 요소 제거 |
| clear | 덱 내부 전체 제거 |
| swap | 덱끼리 내부 요소 교환 |
empty
deque1.empty();deque가 비어있다면 true 아니라면 false 반환
size
deque1.size();deque의 크기를 정수형으로 반환
front
deque1.front();deque의 앞의 요소를 반환
back
deque1.back();deque의 뒤 요소를 반환
push_front
deque1.push_front(10);deque 앞에서 요소 삽입
push_back
deque1.push_back(20);deque 뒤에서 요소 삽입
pop_front
deque1.pop_front();deque 앞에서 요소 제거
pop_back
deque1.pop_back();deque 뒤에서 요소 제거
clear
deque1.clear();deque 내부 전체 제거
swap
deque<int> dequeFirst, dequeSecond;
dequeFirst.swap(dequeSecond);deque끼리 내부 요소 교환
✨ Vector의 성질도 지닌 덱
Deque은 Vector의 성질도 지니고 있어서 아래와 같은 메서드도 지원해요.
| 메서드 이름 | 역할 |
|---|---|
| assign | 원하는 값으로 원하는 개수의 요소 할당 |
| [index] | deque의 index의 값을 반환 |
| at | [index]와 동일 |
| resize | deque의 크기를 재설정 |
| begin, end | 각각 시작, 끝의 iterator 반환 |
| rbegin, rend | 각각 reversed된 시작, 끝의 iterator 반환 |
| cbegin, cend | 각각 시작, 끝의 const_iterator 반환 |
| insert | 원하는 위치에 요소 삽입 |
| erase | iterator를 이용해 원하는 위치 요소 제거 |
assign
deque1.assign(n1, n2);n1개의 n2 할당
[]연산자
deque1[3];deque의 해당 index의 값을 반환
at
deque1.at(3);[index]와 동일하지만 [index]보다 속도가 느리다
resize
deque1.resize(n);deque의 크기를 n만큼 재설정
크기가 더 커지면 비어있는 요소는 0으로 초기화
deque1.resize(n, 10);0이 아닌 다른 값으로 초기화 하고 싶다면 n 다음 매개변수에 초기화 하고 싶은 값 입력
begin, end | rbegin, rend | cbegin, cend
deque<int>::iterator it = deque1.begin();
while (it != deque1.end())
cout << ' ' << (*it)++;위의 코드는 deque1의 내부 요소들을 모두 하나씩 출력 하는 코드
- 시작, 끝의 iterator 반환
- 각각 reversed된 시작, 끝의 iterator 반환
- 각각 시작, 끝의 const_iterator 반환
insert
deque1.insert(n1, n2);n1 위치에 n2 삽입
n1 위치의 iterator 반환
deque1.insert(n1, n2, n3);n1 위치에 n2개의 n3 값을 삽입
iterator 반환 하지 않음
erase
deque1.erase(deque1.begin() + 5);iterator를 이용해 원하는 위치 요소 제거
위의 코드는 deque1의 6번째 요소 값을 제거하는 코드
⏰ 시간 복잡도
삽입(Insert), 제거(Delete)
- 덱의 양쪽에서 이루어지는 연산이에요.
- O(1)의 시간 복잡도를 가져요.
탐색(Search)
- 덱 내부에서 원하는 데이터를 찾을 때까지 연산을 수행해요.
- O(n)의 시간 복잡도를 가져요.
📋 예제
백준 5430 - AC
백준 5430 - 해답
백준 3190 - 뱀
백준 3190 - 해답
