[출처] [자바][기본] Deque 데크, 디큐, 덱 ( double ended queue )|작성자 카루
큐 + 스택 의 기능을 가진 Deque에 대해 알아보자.
Deque는 인터페이스므로 구현된 다른 클래스를 사용해야 한다.
여러가지가 있지만 본 예제에서는 LinkedBlockingDeque 를 사용한다.
큐+스택 인 만큼 넣는 방법도 다양하고.
꺼내는 방법도 다양하다.
그러나 큐는 먼저 넣은게 먼저나온다.
스택은 먼저 넣은게 나중에 나온다.
그 두개가 혼합되어 사용될경우
즉 큐로서 넣은 값이
스택방식으로 꺼내질경우
어떻게 될지에 대해 상상이 가는가.
큐로 넣은값이 앞으로 가는가 뒤로 가는가.
스택으로 꺼내는값은 뒤에서 꺼내는것인가 앞에서 꺼내는 것인가.
이번 실험으로 애매함을 해결해보자.
물론 이 실험으로도 어디가 앞인지 뒤인지 알수 없다.
다만 방향을 제시할수 있다. 즉 어떤 방법은 A로 가고 어떤방법은 B에서 꺼내고 라는등...
결국 이것을 앞 뒤라고 이해하면 편할 것이다.
일단 꺼내는 함수들에 대해 알아보자.
값을 제거하지 않는 것들
peek() : 앞
peekLast() : 뒤
peekFirst() : 앞
getFirst() : 앞
getLast() : 뒤
값을 제거하는 것들
poll() : 앞
pollFirst() : 앞
pollLast() : 뒤
pop() : 앞
입력하는 함수들에 대해 알아보자.
offerFirst : 앞
offerLast : 뒤
offer : 뒤
addFirst : 앞
addLast : 뒤
add : 뒤
putFirst : 앞
putLast : 뒤
put : 뒤
push : 앞
정리하자면
출력은 Last가 붙지 않은건 전부 앞에서 꺼낸다.
입력이 엄청나게 괴랄 하다.
First, Last가 붙은것들은 해당 위치로 다 들어간다.
offer, add, put은 뒤에 넣는다.
push는 앞으로 넣는다.
참고로 앞으로 넣는다는 얘기는 먼저넣은게 점점 뒤로 밀려나간다는 얘기이며
뒤로 넣는다는 얘기는 뒤에 먼저 들어간 순서대로 서있는다는 이야기이다.
테스트 소스를 첨부함니다.
잘못된 부분이 있으면 댓글로 부탁드려요.
[펌] : http://cafe.naver.com/mymejong/378
DEQUES
Deque는 double-ended queues의 줄임말이다(디큐가 아니라 데크로 발음함). 큐는 한쪽 엔드에서 추가하고 다른 쪽 엔드에서 제거할 수 있는 반면, 양쪽 엔드에서 추가와 제거가 가능한 double-ended queues는 스택과 큐가 결합된 것처럼 작동한다. Deque 인터페이스는 J2SE 5.0에 도입된 Queue 인터페이스에서 확장되는데, 이 기능은 최근에 Java SE 6의 Java Collections Framework에 추가되었다(이 기능이 최종적으로 포함되려면 JCP의 승인을 받아야 함). 인터페이스 구현에는 LinkedList, ArrayDeque와 이에 수반되는 LinkedBlockingDeque가 포함된다.
LinkedList는 아마도 deque의 가장 전형적인 용례일 것이다. LinkedList는 제한 없이 확장이 가능하고 양쪽 엔드에서 신속하게 추가 및 제거 작업이 가능하다. ArrayDeque는 용량 제한이 없는 또 하나의 전형적인 구현으로, 성능을 최상으로 유지하기 위한 wraparound index 구현을 제공한다. 모든 베이스 컬렉션 구현이 그렇듯이, 어느 쪽도 threadsafe하지 않다. (Vector나 Hashtable 같은 역사적인 컬렉션은 threadsafe하지만 고도의 동시발생적인 액세스를 위해 설계되지는 않았다.) 쓰레드 안전이 필요한 경우에는 LinkedBlockingDeque를 이용하면 되는데, LinkedBlockingDeque 클래스는 Deque에서 확장되는 새로운 BlockingDeque 인터페이스를 구현한다. 이 클래스는 사이즈가 제한되거나 제한되지 않을 수도 있다. 용량이 지정되지 않은 경우, 사이즈 제한은 Integer.MAX_VALUE이다.
다음 메소드 중 하나로 deque에 엘리먼트를 추가할 수 있다.
void addFirst(E e)
void addLast(E e)
boolean add(E e)
add() 메소드는 addLast()와 동등하다고 볼 수 있다. deque의 용량이 부족하면 IllegalStateException이 throw된다. 또한 다음 메소드 중 하나를 통해 추가될 엘리먼트를 제공할 수도 있다.
boolean offer(E e)
boolean offerFirst(E e),
boolean offerLast(E e)
addXXX() 메소드로 엘리먼트를 추가하는 경우와 달리, offerXXX() 메소드가 제공되었을 때 항목을 추가할 수 없으면 메소드는 false를 반환한다.
이 외에도 엘리먼트 제거를 위한 한 쌍의 메소드 세트가 있다.
remove(), removeFirst(), and removeLast()
poll(), pollFirst(), and pollLast()
deque가 비어있을 경우 removeXXX() 메소드는 NoSuchElementException를 throw하고, pollXXX() 메소드는 null을 반환한다. 또한, 아래의 메소드 중 한 가지를 사용하여 특정 개체를 제거할 수 있다(deque가 엔드에서의 추가/제거의 용도로만 의도된 경우라도).
boolean remove(Object o)
boolean removeFirstOccurrence(Object o)
boolean removeLastOccurrence(Object o),
Deque는 엘리먼트를 검사하기 위한 6개의 메소드를 가진다.
element()
getFirst()
getLast()
peek()
peekFirst()
peekLast()
element()는 오래된 Queue 인터페이스로부터 상속한 인터페이스 메소드이기 때문에 get() 메소드가 없다. get 메소드는 removeXXX()와 유사하며 deque가 비어있는 경우 NoSuchElementException을 throw하는데, 이와 대조적으로 peek 메소드는 비어있는 경우 null을 반환한다. 이는 물론 Deque가 null 값의 추가를 허용할 경우 deque의 엔드에 있는 null 항목과 ‘nobody on deck’ 간의 차이를 알 수 없다는 것을 의미한다. 그러나 이 경우에는 size() 메소드를 활용할 수 있다.
Deque는 개념상 이중으로 링크되므로, 어떤 순서로도 엘리먼트들을 traverse할 수 있다. 앞에서 뒤로 traverse하려면 iterator()를 이용하고 역순, 즉 뒤에서 앞으로 traverse하려면 descendingIterator()를 이용한다. 하지만 위치별로 엘리먼트에 액세스할 수는 없다?적어도 Deque 인터페이스로는 불가능하다. LinkedList는 Deque의 구현이지만 함께 구현되는 List 인터페이스를 통해 색인 액세스(indexed access)를 지원한다. 랜덤 액세스 요건이 없다면 Deque 구현이 더 효과적으로 이루어질 수 있다.
왜 deque를 사용하는 것일까? deque는 maze 또는 parsing 소스를 통한 검색과 같은 반복적인 문제에 특히 유용한 데이터 구조로서, path를 따라 이동하면서(path가 양호하다고 판단되는 한) "good" spot을 저장하고 계속해서 데이터를 추가할 수 있다. path가 bad를 반환할 경우에는 bad 비트를 pop off하여 마지막 good spot으로 복귀한다. 이 경우 스택과 같은 동일한 엔드에서 추가와 제거를 수행하게 된다. 일단 길을 찾으면 처음부터 다시 시작하여 반대쪽 엔드에 해당하는 솔루션을 밝혀낸다. 또 다른 전형적인 예로, 운영체제 스케줄러, 그리고 사람들을 속이기를 좋아하는 악질 카드 딜러 등을 들 수 있을 것이다.
다음 프로그램 Blocked는 Deque의 용례, 보다 구체적으로는 용량 제한이 있는 LinkedBlockingDeque를 보여주고 있다. 이는 물론 최상의 deque 용례는 아니지만 API와 용량 제한에 도달했을 때의 상황을 예시해준다. 프로그램은 23개의 달 이름(짧은 이름과 긴 이름 모두)을 취하여 이를 6-엘리먼트 블로킹 deque의 헤드에 한번에 하나씩 추가한다. 또 다른 스레드에서는, 현재 컬렉션 내에 있는 엘리먼트의 수를 토대로 엘리먼트를 deque의 헤드와 테일에서 제거한다.
import java.io.*;
import java.util.*;
import java.util.concurrent.*;
public class Blocked {
public static void main(String args[]) {
Calendar now = Calendar.getInstance();
Locale locale = Locale.getDefault();
final Console console = System.console();
final Map<String, Integer> names = now.getDisplayNames(
Calendar.MONTH, Calendar.ALL_STYLES, locale);
console.printf("Starting names: %s%n", names);
final Deque<String> deque =
new LinkedBlockingDeque<String>(6);
// Add one at time to beginning of deque
new Thread() {
public void run() {
Set<String> keys = names.keySet();
Iterator<String> itor = keys.iterator();
String element = null;
while (itor.hasNext() || element != null) {
if (element == null) {
element = itor.next();
console.printf("MapGot: %s%n", element);
}
console.printf("Offering: %s%n", element);
if (deque.offerFirst(element)) {
console.printf("MapRemoving: %s%n", element);
itor.remove();
element = null;
} else {
try {
Thread.sleep(250);
} catch (InterruptedException ignored) {
}
}
}
// Done. Give time to process rest.
try {
Thread.sleep(3500);
} catch (InterruptedException ignored) {
}
System.exit(0);
}
}.start();
while (true) {
if ((deque.size() % 2 == 1)) {
// remove head
console.printf(
"Remove head: %s%n", deque.pollFirst());
} else {
// remove tail
console.printf(
"Remove tail: %s%n", deque.pollLast());
}
// Sleep between loops
try {
Thread.sleep(500);
} catch (InterruptedException ignored) {
}
}
}
}
아래에서 보듯이, 프로그램 실행 시 printf 선언문 때문에 많은 아웃풋이 생성된다. 엘리먼트를 소스 맵에서 가져오거나, 소스 맵에서 제거하거나, deque에 제공하거나, deque에서 제거할 때마다 아웃풋 행이 생성된다. deque가 full 상태일 때 어떻게 제공(offering) 동작이 복수로 발생하는지 유의할 것.
>> java Blocked
Starting names: {Jun=5, March=2, December=11, April=3,
November=10, September=8, October=9, Sep=8, Aug=7, Apr=3,
May=4, June=5, Feb=1, Dec=11, Oct=9, Jan=0, Mar=2, Jul=6,
August=7, January=0, February=1, July=6, Nov=10}
Remove tail: null
MapGot: Jun
Offering: Jun
MapRemoving: Jun
MapGot: March
Offering: March
MapRemoving: March
...
Remove tail: Jul
Remove head: Nov
Remove tail: August
Remove head: July
Remove tail: January
Remove head: February
Remove tail: null
여기서 두 가지 사실에 주목할 필요가 있다. 첫째, 24개가 아닌 23개의 짧고 긴 달 이름이 있다(5월인 "May"의 경우에는 짧은 이름과 긴 이름 모두에 해당하기 때문에 23개가 된다). getDisplayNames() 메소드는 Map을 반환하므로 "May"는 짧은 이름과 긴 이름 등 2개 엔트리에 대한 key가 될 수 없다. 둘째는, 한쪽 엔드에서 추가하고 다른 쪽 엔드에서 제거하는 것이 작업의 전부라면 Deque 대신 컬렉션 프레임워크에서 Queue 구현을 이용하는 편이 더 나을 것이라는 점이다.
최소한, STL(Standard Template Library)에서의 유용한 deque/vector 비교 자료를 보려면 An In-Depth Study of the STLDeque Container를 참조할 것(여기서는 두 컨테이너 타입의 성능 차이에 대해 다루고 있음). 자바 플랫폼 상의 실제 수에는 차이가 있지만 전반적인 개념은 나름대로 정확하다고 볼 수 있다.
