Queue 인터페이스

 

(Queue) : 데이터를 처리하기 전에 잠시 저장하고 있는 자료 구조이다.

 

- 전형적인 큐는 원소들을 FIFO(First-In-Fist-Out) 형식으로 저장하는 FIFO 큐인데, 후단(tail)에서 원소를 추가하고, 전단(head)에서 원소를 삭제한다새로운 원소들은 큐의 끝에 추가된다.


큐에서는 중간에 원소를 추가하는 것은 허용되지 않는다.

 

디큐는 자바 버전 1.6부터 Deque 인터페이스로 추가되었는데, 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있다.

 

- Deque 인터페이스는 ArrayDeque LinkedList 클래스들로 구현된다. 

 

- Queue 인터페이스는 기본적인 Collection의 연산 외에 다음과 같은 삽입삭제검색연산을 추가로 제공한다.

 

public interface Queue<E> extends Collection<E> {

E element(); //큐의 처음에 있는 원소를 삭제하지 않고 가져온다큐가 비어있으면 예외발생

E peak(); //큐의 처음에 있는 원소를 삭제하지 않고 가져온다큐가 비어있으면 null을 반환


boolean offer(E e); //원소를 추가할 때 큐의 용량을 넘어서면 false를 반환한다.


E poll(); //큐의 처음에 있는 원소를 가져온다큐에 원소가 없으면 null을 반환한다.

E remove(); //큐의 처음에 있는 원소를 제거한다큐에 원소가 없으면 예외가 발생한다.

}



아래의 예제는 큐가 카운트 다운 타이머를 구현하는 예제이다.

import java.util.*;

public class QueueTest {
    public static void main(String[] args) throws InterruptedException {
        int time = 10;

        // LinkedList 안에 Queue 인터페이스가 구현되어 있다.
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = time; i > 0; i--) {
            queue.add(i);
        }

        System.out.println("start time : " + System.currentTimeMillis() / 1000);
        while(!queue.isEmpty()) {
            System.out.println(queue.remove()+ " ");
            Thread.sleep(1000); //현재의 스레드를 1초간 재운다.
        }
        System.out.println("end time : " + System.currentTimeMillis() / 1000);
    }
}

[출력 결과]

start time - end time = 10



- FIFO 큐가 전형적이지만 예외적인 큐도 존재한다. 원소들을 우선순위에 따라 저장하고 기본적인 우선순위는 원소들의 값으로 결정되는 우선순위 큐(Priority Queues)가 있다.




▶ 우선순위 큐(Priority Queue)


원소들이 무작위로 삽입되었더라도 정렬된 상태로 원소들을 추출한다.


- remove()를 호출할 때마다 가장 작은 원소가 추출된다.


- 우선순위 큐는 히프(heap)라고 하는 자료 구조를 내부적으로 사용하여 큐를 정렬한다.

  • 히프는 이진 트리의 일종으로서 add() remove()를 호출하면 가장 작은 원소가 효율적으로 트리의 루트로 이동하게 된다.

  • 오름차순으로 트리가 설정된다.


- 우선순위 큐의 가장 대표적인 예는 작업 스케쥴링(job scheduling)이다각 작업은 우선순위를 가지고 있고 가장 높은 우선순위의 작업이 큐에서 먼저 추출되어 시작된다.


- 아래는 우선순위 큐에 대한 예제이다.

import java.util.*;
 
public class PriorityQueueTest {
	public static void main(String[] args) {
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		 
		pq.add(30);
		pq.add(80);
		pq.add(20);
		 
		for(Integer o : pq) {
			System.out.println(o); // 20, 80, 30 순으로 출력됨
		}

		System.out.println("원소를 삭제합니다.");
		
		while(!pq.isEmpty()) {
			System.out.println(pq.remove()); //20, 30 80 순으로 정렬된 상태로 출력됨.
		}
	}
}

[출력 결과]








 Set 인터페이스

 

- 순서에 상관없이 원소만 저장하고 싶은 경우 집합(Set)을 사용한다.

 

동일한 원소를 가질 수 없다.

 

해쉬 테이블(Hash Table)

  • 집합을 구현하는 가장 잘 알려진 방법이다.

  • 각각의 원소에 대해 해쉬 코드란 정수를 계산하며해쉬 코드는 대개 객체의 인스턴스 필드로부터 계산된다.

  • 각 클래스마다 해쉬 코드를 계산하는 hashCode()를 가지고 있다.

  • 해쉬 테이블은 연결 리스트의 배열로 구현되며각 리스트는 버킷(bucket)이라고 불린다.

  • 순서는 임의적이지만 검색 속도가 빠르다.

  • 테이블에서 원하는 객체를 찾기 위해 먼저 객체의 해쉬 코드를 계산하고 테이블의 크기에 맞추어 나머지 연산을 수행한 후에 결과로 나오는 숫자를 테이블의 인덱스로 사용하면 된다.

  • 쉽게 말해원하는 객체의 해쉬 코드를 테이블의 크기로 나누어서 나온 나머지가 버킷을 대표하는 번호가 된다이 때 각 리스트들은 순서가 임의적이다.


- Set 인터페이스를 구현하는 클래스는 HashSet, TreeSet, LinkedHashSet 등이 있다. 주로 사용되는 3가지에 대해 알아보자.





 HashSet


- HashSet 해쉬 테이블에 원소를 저장하기 때문에 성능면에서 가장 우수하다원소들의 순서가 일정하지 않다.

 

HashSet<String> hashSet = new HashSet<String>();

 

hashSet.add(“Milk”);

hashSet.add(“Bread”);

hashSet.add(“Butter”);

hashSet.add(“Cheese”);

hashSet.add(“Ham”);

hashSet.add(“Ham”);

 

System.out.println(hashSet);

 

출력 결과 : [Bread, Milk, Butter, Ham, Cheese] -> 순서가 임의적이다.





 TreeSet


- TreeSet 레드-블랙 트리(red-black tree)에 원소를 저장하므로 값에 따라서 순서가 결정되며 속도가 HashSet보다 느리다.

 

TreeSet<String> treeSet = new TreeSet<String>();

 

treeSet.add(“Milk”);

treeSet.add(“Bread”);

treeSet.add(“Butter”);

treeSet.add(“Cheese”);

treeSet.add(“Ham”);

treeSet.add(“Ham”);

 

System.out.println(treeSet);

 

출력 결과 : [Bread, Butter, Cheese, Ham, Milk] -> 알파벳 순으로 정렬됨

 




 LinkedHashSet


- LinkedHashSet 해쉬 테이블과 연결 리스트의 결합된 형태로 원소들의 순서는 삽입되었던 순서와 같다야간의 비용을 들여서 HashSet의 문제점인 순서의 불명확성을 제거한 방법이다.

 

LinkedHashSet<String> linked = new LinkedHashSet<String>();


linked.add(“Milk”);

linked.add(“Bread”);

linked.add(“Butter”);

linked.add(“Cheese”);

linked.add(“Ham”);

linked.add(“Ham”);

 

System.out.println(linked);

 

출력 결과 : [Milk, Bread, Butter, Cheese, Ham] -> 입력된 순서대로 출력됨.



대량 연산 메소드

 set1.containsAll(set2)

 만약 set2 set1의 부분집합이면 true를 반환한다.

 set1.addAll(set2)

 set1 set1 set2의 합집합으로 만든다.

 set1.retainAll(set2)

 set1 set1 set2의 교집합으로 만든다.

 set1.removeAll(set2) 

 set1 set1 set2의 차집합으로 만든다. (set1  set2)



집합 연산 시 주의할 점은 원집합이 파괴되면 안되므로 항상 연산 수행 전에 복사본을 만들어야 한다.

 

Set<String> union = new HashSet<String>(set1); //합집합을 위해 set1의 복사본을 union에 저장한다.

union.addAll(set2);





 

 

▶ List 인터페이스

 

리스트(List)는 순서를 가지는 원소들의 모임으로 중복된 원소를 가질 수 있다.

 

위치(index)를 사용하여 원소에 접근한다는 점이 배열과 동일하다.

 

리스트에 들어 있는 원소들의 인덱스는 0부터 시작한다.

 

리스트 인터페이스는 ArrayList, LinkedList, Vector 등의 클래스에 의하여 구현된다Vector 클래스는 이전 버전에서도 있었던 것으로 멀티 스레드 환경에서도 사용할 수 있도록 동기화되어 있다.





▶ ArrayList


- 저장되는 데이터의 개수에 따라 자동적으로 크기가 변경된다.

- 가변 크기의 배열(Dynamic Array)이라고도 불린다.

- 원소가 삭제되면 그만큼 크기를 줄이게 된다.

- 타입 매개변수를 가지는 제네릭 클래스로 제공된다.


ArrayList<String> arrList = new ArrayList<String>(); //타입 매개변수 지정

 

[기본 연산]

  • 데이터 저장 시 Collection 인터페이스의 add() 메소드를 사용한다.

arrList .add(“Hello”); // index0 : Hello

arrList .add(“World”); // index1 : World

arrList .add(“Good!”); // index2 : Good!


  • 기존의 데이터가 들어 있는 위치를 지정하여 add()를 호출하면그 위치에 삽입된다.

arrList .add(1, “Yeah~”); // index0 : Hello, index1 : Yeah~, index2 : World, index 3: Good!

 

  • 특정한 위치에 있는 원소를 바꾸려면 set() 메소드를 사용

arrList .set(2, “Nice”); // index0 : Hello, index1 : Yeah~, index2 : Nice, index 3: Good!

 

  • 데이터를 삭제하려면 remove() 메소드 사용

arrList .remove(3); // index0 : Hello, index1 : Yeah~, index2 : Nice

 

  • 저장된 객체 가져오려면 get() 메소드 사용

String s = arrList .get(1); // “Yeah~” 반환

 

  • 현재 저장된 원소의 개수를 얻으려면 size() 메소드 사용 (범위를 벗어나는 인덱스를 사용하면 예외가 발생한다.)

 System.out.println("총 원소 개수 : " + arrList.size()); // 출력 결과 → 총 원소 개수 : 3



[추가 연산]

  • 특정 데이터의 위치를 알려면 indexOf() 메소드 사용

int index = arrList.indexOf(“Yeah~”); // 1이 반환된다.


 단중복된 데이터는 맨 처음에 있는 데이터의 위치가 반환된다.


ArrayList<String> arrList2 = new ArrayList<>();

arrList2 .add(“Hello”); // index0 : Hello

arrList2 .add(“Hello”); // index1 : Hello

arrList2 .add(“Good!”); // index2 : Good!


System.out.println(arrList2.indexOf("Hello"); // 0이 반환된다.

  • 탐색을 반대방향으로 하려면 lastIndexOf() 메소드를 사용 (끝에서부터 탐색한다.)

ArrayList<String> arrList2 = new ArrayList<>();

arrList2 .add(“Hello”); // index0 : Hello

arrList2 .add(“Hello”); // index1 : Hello

arrList2 .add(“Good!”); // index2 : Good!


System.out.println(arrList2.lastIndexOf("Hello"); // 1이 반환된다.


- 참고 배열, ArrayList, 문자열 객체의 크기를 알아내는 방법은 서로 다르다.

  • 배열 : array.length

  • ArrayList : arrayList.size()

  • 문자열 : string.length()

- ArrayList에 있는 원소에 접근하는 또 다른 방법은 반복자(iterator)를 사용하는 것이다반복자는 특별한 타입의 객체로 컬렉션의 원소들을 접근하는 것이 목적이다또한 모든 컬렉션에서 반복자를 적용할 수 있다반복자는 java.util 패키지에 정의되어 있는 Iterator 인터페이스를 구현하는 객체이다아래는 Iterator 인터페이스에서 제공하는 메소드이다원래 3개의 메소드만 제공한다.


메소드 

 설명

 hasNext()

 아직 방문하지 않은 원소가 있으면 true를 반환

 next()

 다음 원소를 반환

 remove()

 최근에 반환된 원소를 삭제한다.


- 반복자를 사용하려면 아래와 같이 iterator() 메소드를 호출하여 반복자 객체를 얻어야한다.

 

Iterator iterator = arrList.iterator(); //반복자 객체 얻기

...

while(iterator.hasNext()) {

s = (String) s.next(); //반복자는 Object 타입을 반환하므로 캐스팅해야 한다.

System.out.println(s);

}

 

출력 결과 :

Hello

Yeah~

Nice


- 반복자 사용을 보다 간편하게 한 것은 자바 버전 1.5부터 도입된 for-each 루프이다.





 LinkedList


연결 리스트(LinkedList)는 각 원소를 링크로 연결한다. 따라서 각 원소들은 이전 원소를 가리키는 링크와 다음 원소를 가리키는 링크를 저장한다. 이처럼 자바에서는 모든 연결 리스트가 이중 연결 리스트로 구현되어 있다.


- 중간에 빈번하게 원소(데이터)의 삽입과 삭제가 이루어지는 경우 연결 리스트는 링크만 수정하면 되기 때문에 ArrayList보다 더 효율적이다LinkedList는 위와 같은 연산에서는 일정한 시간이 걸리나 ArrayList에서는 원소의 개수에 비례하는 시간이 소요된다.


- 단, 위치(index)를 가지고 원소를 접근하는 연산은 ArrayList보다 시간이 더 많이 걸린다위치(인덱스) 기반의 접근이 많다면 ArrayList가 더 낫다사용 방법은 ArrayList와 유사하다.


- LinkedList 예제

import java.util.*;
 
public class LinkedListTest {
	public static void main(String[] args) {
		LinkedList<String> linkedList = new LinkedList<String>();
		 
		linkedList.add(“Hello”);
		linkedList.add(“Nice”);
		linkedList.add(“Yeah!!”);
		linkedList.add(“Cheer”);
		linkedList.add(“Up!!”);
		 
		for(int i = 0; i <linkedList.size(); i++) {
			System.out.println(linkedList.get(i));
		}
	}
}


- 연결 리스트도 반복자를 지원한다. 연결 리스트도 리스트이기 때문에 리스트에서 사용하기 편리한 반복자가 제공되는데바로 ListIterator이다.

 

interface ListIterator<E> extends Iterator<E> { 

...

//두 개의 메소드가 제공되며리스트를 역순으로 방문하는 경우에 사용된다.

E previous();

boolean hasPrevious();

...

}


 

배열을 리스트로 변경하는 방법은 Arrays.asList() 메소드를 사용하는 것이다.

  • 이 메소드는 배열을 받아서 리스트 형태로 반환한다.

  • 리스트를 변경하면 배열도 변경되며 그 역도 성립한다.

  • 리스트의 크기는 배열과 같고 변경이 불가능하다.

  • 배열을 컬렉션이나 리스트를 받는 메소드에 매개변수로 넘기는 것을 허용한다.

  • 고정된 크기의 리스트를 원하는 경우에 어떤 일반적인 리스트 구현보다 효율적이다.

List<String> list = Arrays.asList(new String[100]);

 




▶ Vector 클래스

 

Vector 클래스는 java.util 패키지에 있는 컬렉션의 일종으로 가변 크기의 배열(dynamic array)”을 구현하고 있다.

 

배열의 원소 개수가 늘어나면 자동으로 배열의 크기가 늘어난다.

 

- 어떤 타입의 객체라도 저장할 수 있다기초 자료형 역시 오토박싱 기능을 이용하여 객체로 변환되어 저장된다.

 

제네릭도 지원하므로 생성 시 new String<T>의 형태로 선언하면 타입의 객체만을 저장하는 Vector를 생성할 수 있다.

 

자주 사용되는 메소드

 boolean add()

 Vector 객체에 요소를 추가한다.

 boolean add(int index, Object object)

 정해진 위치에 요소를 추가한다.

 Object get(int index)

 해당 위치의 요소를 추출한다추출 시 캐스팅해야 한다.

 int size()

 현재 요소들의 개수를 반환한다.




 

 

 

- Vector 예제

import java.util.Vector;

public class VectorTest {
    public static void main(String[] args) {
        Vector v = new Vector();
        v.add("안녕하세요");
        v.add(new Integer(20));
        v.add(400);

        System.out.println("vector size : " + v.size());

        for (int i = 0; i < v.size(); i++) {
            System.out.println("vector element " + i + " : " + v.get(i));
        }

        String s = (String) v.get(0); //추출 시 형변환 필수 !

    }
}

[출력 결과]

 




 

컬렉션

 

- 컬렉션(Collection) : 자바에서 자료 구조를 구현한 클래스들을 칭하는 용어이다.

 

자료 구조(Data Structure) : 자료를 저장하기 위한 구조이다.

 

대부분의 프로그램은 자료를 저장하여야 하고 따라서 어떤 자료 구조를 사용할 것인지 결정하여야 한다.


많이 사용되는 자료 구조로는 리스트(list), 스택(stack), (queue), 집합(set), 해쉬 테이블(hash table) 등이 있다.

 

 



컬렉션의 종류

 

자바는 컬렉션 인터페이스 컬렉션 클래스로 나누어서 제공한다.

 

컬렉션 인터페이스를 구현한 클래스도 함께 제공하므로 간단히 사용하거나 각각 필요에 맞추어 인터페이스를 자신의 클래스로 구현할 수도 있다.

 

컬렉션 인터페이스와 컬렉션 클래스는 모두 java.util 패키지에 포함되어 있다.

 

컬렉션 라이브러리들은 모두 제네릭 기능을 지원한다.

 

아래는 컬렉션 인터페이스를 간단히 설명한 것이다.


 인터페이스

 설명

 Collection 

 모든 자료 구조의 부모 인터페이스로서 객체의 모임을 나타낸다.

 Set 

 집합을 나타내는 자료 구조로중복된 원소를 가지지 않는다.

 List 

 순서가 있는 자료 구조로중복된 원소를 가질 수 있다.

 Map 

 키와 값들이 연관되어 있는 사전과 같은 자료 구조이다.

 Queue 

 FIFO(First-In-First-Out) 식으로 들어온 순서대로 내보내는 자료 구조이다.

 

자바 버전 1.2이전에는 Vector, Stack, HashTable, Bitset, Enumberation 클래스만 제공하였다.

 

자바 버전 1.2이후에는 위의 기재한 클래스 외에 다양한 클래스를 제공되며, 인터페이스와 구현을 분리하였다.

 

 



▶ Collection 인터페이스


[인터페이스의 계층 구조]


모든 컬렉션 인터페이스의 부모 인터페이스에 해당된다.

 

모든 컬렉션 클래스들이 Collection 인터페이스를 구현하고 있으므로 Collection에 들어 있는 메소드들은 거의 대부분 컬렉션 클래스에서 사용할 수 있다.


- Collection 인터페이스가 제공하는 메소드


기본연산

 int size()

 원소의 개수 반환

 boolean isEmpty()

 비어있으면 true를 반환

 boolean contains(Object obj) 

 해당 객체를 포함하고 있으면 true를 반환

 boolean add(E element)

 원소 추가

 boolean remove(Object obj)

 원소(객체삭제

 Iterator<E> iterator() 

 원소를 순서대로 방문한다.

 벌크연산

 boolean addAll(Collection<? extends E> c)

 c에 있는 모든 원소 추가

 boolean containsAll(Collection<?> c)

 c에 있는 모든 원소가 포함되어 있으면 true

 boolean removeAll(Collection<?> c)

 c에 있는 모든 원소 삭제

 void clear() 모든 원소 삭제

 배열연산

 Object[] toArray()

 컬렉션을 Object 타입의 배열로 변환

 <T> T[] toArray(T[] a) 컬렉션을 해당 입의 배열로 변환




+ Recent posts