본문 바로가기

# Foundation/자료구조

덱 (데크)

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

벡터의 한계

  • 벡터는 첫 지점에서 데이터 삽입/삭제의 성능이 떨어짐.
  •    앞에도 청크를 붙이면 되는거 아냐?
  • →   덱(데크)의 등장




덱 (데크)

앞 뒤로 유동적인 확장이 가능한 고수준 배열.

벡터처럼 여러개의 배열(청크)가 모여 하나의 데크를 이룬다.


앞이 꽉 찬 상태에서,  앞에 데이터 삽입을 시도하면,  앞에 새로운 청크를 덧붙이고.

뒤가 꽉 찬 상태에서,  뒤에 데이터 삽입을 시도하면,  뒤에 새로운 청크를 덧붙인다.


 


덱 (데크)의 특성 

  • 여러개의 독립적인 배열(청크)을 접한한 것 이다.
  • 논리적 수용량의 제한이 없다.
  • 어느 위치에서든 데이터를 가져오는 것은 빠르다.  (상수시간)
  • 중간 위치의 데이터를 가져올 때, 인덱스 계산으로 인한 약간의 오버헤드가 있다.  (그래도 상수시간)
  • 중간에 위치한 데이터를 삽입/삭제하는 것은 느리다.  (선형시간)
  • 처음이나 마지막에 데이터를 삽입/삭제하는 것은 빠르다.  (상수시간)
  • 새로운 배열을 앞, 뒤에 붙일 때 큰 오버헤드가 있다.


스택 + 큐 = 덱(데크)?

스택과 큐는 ADT.

덱(데크)는 자료구조 중 하나.



  • 덱 (데크)
  • =  앞 뒤로 데이터를 삽입/삭제할 수 있는 자료구조.
  •  인덱싱이 가능한 고수준 배열
  • ≠ 스택 + 큐



비슷한 스펙의 구현

환형 배열(원형 배열)과 성능이 비슷하다.

데크와 달리 유동적으로 수용량을 확장할 수 없는데,
데이터를 넣다보면, 언젠가는 꽉차서 넣을 수 없게된다.



'# Foundation > 자료구조' 카테고리의 다른 글

트리 ADT  (0) 2019.02.06
그래프 ADT  (0) 2019.02.06
환형 배열 (원형 배열)  (0) 2019.02.03
큐 ADT  (0) 2019.02.03
스택 ADT  (0) 2019.02.03