[바킹독의 실전 알고리즘] 0x07강 - 덱

 

정의와 성질

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

자료구조의 덱은 deque이고 Double Ended Queue라는 뜻을 가지고 있다.

 

덱의 성질

• 원소 추가/제거의 시간 복잡도는 O(1)이다.
• 제일 앞/뒤 원소 확인의 시간 복잡도는 O(1)이다.
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.
• 그러나 STL deque에서는 인덱스로 원소에 접근할 수 있다.

 

기능과 구현

배열의 형태로 덱을 구현해 보았다!

 

STL deque

STL deque은 매우 독특하게 double ended queue보다는 vector와 느낌이 비슷한데, front에서도 O(1)에 데이터의 추가와 제거가 가능하다는 느낌이 강하다.

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

STL vector에서 제공되는 기능을 STL deque에도 다 제공해주고 심지어 deque은 front에서도 O(1)에 추가와 제거가 가능하니 deque이 vector의 상위호환이라고 생각할 수 있다.

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

 

✔️ 앞쪽과 뒤쪽에서의 추가와 제거가 모두 필요하면 STL deque를 사용하는 것이 효율적이지만,

굳이 앞쪽에의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶다면 STL vector를 사용하면 된다.

 

 

출처: 바킹독님 블로그