컬렉션 프레임워크 (2)

Stack과 Queue

Stack

LIFO (Last In First Out)

메소드	설명
boolean empty()	스택이 비어있는지 알려준다.
Object peek()	스택의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지 않음
Object pop()	스택의 맨 위에 저장된 객체를 꺼낸다
Object push(Object item)	스택에 객체(item)을 저장
int search(Object o)	스택에서 주어진 객체를 찾아서 그 위치를 반환. 못찾으면 -1을 반환.(배열과 달리 위치는 0이 아닌 1부터 시작)

Queue

FIFO (First In First Out)

메소드	설명
boolean add(Object o)	지정된 객체를 큐에 추가한다. 저장공간이 부족하면 예외 발생
Object remove()	큐에서 객체를 꺼내 반환
Object element()	삭제없이 요소를 읽어온다. peek와 달리 뷰가 비었을 때 예외 발생
boolean offer(Object o)	큐에 객체를 저장. 성공하면 true 실패하면 false 반환
Object poll()	큐에서 객체를 꺼내서 반환. 비어있으면 null 반환
Object peek()	삭제없이 요소를 읽어온다. 비어있으면 null 반환

자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만 큐를 Queue인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue인터페이스를 구현한 클래스들이 있어서 이 들 중의 하나를 선택해서 사용하면 된다.

PriorityQueue

Queue인터페이스의 구현체 중의 하나로, 저장 순서에 관계없이 우선순위가 높은 것 부터 꺼내게 된다는 특징이 있다. 그리고 Null을 저장할 수 없다. 객체를 저장할 경우, 각 객체의 크기를 비교할 수 있는 방법을 제공해야 한다.

Deque(Double-Ended Queue)

Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Dequq은 양쪽 끝에 추가/ 삭

Iterator, ListIterator, Enumeration

Iterator

컬렉션 프레이웍에서는 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화함.

메서드	설명
boolean hasNext()	읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환
Object next()	다음 요소를 읽어온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전
void remove()	next()로 읽어 온 요소를 삭제한다

List list = new ArrayList();
Iterator it = list.iterator();

while(it.hasNext()) {
	System.out.println(it.next());
}

ListIterator

Iterator에 양방향 조회 기능 추가(List를 구현한 경우만 사용 가능)

Enumeration

Iterator의 구버전

HashSet

해싱을 이용해 구현.

HashSet은 Set 인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다.

Hashset은 새로운 요소를 추가할 때는 add메서드나 addAll메서드를 사용하는데, 만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다. 이러한 HashSet의 특징을 이용하면, 컬렉션 내의 중복 요소들을 쉽게 제거할 수 있다.

ArrayList와 같이 List인터페이스를 구현한 컬렉션과 달리 HashSet은 저장순서를 유지하지 않으므로 저장 순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다.

중복을 제거하는 동시에 저장한 순서를 유지하고자 한다면 LinkedHashSet 사용

HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에 이 두 메소드를 목적에 맞게 오버라이딩을 해야 두 인스턴스를 같은 것으로 인식하게 할 수 있다.

TreeSet

이진탐색트리를 이용해 구현

TreeSet은 이진 탐색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스. 이진 탐색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조.

그리고 Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

이진 탐색트리는

• 모든 노드는 최대 두 개의 자식 노드를 가질 수 있다.

• 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽자식노드의 값은 부모노드의 값보다 커야 한다.

• 노드의 추가 삭제에 시간이 걸린다.

• 검색과 정렬에 유리하다.

• 중복된 값을 저장하지 못한다.