[Java] #23-2. Collection(컬렉션) - Queue

* Queue는 왜 필요할까?

 

앞에서 LinkedList라는 클래스에 대해 다루어 봤다. LinkedList라는 것은 자료 구조에 대해 배울 때 중요한 항목 중 하나이기 때문에 꼭 기억하고 있어야 한다.

LinkedList에서는 바로 앞 뒤의 만 기억한다. 즉, A,B,C가 순차적으로 들어가 있을 때 A는 뒤에 있는 값이 B라는 것만 알 뿐, C의 존재는 모른다. C또한 앞에 B만 알 뿐 A는 모른다. 그렇다면 이렇게 복잡한 LinkedList를 왜 쓸까? 배열과 같이 데이터를 담아 순차적으로 뺄 경우엔 필요 없을지도 모른다. 그러나 배열의 중간에 있는 데이터가 지속적으로 삭제되고, 추가될 경우에는 LinkedList가 배열보다 메모리 공간 측면에서 훨씬 유리하다. 왜냐하면 배열과 같은 ArrayList와 Vector는 각 위치가 정해져 있고, 그 위치로 데이터를 찾는다. 그런데 맨 앞의 갚을 삭제하면 그 뒤에 있는 값들을 하나씩 앞으로 위치를 이동해야 제대로 된 위치의 값을 가지게 된다. 

 

반면 LinkedList는 중간에 있는 데이터를 삭제하면 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결할 때 위치를 맞추기 위해 값을 이동하는 단계를 거칠 필요가 없다. 또한 LinkedList는 List의 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. 즉, LinkedList 자체가 List이면서도 Queue, Deque도 된다.

 

큐는 왜 사용할까?

웹 서버에 100명의 사용자가 요청을 했다고 가정하자. 만약 LIFO(Last In First Out)로 처리해서 사용자에게 응답을 준다면 먼저 와서 대기 중인 사용자는 제일 마지막으로 서비스를 받게 된다. 이렇게, 사용자들의 요청을 들어온 순서대로 처리할 때 큐를 사용한다.

 

LinkedList 클래스가 구현한 인터페이스 중에 Java 6에 추가된 Deque라는 것이 있다. Deque는 "Double Ended Queue"의 약어로, Queue 인터페이스를 확장했기 때문에 Queue의 기능을 전부 포함한다. 대한 맨 앞에 값을 넣거나 빼는 작업, 맨 뒤에 값을 넣거나 빼는 작업을 수행하는 데 용이하도록 되어 있다.

 

 

* LinkedList에 대하여

 

LinkedList의 상속 관계를 알아보자.

 

java.lang.Object
  ㄴ java.util.AbstractCollection<E>
    ㄴ java.util.AbstractList<E>
      ㄴ java.util.AbstractSequentialList<E>
        ㄴ java.util.LinkedList<E>

 

ArrayList 클래스나 Vector 클래스와 상속관계는 비슷하지만, AbstractSequential이 부모인 것을 볼 수 있다. LinkedList 클래스가 구현한 인터페이스 목록을 보자.

 

인터페이스	용도
Serializable	원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정
Cloneable	Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 복제가 가능한 객체임
Iterable<E>	객체가 "foreach" 문장을 사용할 수 있음을 지정
Collection<E>	여러 개의 객체를 하나의 객체에 담에 처리할 때의 메소드 지정
Deque<E>	맨 앞과 맨 뒤의 값을 용이하게 처리하는 큐와 관련된 메소드 지정
List<E>	목록형 데이터를 처리하는 것과 관련된 메소드 지정
Queue<E>	큐를 처리하는 것과 관련된 메소드 지정

 

 

* LinkedList의 생성자와 주요 메소드

 

LinkedList는 일반적인 배열 타입의 클래스와 달리 생성자로 객체를 생성할 때 처음부터 크기를 지정하지 않는다. 각 데이터들이 앞 뒤로 연결되어 있어 미리 공간을 만들어 놓을 필요가 없기 때문이다. 그러므로 다음의 두 생성자만 필요하다.

 

생성자	설명
LinkedList()	비어 있는 LinkedList 객체를 생성한다.
LinkedList(Collection<? extends E> c)	매개 변수로 받은 컬렉션 객체의 데이터를 LinkedList에 담는다.

 

LinkedList 클래스는 구현한 인터페이스의 종류가 많기 때문에 메소드의 종류도 다양한다. 우선 객체에 데이터를 추가하는 메소드를 알아보자.

 

리턴 타입	메소드 이름 및 매개 변수	설명
void	addFirst(Object)	LinkedList 객체의 가장 앞에 데이터를 추가한다.
boolean	offerFirst(Object)
void	push(Object)
boolean	add(Object)	LinkedList 객체의 가장 뒤에 데이터를 추가한다.
void	addLast(Object)
boolean	offer(Object)
boolean	offerLast(Object)
void	add(int, Object)	LinkedList 객체의 특정 위치에 데이터를 추가한다.
Object	set(int, Object)	LinkedList 객체의 특정 위치에 있는 데이터를 수정한다. 그리고 기존에 있던 데이터를 리턴한다.
boolean	addAll(Collection)	매개 변수로 넘긴 컬렉션의 데이터를 추가한다.
boolean	addAll(int, Object)	매개 변수로 넘긴 컬렉션의 데이터를 지정된 위치에 추가한다.

 

각 메소드의 이름을 보면 매우 중복된 기능을 수행하는 메소드가 많을 것을 알 수 있다. LinkedList가 여러 종류의 인터페이스를 구현했기 때문이다. 예제를 통해 기능들을 알아보자. LinkedList에 객체를 넣고 빼는 메소드를 만들어보자.

 

import java.util.LinkedList;

public class QueueSample {
	
	public static void main(String[] args) {
		QueueSample sample = new QueueSample();
		sample.checkLinkedList1();
	}
	public void checkLinkedList1() {
		LinkedList<String> link = new LinkedList<String>();
		link.add("A");
		link.addFirst("B");
		System.out.println(link);
		link.offer("C");
		System.out.println(link);
		link.addLast("D");
		System.out.println(link);
		link.offer("E");
		System.out.println(link);
		link.offerLast("F");
		System.out.println(link);
		link.push("G");
		System.out.println(link);
		link.add(0, "H");
		System.out.println(link);
		System.out.println("EX=" + link.set(0, "I"));
		System.out.println(link);
	}
}

 

LinkedList 객체를 System.out.println()으로 출력하면 객체의 내용들이 순서대로 출력되며, 대괄호로 감싸진다.

 

결과부터 보자.

 

[B, A]
[B, A, C]
[B, A, C, D]
[B, A, C, D, E]
[B, A, C, D, E, F]
[G, B, A, C, D, E, F]
[H, G, B, A, C, D, E, F]
EX=H
[I, G, B, A, C, D, E, F]

 

이 중 어떤 메소드를 대표적으로 사용하는 것이 좋을까? 자바의 LinkedList 소스를 보면 맨 앞에 추가하는 메소드는 동일한 기능을 수행하는 어떤 메소드를 호출해도 addFirst() 메소드를 호출한다. 맨 뒤에 추가하는 메소드는 동일한 기능을 수행하는 offer() 관련 메소드를 호출하면 add()나 addLast() 메소드를 호출하도록 되어 있다. 이에, 여러 메소드를 혼용하여 사용하면 그 소스를 읽는 사람도 이해하기 힘들기 때문에 한가지만 선택하여 사용하는 것이 권장되며, add가 붙은 메소드를 사용하는 것이 모호성이 제일 적다.

 

LinkedList 클래스의 주요 메소드들을 살펴보자. LinkedList 클래스에서 특정 위치의 데이터를 꺼내는 메소드들이다.

 

리턴 타입	메소드 이름 및 매개 변수	설명
Object	getFirst()	LinkedList  객체의 맨 앞에 있는 데이터를 리턴한다.
Object	peekFirst()
Object	peek()
Object	element()
Object	getLast()	LinkedList 객체의 맨 뒤에 있는 데이터를 리턴한다.
Object	peekLast()
Object	get(int)	LinkedList 객체의 지정한 위치에 있는 데이터를 리턴한다.

 

Last가 붙지 않은 조회용 메소드는 모두 맨 앞의 데이터를 가져온다고 보면 된다. 그리고 맨 앞 데이터를 가져오는 메소드는 모두 내부적으로 getFirst() 메소드를 호출하므로, 이 메소드를 사용할 것을 권장한다.

 

LinkedList에 어떤 객체가 포함되어 있는지 확인하는 메소드는 다음과 같은 것이 있다.

 

리턴 타입	메소드 이름 및 매개 변수	설명
boolean	contains(Object)	매개 변수로 넘긴 데이터가 있을 경우 true를 리턴한다.
int	indexOf(Object)	매개 변수로 넘긴 데이터의 위치를 앞에서부터 검색하여 리턴한다 없을 경우 -1을 리턴한다.
int	LastIndexOf(Object)	매개 변수로 넘긴 데이터의 위치를 끝에서부터 검색하여 리턴한다. 없을 경우 -1을 리턴한다.

 

데이터의 값으로 위치를 찾거나, 존재하는지를 확인하려면 위의 메소드를 사용하면 된다.

 

데이터를 삭제하는 메소드의 목록을 아래와 같다. 여기 대부분의 삭제 관련 메소드들은 LinkedList 객체에서 삭제하고 데이터를 리턴해주기 때문에 앞에서 살펴본 조회용 메소드보단 이 메소드를 많이 사용한다.

 

리턴 타입	메소드 이름 및 매개 변수	설명
Object	remove()	LinkedList 객체의 가장 앞에 있는 데이터를 삭제하고 리턴한다.
Object	removeFirst()
Object	poll()
Object	pollFirst()
Object	pop()
Object	pollLast()	LinkedList 객체의 가장 끝에 있는 데이터를 삭제하고 리턴한다.
Object	removeLast()
Object	remove(int)	매개 변수에 지정된 위치에 있는 데이터를 삭제하고 리턴한다.
boolean	remove(Object)	매개 변수로 넘겨진 객체와 동일한 데이터 중 앞에서부터 가장 처음에 발견된 데이터를 삭제한다.
boolean	removeFirstOccurence(Object)
boolean	removeLastOccurence(Object)	매개 변수로 넘겨진 객체와 동일한 데이터 중 끝에서부터 가장 처음에 발견된 데이터를 삭제한다.

 

맨 앞에 있는 데이터를 삭제하는 많은 메소드들은 모두 removeFirst() 메소드를 내부적으로 호출한다. 반대로 맨 뒤에 있는 데이터를 삭제하는 메소드들을 모두 removeLast() 메소드를 내부적으로 호출한다. 따라서 혼동을 피하려면 remove가 붙은 메소드를 사용하는 것이 좋다.

 

지금까지 LinkedList의 주요 메소드를 살펴봤다. 그 외에도 크기를 확인하는 size()나 모든 데이터를 삭제하는 clear(), 데이터를 복제하는 clone() 배열로 만드는 toArray() 메소드를 앞에서 배열 다룰 때와 사용법이 같다.

 

마지막으로 LinkedList 객체를 하나씩 검색하기 위한 Iterator 객체에 대해 알아보자.

 

리턴 타입	메소드 이름 및 매개 변수	설명
ListIterator	ListIterator(int)	매개 변수에 지정된 위치부터의 데이터를 검색하기 위한 ListIterator 객체를 리턴한다.
Iterator	descendingIterator()	LinkedList의 데이터를 끝에서부터 검색하기 위한 Iterator 객체를 리턴한다.

 

ListIterator는 Iterator 인터페이스가 다음 데이터만을 검색할 수 있다는 단점을 보완하여, 이전 데이터도 검생할 수 있는 이터레이터이다. 따라서 next() 외에도 previous() 메소드를 사용하면 이전 데이터를 확인할 수 있다. 

 

 

* 정리

 

1. 순서와 상관 없는 여러 데이터를 하나의 객체에 저장할 때 사용하는 Collection의 하위 인터페이스는 무엇인가요?
-Set 인터페이스는 데이터의 순서와 상관없이 데이터를 담을 때 사용한다.

2. HashSet 클래스는 생성자를 통하여 저장 가능한 데이터의 초기 크기를 지정할 수 있나요?
-HashSet도 ArrayList처럼 int를 매개변수로 갖는 생성자를 통하여 데이터 저장 공간을 명시적으로 지정할 수 있다.

3. HashSet 클래스의 객체에 데이터를 추가하는 메소드는 무엇인가요?
-HashSet에 데이터를 담는 메소드는 add()이다.

4. HashSet 클래스의 객체에 어떤 데이터가 존재하는지 확인하는 메소드는 무엇인가요?
-HashSet의 contains() 메소드를 사용하면 매개변수로 넘긴 값이 존재하는지 확인할 수 있다.

5. HashSet 클래스의 객체에 어떤 데이터를 삭제하는 메소드는 무엇인가요?
-HashSet의 데이터를 지우는 메소드는 remove()이다.

6. Queue는 FIFO를 처리하기 위한 클래스들의 인터페이스 입니다. FIFO는 무슨 단어의 약어인가요?
-FIFO는 First In First Out의 약자로 처음 들어온 값이 먼저 나간다는 것을 의미한다.

7. Deque는 무슨 단어의 약어이며, 용도는 무엇인가요?
-Deque는 Double Eneded Queue의 약자이다.

8. LinkedList 클래스의 특징을 이야기해 봅시다.
-LinkedList는 List 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. 즉, 목록형 클래스이기도 하면서 큐의 역할도 수행할 수 있다.

 

 

그럼 이만.