링버퍼를 사용하면 디큐(deque)시 발생하는 요소 이동 문제를 해결할 수 있다. 2021/01/05 - [분류 전체보기] - 자바(JAVA)로 큐(Queue) 구현하기 public class IntQueue { private int max; private int num; private int[] que; private int front; private int rear; // 예외 : 큐가 비어 있음 class EmptyIntQueueException extends RuntimeException{ } // 예외 : 큐가 가득 참 class OverflowIntQueueException extends RuntimeException{ } public IntQueue(int capacity){ num = fr..
프로그래밍 노트/자료구조
public class IntAryQueue { private int max; // 큐 용량 private int num; // 현재 데이터 수 private int[] que; // 큐 본체 private int front; private int rear; // 예외 : 큐가 비어 있음 class EmptyIntQueueException extends RuntimeException{ } // 예외 : 큐가 가득 참 class OverflowIntQueueException extends RuntimeException{ } public IntAryQueue(int capacity){ num = front = rear = 0; max = capacity; try { que = new int[capacity]..
public class IntStack { private int max; // 스택 용량 private int ptr; // 스택 포인터 private int[] stk; // 스택 본체 // 예외 : 스택이 비어 있음 class EmptyIntStackException extends RuntimeException{ } // 예외 : 스택이 가득 class OverflowIntStackException extends RuntimeException{ } // 생성자 public IntStack(int capacity){ ptr = 0; max = capacity; try { stk = new int[max]; }catch(OutOfMemoryError e){ max = 0; } } public int pu..
이진 탐색 트리(binary search tree, BST)트리로 구현된 맵의 성능을 시험. MyTreeMap 클래스를 구현하고, 문제점을 알아본 후 자바의 TreeMap 클래스가 어떻게 문제를 해결했는지 알아보자. 내부 class인 Node 클래스를 구현1234567891011protected class Node{ public K key; public V value; public Node left = null; public Node right = null; public Node(K key, V value){ this.key = key; this.value = value; }}cs 노드를 찾는 findNode 메서드 구현1234567891011121314151617181920212223private No..
이진 탐색 트리(binary search tree, BST)요소가 정렬된 Map 인터페이스를 구현할 때 유용하게 쓰임 해싱의 문제점HashMap 클래스의 연산이 상수 시간이더라도 해싱이 느릴 수 있음(상수가 꽤 커질 수 있음)해시 함수를 설계하는 것이 쉬운일이 아니며, 키가 특정하위 맵에 집중되면 성능이 나빠질 수 있음키는 어떤 순서대로 저장되지 않음(테이블이 커지고 키가 재해시될 때 변하기도 함). 어떤 응용 프로그램에서는 키를 순서대로 유지하는 것이 필요하거나 유용할 때가 존재 Java에서는 TreeMap클래스를 제공TreeMap은 해시 함수를 사용하지 않음. 해싱 비용과 해시 함수를 고르는 어려움을 피할 수 있음키는 이진탐색트리에 저장되는데, 선형시간으로 키를 순서대로 순회할 수 있음핵심 메서드는 ..
Map 인터페이스 구현 MyHashMaphashing을 이용한 MyBetterMap은 여전히 성장차수는 선형이었다. (MyBetterMap 포스팅) n개의 엔트리와 k개의 하위 맵이 있다면 하위 맵의 크기는 평균 n/k가 되고, 여전히 n에 비례하게 된다.하지만, n과 함께 k를 늘려간다면 n/k의 크기를 제한할 수 있다. 하위 맵당 엔트리의 개수가 일정하면 단일 하위 맵은 상수시간으로 검색이 가능(해시 함수를 계산하는 것 => 상수시간)MyHashMap 클래스는 MyBetterMap 클래스를 확장하므로 MyBetterMap에 정의된 메서드를 상속한다. 123456789101112131415161718192021222324252627282930public class MyHashMap extends MyB..
해싱의 동작방식해시함수의 근본적인 요구사항은 같은 객체는 매번 같은 코드를 만들어야된다는 것이다. 불변객체(immutable object)일 때는 상대적으로 쉽지만, 가변 객체(mutable object)일 때는 고민이 필요하다. 불변객체(immutable object)의 예객체를 생성할 때 항상 생각해야하는게 equals, hashcode 의 오버라이드 이다.두 메서드는 일치해야 하는데, equals 메서드가 true 이면 해시코드 또한 같아야 한다. 하지만 이 요구사항은 단방향 이기 때문에 두 객체의 해시 코드가 같더라도 그들이 같은 객체일 필요는 없다.String 객체를 캡슐화하는 SillyString 클래스를 정의12345678910111213141516171819202122232425public..
Map 인터페이스 구현 (MyBetterMap)MyLinearMap클래스보다 Map 인터페이스를 더 잘 구현한 MyBetterMap 정의 MyBetterMap을 좀 더 효율적으로 만든 해싱(hashing)을 소개 해싱(hashing)MyLinearMap 클래스의 성능 향상을 위해 MyLinearMap 객체의 컬렉션을 포함하는 MyBetterMap이라는 새로운 클래스를 정의내장된 맵에 따라 키를 나누므로 각 맵의 엔트리 개수는 더 줄어들고, 이 것은 findEntry 메서드와 그 것을 호출하는 메서드의 속도를 빠르게 함.123456789101112131415161718public class MyBetterMap implements Map { protected List maps; MyBetterMap(int..
Map 인터페이스의 구현 (MyLinearMap) Map 인터페이스의 여러 구현 중 하나는 해시 테이블(hash table)에 기반을 두는데 지금까지 발명된 자료구조 중 단연 으뜸이다. 해시 테이블을 설명하기에 앞서 키-값 쌍으로 이루어진 리스트를 사용하여 간단한 Map 인터페이스를 구현해 본다. MyLinearMap 객체에는 단일 인스턴스 변수 entries가 있는데 Entry객체들을 담은 ArrayList이다. (Entry 클래스는 MyLinearMap의 inner class) public class MyLinearMap implements Map { // MyLinearMap 기본 구현 private List entries = new ArrayList(); public class Entry impl..
성능을 비교할 자료구조는 세가지 이다.앞에서 구현한 MyArrayList, MyLinkedList 와 Java에서 구현되어 있는 LinkedList 이다.앞에서 구현한 MyLinkedList와 Java에서 구현된 LinkedList 차이점은 MyLinkedList는 List 인터페이스만 구현하였고, LinkedList는 List와 Deque 인터페이스를 구현한 이중 연결 리스트이다. 구분 MyArrayList MyLinkedList LinkedList add(끝) 1 n 1 add(시작) n 1 1 add(일반적) n n n get/set 1 n n indexOf/lastIndexOf n n n isEmpty/size 1 1 1 remove(끝) 1 n 1 remove(시작) n 1 1 remove(일반..
