deque 검색 결과

해당 글 2건
랜덤 접근이 가능한 deque 자료구조를 chunk로 구현하면 어떤 이점이 있을까요?

deque를 공식 레퍼런스 사이트에서 보면, Chunk로도 구현이 된다고 되어 있습니다. 그러면, Chunk로 구현했을 때, 장점이 무엇일까요? 일단, deque가 Random 접근이 되려면, 기본적으로 연속적이여야 합니다. List는 Random access를 지원하지 않습니다. 더 정확히 이야기 하면, base 주소가 있고, 그것을 통해서 i번째 index에 접근할 수 있어야 합니다. 1차 구조의 덱을 생각해 보겠습니다. 원래 4개의 원소가 있었고, 5를 어딘가에 추가한다고 해 보겠습니다. 원래 capacity가 4였다면, 하나를 추가하려는 순간 추가하지 못하게 될 겁니다. 그러므로 확장 연산이 수행이 될 겁니다. 그러면 확장된 후에 기존의 원소가 어떻게 들어가는 것이 좋을까요? 이렇게 들어가는 것이..
자료알고/자료구조 2020. 4. 7. 01:08
자료구조 덱 (deque) : 앞과 뒤에서 추가되고 삭제된다.

자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다. 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다. 먼저 다음과 같이 초기화를 시켜 봅시다. 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. ..
자료알고/자료구조 2019. 8. 22. 01:05