cyphen156

마지막으로 구현할 선형 자료구조는 우선순위 큐이다.우선 순위 큐는 기본적으로 비 선형 자료구조인 Heap을 응용하여 만들어진 자료구조다. 그런데 캐시 친화성을 살짝 고려하자면 이차원 배열 또는 청크 기반 포인터 배열을 통해 같은 우선순위를 갖는 자료형 끼리는 캐시 친화도를 높여 캐시 친화성을 높여줄 수 있다. 우선 이 글에서는 STL에 맞도록 Heap을 기반으로 작성하고, 이 다음 글에서 올 Chunk - Based-Deque를 구현한 후 vector의 어댑터 클래스로 변형하여 구현해보도록 하겠다.PriorityQueue 우선순위 큐는 선입선출의 기능을 갖고 있는 자료구조이다.기존 큐와는 다르게 자료에 우선순위가 부여되어 우선순위에 따라 출력 순서가 제어된다. 📌 구현 목표본 글에서는 Priority ..

선형 자료구조 중 꽃이라 할 수 있는 Deque다. 앞서 글에서 보았듯 STL에서는 Deque를 통해 Stack과 Queue를 구현한다.이 작업이 끝나면 Deque의 자료형을 단순 1차원 배열에서 Chunk Base Block을 통해 더 빠른 인덱싱이 가능하도록 수정하고, Stack과 Queue를 어댑터 클래스로 적용한다.Deque(Double-Ended Queu)덱는 선입선출의 기능을 갖고 있는 자료구조이다.큐와는 다르게 자료의 입출력이 자료구조의 앞과 뒤 모두에서 일어날 수 있다. 📌 구현 목표본 글에서는 Deque(덱) 자료구조를 직접 구현템플릿 기반으로 자료형에 독립적인 구조를 구성내부적으로는 동적 배열을 사용하여 크기 확장(reallocation)을 지원다음 주요 연산 지원Push_Front(..

스택 다음으로 구현할 자료구조는 Queue다.사실 STL 문서를 뒤적이다가 알게 된 것인데, Stack과 Queue는 사실 뒤에 나올 Deque를 통해 구현된 어댑터 패턴이 적용된 클래스이다. 기본 구현은 이미 Deque를 통해 구현되어 있지만, 메서드 hiding을 통해 필요한 부분만 사용자에게 노출시키는 전략을 사용한다.하지만 우리는 다시 구현하는 입장이기 때문에 우선 Stack과 Queue를 구현한 뒤, Deque를 구현하고 나서 어댑터를 통해 Stack과 Queue 클래스를 수정하도록 하겠다.Queue큐는 선입선출의 기능을 갖고 있는 자료구조이다.📌 구현 목표본 글에서는 Queue(큐) 자료구조를 직접 구현템플릿 기반으로 자료형에 독립적인 구조를 구성내부적으로는 동적 배열을 사용하여 크기 확장(..

배열은 기본 자료형이니 구현하지 않고 넘어간다.리스트는 배열로 대체할 수 있으니 구현하지 않는다.그렇다면 남은것은 Stack, Queue - Deque / Priority Queue다.이 글에서 구현할 것은 Stack이다. 가변길이 할당과 템플릿 기반으로 구현하도록 하겠다.📌 구현 목표본 글에서는 Stack(스택) 자료구조를 직접 구현템플릿 기반으로 자료형에 독립적인 구조를 구성내부적으로는 동적 배열을 사용하여 크기 확장(reallocation)을 지원다음 주요 연산 지원Push, Pop : O(1) / 재할당 시 O(n) Top : O(1) Empty, Size : O(1) Clear : O(1) 복사 생성자와 대입 연산자를 통한 얕은 복사 방지(Deep Copy)도 고려🧱 프로젝트 구조Sta..