Java: 덱(Deque)의 개념과 사용

덱

 

Double-Ended Queue

큐의 양쪽에 데이터를 넣고 뺄 수 있는 자료구조

큐 또는 스택으로도 사용할 수 있다

 

덱의 분류

한 쪽으로만 입력이 가능한 덱 = Scroll

한쪽으로만 출력이 가능한 덱 = Shelf

 

덱은 인터페이스

Deque의 자료구조는 interface로 정의되어있다

그렇기에 이를 구현해주는 클래스를 같이 쓰는데

ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList

등이 있다

 

 

Java에서의 덱(Double-Ended Queue)

Deque는 입력 출력의 방향이 자유로운 만큼 많은 메소드가 존재한다

클래스 연결

큐와 마찬가지로 2개를 import 해주어야 한다

import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
	
    Deque<Integer> dq = new ArrayDeque<>();
    
}}

이렇게 연결하면 ArrayDeque 클래스 내부의 메소드를 사용할 수 있다

큐에서의 add와 offer / remove와 poll 형식을 그대로 사용할 수 있다

방향을 기억한다: First = 왼쪽, Last = 오른쪽

개념	큐(Queue)	덱(Deque)
push	.offer( 값 ); / .add( 값 );	.offerFirst( 값 );
		.offerLast( 값 );
pop	.poll(); / .remove();	.pollFirst( 값 );
		.pollLast( 값 );
top	.peek();	.peekFirst();
		.peekLast();
size	.size();	.size();
empty	.isEmpty();	.isEmpty();
검색 후 삭제 First = 왼쪽에서 탐색 Last = 오른쪽에서 탐색		.removeFirstOccurrence( 제거할 값 );
		.removeLastOccurrence( 제거할 값 );
		.remove( 제거할 값 ); //First와 동일
값이 있는지 확인		.contain( Object o );
순회 (Iterator)		.iterator(); //iterator로 변환한다
		.descendingIterator(); //역순 변환

 

덱의 순회

※ 덱에서 클래스 내부에 iterator() 메소드로 iterator 형식의 변환을 할 수 있다

//iterator 연결
	Iterator<Integer> it = dq.iterator();
		while(it.hasNext()) {
			int n = it.next();
			System.out.println(n);
		}
//역순으로 iterator 형식 저장 후 연결
	Iterator<Integer> dcit = dq.descendingIterator()();
		while(dcit.hasNext()) {
			int n = dcit.next();
			System.out.println(n);
		}
//for문을 통한 순회
	for(Integer e : dq) {
		System.out.println(e);
	}