덱 (데크)

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

    https://github.com/AeroCodeX/

벡터의 한계

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

덱 (데크)

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

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

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

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

 

덱 (데크)의 특성

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

스택 + 큐 = 덱(데크)?

스택과 큐는 ADT.

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

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

비슷한 스펙의 구현

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

데크와 달리 유동적으로 수용량을 확장할 수 없는데,

데이터를 넣다보면, 언젠가는 꽉차서 넣을 수 없게된다.