자바의정석 CH 11 컬렉션 프레임웍 - 2
2. 스택과 큐
스택 (Stack) : LIFO구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
큐 (Queue) : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.
=> 스택은 배열로 구현하는 것이 좋고, 큐는 링크드리스트가 더 적합하다.
+링크드리스트는 삭제할 때 자리이동이 없기 때문.
=> pop 삭제, push 추가, peek는 맨 위에 객체 반환, search는 indexOf처럼 찾는 것 1부터 시작
Stack에서 2 1 0의 위치가 1 2 3 이 되는 것.
Offer 저장 예외발생 X, add는 예외발생 O, poll 추출은 에외 발생 X, remove는 예외 발생 Otry-catch문 사용해야함
=> 그냥 offer poll peek만 보자.
Queue는 인터페이스이기 때문에 Stack st = new Stack() , st.push("0")이 안된다.
=> JAVA API에서 Queue 인터페이스를 구현한 클래스를 사용해야한다.
아래 인터페이스를 구현한 클래스를 찾아서 적절한 객체를 만들면 된다.
2-2 스택과 큐의 활용
스택의 활용 예 - 수식계산, 수식괄호 검사, 워드프로세서의 undo/redo, 웹 브라우저의 뒤로/앞으로
큐의 활용 예 - 최근 사용 문서(만약 최대 5개 적용할 수 있다면 가장 마지막 걸 빼야함), 인쇄 작업 대기 목록, 버퍼(buffer)
괄호의 개수가 일치하는지 확인하는 예제
=> for문으로 "("를 만나면 stack에 넣고 ")"를 만나면 "("를 꺼내는 것.
+ 예외, 꺼내야하는데 꺼낼 괄호가 없을 때에도 괄호일치X
1. trim으로 입력받은 값의 양 옆 공백을 줄이고 input에 저장
Queue q =new LinkedList(); // Queue는 인터페이스이기 때문에 이를 구현한 클래스로 저장
2. q입력 시 프로그램 종료 / help 입력 시 내용 반환 / history 입력 시 입력받은 명령어를 저장 후 반환
3. 입력받은 명령어 save() 클래스로 구현. input 값이 null 이거나 ""가 아니면 offer 저장.
만약 q.size()가 MAX_SIZE보다 많으면 첫 번째 값으로 remove().
이를 for문으로 list.size()만큼 돌려서 출력.
=> 여기서 for(int i=0; i<list.size() ; i++)보다 final int SIZE = list.size()로 선언하고 for(int=0;i<SIZE;i++)이 더 좋은 코드.
+ LinkedList에 있는 명령을 보여줘야 하기 때문에 LinkedList list = (LinkedList)q;로 형변환
3. lterator, Listlterator, Enumeration
- 컬렉션에 저장된 데이터를 접근하는데(=읽어오기) 사용되는 인터페이스
lterator에서는 next() ,읽기와 hasNext() ,확인가 핵심.
- Eenumeration은 lterator의 구 버전이기 때문에 두개가 거의 같다고 보면 된다.
- Listlterator은 lteraotr의 접근성을 향상시킨 것 (단방향 -> 양방향) 그래서 이전 요소도 읽어올 수 있다.
=> 컬렉션마다(List, Set, Map) 읽어오는 구조가 다르기 때문에 저장된 요소를 읽어오는 방법을 표준화한 것
=> 컬렉션들이 동일하게 hashNext(), next()으로 확인하고 읽어오면 사용하기가 훨씬 편리하다.
=> 컬렉션에 iterator()을 호출해서 lterator를 구현한 객체를 얻어서 사용.
iterator은 Collection에 구현되어있는 메서드라서 List와 Set이 모두 사용할 수 있는 메서드이다.
=> iterator은 1회용이라 다 쓰고 다면 다시 얻어와야한다.
while문을 for문으로 바꾸고 lterator에 next()를 get으로 바꾼 후, ArrayList를 HashSet으로 바꾸면 for문은 작동 X
=> HashSet에는 get메서드가 없기 때문, 그러나 HashSet (=>Set)도 Collection의 자손이기 때문에 iterator을 사용할 수 있어 while문에 next()는 표준화되어 있기 때문에 작동 O
+HashSet c = new HashSet(); 과 Collection c = new Hashset();의 차이 (다형성을 사용해야하는 이유)
HashSet c = new HashSet(); 으로 작성하면 만약에 HashSet()을 TreeSet()으로 변경하고 싶을 때
아래에 HashSet에서만 사용할 수 있는 메서드가 작성되어 있는지 확인해야함.
그러나 Collection c = new HashSet(); 은 Set의 조상인 Collection이 사용하는 메서드는 Set에서 사용할 수 있기 때문에
확인할 필요가 X
=> 꼭 HashSet이라고해서 HashSet c = new HashSet()인 것이 아니라
이 HashSet이 구현한 컬렉션 인터페이스만 쓴 경우엔 Collection c = new HashSet()으로 해야 더 유연한 코드가 되는 것.
3-2 Map과 lterator
- Map에는 lterator이 없다. keySet(), entrySet(), values()를 호출해야 한다. => set은 Collection의 자손이기 때
- Map는 Collection의 자손이 아니기 때문
=> entrySet는 (key, value)값을 반환하는
4. Arrays
- 배열을 다루기 편리한 메서드(static) 제공
1. 배열의 출력 - toString()
2. 배열의 복사 - copyOf(), copyOfRange() : 새로운 배열을 생성해서 반환한다.
3. 배열 채우기 - fill(), setAll()
fill -> 특정 값으로 채우기
setAll -> 람다식으로 채우기
4. 배열의 정렬과 검색 - sort(), binarySearch()
정렬하지 않고 검색하면 잘못된 결과가 나온다.
1. sort()로 배열을 정렬한다.
2. binarySearch()로 검색한다.
=> 정렬이 되어 있을 때 둘로 나눠가며 검색하면 더 효율적이기 때문에 binarySearch()가 사용 되었다.
5. 다차원 배열의 출력 - deepToString()
6. 다차원 배열의 비교 - deepEquals()
7. 배열을 List로 변환 - asList(Object ... a) <- 가변 매개 변수
=> List는 읽기 전용이라 추가하면 지원되지않는다는 예외가 발생한다.
그럴 땐 List를 내용으로 하는 새로운 ArrayList를 만들면 변경이 가능하다.
8. 람다와 스트림(14장)관련 - parallelXXX{}, spliterator(), stream()
https://github.com/castello/javajungsuk_basic/blob/master/javajungsuk_basic_src/ch11/src/Ex11_6.java
GitHub - castello/javajungsuk_basic: 자바의 정석 기초편 관련 자료입니다.
자바의 정석 기초편 관련 자료입니다. Contribute to castello/javajungsuk_basic development by creating an account on GitHub.
github.com
=> 이해해보기
참고로 for(int i : arr7)은 위 두줄을 합친 상향된 버전.
5. Comparator와 Comparable
- 객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스
Comparable : 기본 정렬기준을 구현하는데 사용 compareTo 메소드사용
Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용 compare()메서드 사
> compare()와 compareTo()는 두 객체의 비교결과를 반환하도록 작성한다.
같으면 0, 오른쪽이 크면 -, 작으면 +
Comparable은 compareTo를 구현해야한다.(=몸통을 만든다.)
=> compare()와 compareTo가 있고 각각 정렬 기준을 제공한다. (오름차순, 내림차순)
그래서 메서드 호출에서 결과값이 양수인지 음수인지에 따라 자리바꿈을 할 지 말 지를 알려준다.
strArr 첫 번째 값 => String에 Comparable의 본 정렬자로 정렬( =사전 순, 즉 대문자가 맨 앞)
strArr 두 번째 값 => 대소문자 구문 X
strArr 세 번째 값 => 역순으로 정렬
=> 역순으로 정렬할 땐 반환 값에 -1를 곱해서 역으로 변경한다.
sort(Object[] a, Comparator c) => a는 정렬 대상이고 c는 정렬 기준을 의미한다.
6. HashSet - 순서 X, 중복 X
- Set 인터페이스를 구현한 대표적인 컬렉션 클래스
- 순서를 유지하고 싶다면 LinkedHashSet클래스를 사용하면 된다.
TreeSet : 범위 검색과 정렬에 유리한 컬렉션 클래스
=> 순서와 중복이 필요없는 컬렉션을 사용하고 싶을 때 사용하면 된다.
Iterator사용법 : hasNext()로 읽어올 요소가 있는지 확인한다. 그리고 next()로 요소를 하나씩 꺼내온다.
이를 while문으로 반복하면 안에 요소가 있을 때 까지 꺼내올 수 있다.
=>set으로 저장했기 때문에 중복이 제거되었다. 순서는 순서대로 출력된 것 처럼 보이는 것이지 그냥 유지만 된 것 뿐.
=> set을 순서대로 정렬하는 방법.
sort는 List에서만 적용되기 때문에 set의 모든 요소를 LinkedList로 List에 저장해야한다.
이후 sort로 List를 정렬한 후 출력하면 순서대로 반환된다.
-HashSet은 객체를 저장하기 전 기존의 같은 객체가 있는지 확인한다. 같은 객체가 있으면 저장, 없으면 저장 X
-boolean add(Object o)메서드는 저장할 객체의 equals()와 hashCode()를 호출하여 중복인지 확인하는 것이다.
-equals()와 hashCode()가 오버라이딩 되어있어야 한다.
equals에서 person tmp = (person)obj; 로 형변환을 꼭 해줘야 한다.
=> object의 리모콘을 person으로 바꿔줘야만 tmp.name을 사용할 수 있기 때문.
return name.equals(tmp.name)에서 name에는 this가 생략되어있는 것
=> this와 obj를 비교.
=> 즉, equals는 iv를 비교하도록 오버라이딩 해야하고 hashCode도 object 클래스의 hash메서드를 이용하여
return Object.hash(name, age)로 바꾸면 된다.
new Person("David", 10)이 중복인데 set에 저장이 되어 버렸다.
- equals()와 hashCode()를 오버라이딩 해야 HashSet이 바르게 동작한다.
오른쪽처럼 hashCode()에 Objecthash메서드로 name와 age를 반환하고, equals로 iv값을 비교한다.
=> 이후 값은 David:10, abd가 나온다.
=> 교집합 합집합 차집합 구하기
7. TreeSet - 범위 탐색, 정렬O
- 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리.
=> 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
- 각 요소(node)가 나무(tree)형태로 연결
LinkedList이 변형된 구조이다.
LinkedList는 나의 데이터를 저장함과 동시에 다음 요소의 주소를 저장하는 구조를 띤다.
여기에서 변형되어 TreeSet은 나의 데이터를 저장함과 동시에 왼쪽 오른쪽의 자식 노드의 위치를 저장한다.
=> 그래서 범위 탐색과 정렬에 유리하다.
이진탐색트리 : 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다.
이진트리는 자식 노드가 2개 이하이면 되지만 이진탐색트리는 작은 값과 큰 값이 왼쪽 오른쪽에 저장되어있어야한다.
=> TreeSet은 이진탐색트리로 되어있는 것.
- 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸린다 (비교횟수가 증가하기 때문)
=> TreeSet 데이터의 저장과정 boolean add (Object o < 저장할 객체)
TreeSet에 7,4,9,1,5의 순서로 데이터를 저장하면 위와같은 과정을 거친다.
루트부터 트리를 따라 내려가며 값을 비교, 작으면 왼쪽 크면 오른쪽에 저장
add() size() remove() inEmpty() iterate()와 같은 Collection 메소드는 겹쳐서 따로 표기되어있지 않다.
=> HashSet은 순서가 없고 TreeSet은 순서가 있다.
여기서 class Test{}만 생성하면 비교기준이 없기 때문에 에러가 발생한다.
그래서 comparator를 구현하여 return값 -1 or 1로 반환하면 같은 객체가 아닌 것으로 반환한다.
참고로 return값이 0이면 객체들이 다 같은 값인 것으로 반환된다는 뜻.
+ TreeSet(비교기준 생성자 넣기< TestComp)에 넣고 출력하면 값이 나온다.
=> TreeSet은 객체(Test)가 비교기준을 가지고 있던지 TreeSet이 비교기준을 갖고 있던지 둘 중에 하나는 무조건 해야함.
어디서 제공하던지 비교기준이 필요하다.
subSet을 이용해 범위 출력
=>TreeSet은 범위 검색에 유리하다(from~to)
=> TreeSet이 범위 출력에 유리한 이유.
단점은 트리가 커질수록 추가 삭제에 시간이 오래걸린다.
8.HaspMap과 Hashtable - 순서 X 중복(키X, 값O)
- Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장한다.
- HashMap(동기화X)는 Hashtable(동기화O)의 신버전
=> HashMap과 TreeMap만 알면 된다.
> HashMap
- Map 인터페이스를 구현한 대표적인 컬렉션 클래스
- Map은 순서를 유지하지않지만 순서를 유지하려면 LinkedHashMap클래스를 사용하면 된다.
> TreeMap
- 범위 검색과 정렬에 유리한 컬렉션 클래스
- HashMap보다 데이터 추가, 삭제에 시간이 더 걸린다.
=> key, value를 저장하는 것 빼곤 TreeSet이랑 똑같다.
8-2 HashMap의 키와 값
- 해싱(hashing)기법으로 데이터를 저장. 데이터가 많아도 검색이 빠르다.
- Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장.
=> add가 아닌 put을 사용,
중복된 값이 저장되면 덮어쓴다.
객체배열을 객체지향적인 코드로 짜는 것이 더 좋다.
8-2 hashing 해싱
: 해쉬함수를 해시테이블에 데이터를 저장하고 읽어오는 것.
- 해시테이블은 배열과 링크드 리스트가 조합된 형태
-> 배열의 장점인 접근성과 링크드리스트의 장점인 변경이 유리하게 하려고.
해시함수는 object.hash()로 작성하면 된다.
=> hashing을 사용하는 클래스는 Hashtable, HashMap, HashSet가 있고 다 hashCode라는 메서드를 사용한다.
이를 사용할 땐 hashCode도 같이 오버라이딩 해야 하고object.hash(객체 넣기)로 하면 된다.
해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야한다. (저장하고 읽어올 때 7을 읽을 때 7을 읽어야하니까)
서로 다른 키라도 같은 값의 해시코드를 반환할 수 있다.
9. Collections
- 컬렉션을 위한 메서드 (static)을 제공
+ static은 object(객체 생성), Arrays(배열), Collections(컬렉션)에 있다.
1. 컬렉션 채우기, 복사, 정렬, 검색 - fill(), copy(), binarySearch() 등이 있다.
2. 컬렉션의 동기화 - synchronizedXXX()
=> Vector과 ArrayList는 특징은 모두 같지만 Vector은 동기화가 되고 ArrayList는 동기화가 안된다.
사용법 : ArrayList(동기화 되지 않은 List)를 Collection의 synchronizedXXX메서드에 넣으면 동기화가 되는 것이다.
= Vector를 사용하는 것과 같음
3. 변경불가(readOnly) 컬렉션 만들기 - unmodifiableXXX()
=> 수정할 수 없도록 보호할 때 사용
4. 싱글톤 컬렉션 만들기 - singletonXXX()
=> 객체 1개만 저장할 수 있도록 하는 것
5. 한 종류의 객체만 저장하는 컬렉션 만들기 - checkedXXX()
=> 원래 Collection에는 여러가지 종류의 객체를 저장할 수 있지만 checkedXXX를 쓰면 한가지 타입만 저장 O
add(object)라서 모든 종류의 객체를 담을 수 있는데 checked를 사용했으므로 String만 저장 가능하다.
=> binarySearch()를 사용하기 위해선 sort()를 먼저 사용해야 한다는 점 잊지 말기!
=>disjoint(object 1, object 2) 2개의 공통요소가 없으면 true를 반환
=>copy(object1, object 2)는 2를 1로 카피하는 것
10. Collection 클래스 총 정리
가장 처음 배운 것은 ArrayList와 Vector(Object [])
이 둘의 특징은 Object기반이라는 것이고 배열 기반으로 생성한다는 점이다.
>이를 이용해서 만든 것이 Stack이다. (LIFO, 선입 후출 구조)
배열의 단점은 추가, 삭제가 불리하기 때문에 이를 개선한 것이 LinkedList이다. ( 연결기반)
>이를 이용해서 만든 것이 Queue이다 (FIFO, 선입 선출 구조)
이 둘의 검색기능을 향상시킨 것이 HashMap과 Hashtable(Object, Object)이다.
>HashMap은 배열과 LinkedList를 결합한 것이고 이를 Hashtable이라고 부르는 것이다.
>HashMap은 배열의 장점과 LinkedList의 장점을 합한 것. HashMap은(key, value)를 쌍으로 저장한다.
>HashMap은 new 버전 Hashtable은 구버전
TreeMap은 연결기반은 변형한 것으로 트리처럼 되어있다.
> 검색과 범위검색, 정렬기능이 향상된 버전이다. + 이진트리, 중위 순회하며 정렬됨
HashMap과 TreeMap에서 Key부분만 가지고 만든 것이 HashSet, TreeSet이다.
HashMap의 변형으로 Properties이다.
>HashMap 저장 타입은 (Object, Object)이지만 Properties는 (String key, String value)이다.
>파일에 읽기와 쓰기에 용이하다.
HashMap은 Map의 특징으로 (set도 마찬가지지만) 순서를 유지하지 않는다.
>그래서 순서유지 기능을 향상시킨 것이 LinkedHashMap이다.