🤔 해시?, 해시 테이블(Hash Table)? 해시 테이블을 알아보기 전에 해시(Hash)에 대해서 알아보겠습니다. 📌해시(Hash) 임의의 길이의 데이터를 고정된 길이의 값으로 매핑한 값을 말하며 해시 함수에 의해 매핑됩니다. 이때 매핑 전 원래 데이터를 키(Key), 매핑 후 고정된 길이의 값을 해시, 해시값(hash value) 매핑하는 과정을 해싱(hashing)이라고 합니다. 해시 함수에 의해 매핑된 해시값은 배열의 인덱스로 사용되고, 인덱스를 사용하여 값을 저장하거나 검색하게 됩니다. 📌 해시 테이블(Hash Table) '저장된 자료의 양에 상관없이 평균 상수 시간 작업이 가능하게 할 수는 없을까?' 라는 질문을 시작으로, 자료를 검색, 삽입, 삭제하는 데 평균 O(1) 시간(상수시간)이 ..
🤔 Deque? Deque는 'Double Ended Queue'의 약자로 큐의 기능을 확장한 자료구조로 볼 수 있습니다. 큐는 뒤쪽(rear)에서 삽입 앞쪽(front)에서 삭제 연산이 가능했다면 기능을 확장하여 큐의 양쪽에서 모두 삽입과, 삭제가 가능합니다. 즉, stack의 LIFO과 queue의 FIFO 특징을 모두 사용할 수 있습니다. ✔ Deque 구현하기 큐를 확장한 자료구조임으로 이전에 만든 큐 인터페이스를 implements하여 기능을 추가하여 구현 하겠습니다. 실제 자바의 덱 자료구조에는 여러가지 기능을 하는 메서드들이 더 있지만, 덱의 가장 큰 특징인 양쪽에서의 삽입,삭제에 관한 기능을 구현하도록 하겠습니다. 메소드명 리턴 타입 설명 offerFirst(E e) E 큐의 첫 번째(Fr..
🤔 Queue? '대기열'이라고 생각하면 이해가 쉬울 것 입니다. 흔히 게임에서 '큐 돌린다', '큐 잡혔다' 같은 말을 들은적이 있을 것 입니다 이때 큐는 Queue를 의미합니다. 큐는 FIFO(First In First Out)선입선출 즉, 먼저 들어간것이 먼저 빠진다 라는 특징이 있습니다. 즉 대기열처럼 데이터를 시간 순서에 따라 순차적으로 처리할때 쓰일 수 있습니다. 한쪽 끝에서는 삽입, 반대쪽 끝에서는 삭제 작업이 이루어지는 자료구조 입니다. ✔ Queue 인터페이스 만들기 실제 자바의 큐 인터페이스 에는 더 많은 메소드들이 있지만 큐의 특징적인 메소드만 우선 만들어보고 추후에 큐의 기능을 확장한 덱(Deque) 자료구조도 만들어보기 위해 최소한의 메소드만 만들어 보겠습니다. 메소드 메소드명 리..
