[C++] deque, stack, queue, priority_queue

deque

 

deque는 vector와 list의 중간 정도의 컨테이너로, 여러 개의 메모리 블록을 할당하여 하나처럼 사용합니다.

 

1. vector처럼 capacity를 늘이는 과정에서 전체 copy가 일어나지 않습니다. (chunk 단위로 메모리 블록을 새로 할당 후 연결함)

2. 인덱스 접근은 가능하나, 연속적인 메모리가 아니기 때문에 포인터 연산은 불가합니다.

3. vector와 같이 처음, 끝이 아닌 중간에 삽입, 삭제하는 경우 요소를 밀어내면서 오버 헤드가 발생합니다 - O(N)

 

 

---

stack과 queue

 

LIFO의 stack과 FIFO의 queue는 위의 deque로 구현되어 있다. (STL 기준)

스택(stack)의 모습

큐(queue)의 모습

1. 두 컨테이너 모두 접근, 삽입, 삭제의 시간 복잡도가 O(1)로 아주 우수합니다. (front 혹은 back으로만 컨테이너를 제어할 수 있으므로)

2. 스택의 경우, front, back 중 하나만 top으로 사용합니다.

3. STL 큐의 경우, 원형 큐 형태를 취하지 않습니다.

 

---

priority_queue

 

최대 heap(default)으로 항상 정렬되는 vector(default), deque 기반 컨테이너입니다.

1. 최대 heap 형태를 띄므로, 접근, 삽입, 삭제가 O(log n)의 시간 복잡도를 갖습니다.

2. 그 외의 오버 헤드는 기반 컨테이너에 따라 달라집니다.

 

https://velog.io/@chappi/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-5%EC%9D%BC%EC%B0%A8-Onlogn-%EC%A0%95%EB%A0%AC-%ED%9E%99%EA%B3%BC-%ED%9E%99%EC%A0%95%EB%A0%AC-%EC%B5%9C%EB%8C%80%ED%9E%99-%EC%B5%9C%EC%86%8C%ED%9E%99-2%EB%B6%80

알고리즘 5일차 - O(nlogn) 정렬, 힙과 힙정렬 최대힙, 최소힙 - 2부