Deque(및 Queue, stack)의 메모리 관점에서 구현 방식

dequeue

deque는 양 쪽에서 push와 pull이 가능한 자료구조 이다.

 

list는 linked list형태로 제작되었고, vector는 연속된 메모리 공간에 존재한다.

 

그럼 deque는?

 

→ 둘 다 좀 다름

deque의 경우 각 object를 가리키는 pointer들의 연속된 집합으로 이루어짐.

 

value 값은 다른 공간에 저장을 해두고, 그 공간을 가리키는 pointer만 연속적으로 저장

 

 

장점

• Random Access도 가능함
• 연속적인 공간의 크기가 작아도 됨
  • Pointer의 작은 크기 덕에 다른 자료형을 연속적으로 저장하는 것보다 작음
  • vector는 크기가 커질 때, 다른 공간에 복사하는 작업이 필요 → deque는 이런 작업이 적게 일어남.

단점

• Random Access시에 한 단계 더 거치기에 vector보다 약간 더 느릴 것 (아주 약간)

 

 

     다만, vector와 비교했으나 두 자료구조의 사용법과 상황이 다르므로 직접적으로 뭐가 더 좋다는 뜻은 아니다.

 

 

Queue & Stack

queue는 deque나 list를 기반으로 구현

Stack도 deque나 vector를 활용해서 구현