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

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

from http://devyoseph.tistory.com/99 by ccl(A) rewrite - 2021-10-24 04:28:13