[(PS)DataStructure] 덱

바킹독님의 강의를 참고하였습니다.

https://blog.encrypted.gg/category/강좌/실전%20알고리즘

'강좌/실전 알고리즘' 카테고리의 글 목록

+ 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드.

+ 기록해두고 싶은 부분만 정리해 둠.

---

정의&성질

덱

양쪽 끝에서 삽입과 삭제가 전부 가능하다.

=> 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮다.

 

자명함.

---

STL deque

STL deque은 독특하게도, vector랑 비슷한데, front에서도 O(1)에 추가와 제거가 가능한 느낌이 강하다.

insert, erase도 있고, 인덱스로 원소에 접근도 할 수 있다.

 

이와 같이, STL vector에서 제공되는 기능을 STL deque에서도 다 제공해 주고

심지어 deque는 front에서도 O(1)에 추가/제거가 가능하니, deque이 vector보다 상위호환이 아닌가?

라는 생각이 들 수 있지만,

vector와 달리 deque은 모든 원소들이 메모리상에 연속하게 배치되어 있지 않다.

💡따라서, 앞쪽과 뒤쪽에서의 추가/제거가 모두 필요하면 당연히 STL deque을 사용하는 게 효율적이지만, 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶을 땐 STL vector를 사용하면 된다.

---

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    deque<int> dq;
    dq.begin(); // 덱의 첫 번째 원소를 가리키는 "반복자"
    dq.end(); // 덱의 마지막 원소를 가리키는 "반복자"
    dq.front(); // 덱의 첫 번째 원소
    dq.back(); // 덱의 마지막 원소
    dq.at(n); // 덱의 n번째 요소
    dq.push_front(x); // 덱의 첫 번째 원소에 'x' 추가
    dq.push_back(x); // 덱의 마지막 원소에 'x' 추가
    dq.pop_front(); // 덱의 첫 번째 원소 삭제
    dq.pop_back(); // 덱의 마지막 원소 삭제
    dq.insert(dq.begin()+1,y); // 덱의 begin()+1 위치에 y추가
    dq.erase(dq.begin()+2); // 덱의 dq.begin()+2의 위치의 값 삭제
    dq.size(); // 덱의 원소 개수 리턴
    dq.empty(); // 덱이 비어있는지 확인
    dq.clear(); // 덱의 전체 원소 clear
}

STL deque는 이렇게 사용가능하다.

(더 있는데 궁금하면 구글링 ㄱㄱ)