[210127] java Deque

java

[210127] java Deque

hjk927 2021. 1. 27. 15:43

java.util.Deque

queue interface를 상속하고 있으며 스택이나 큐와는 달리 head와 tail 양 끝에서 요소를 수정하는 게 가능하다. 스택이나 큐 중 하나의 용도로 사용된다.

양 끝에 있는 요소 각각에 대한 삽입, 수정, 검증을 할 수 있는 메소드가 있다. 메소드는 두 종류로 나뉘는데, 하나는 연산에 실패했을 때 예외를 일으키는 메소드이며, 다른 하나는 연산에 실패했을 때 특정 값(null이나 false 등)을 반환하는 메소드이다. 여기서, 삽입 작업 제한에 대한 후자의 경우에는 용량이 한정적인 deque에 대해서 사용하도록 구현되어 있다.

	Head		Tail
	예외 발생 (Throws Exception)	특정 값 반환 (Special Value)	예외 발생 (Throws Exception)	특정 값 반환 (Special Value)
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

이 인터페이스는 Queue 인터페이스를 상속한다. queue에 있는 메소드와 같은 기능을 하는 Deque 메소드가 아래 표와 같이 존재한다. 또한, queue에서 사용했던 메소드를 그대로 사용할 수도 있다.

Queue Method	Equivalent Deque Method
add(e)	addLast(e)	queue의 tail에 요소 삽입
offer(e)	offerLast(e)	용량 제한이 있는 queue에 요소 삽입
remove()	removeFirst()	queue의 head에 있는 요소 제거 실패할 경우 예외 던짐
poll()	pollFirst()	queue의 head에 있는 요소 제거 성공할 경우 queue의 head, 실패할 경우 null 반환
element()	getFirst()	head에 있는 값을 확인한다. 제거하지는 않는다. queue가 비어있을 경우 예외 던짐
peek()	peekFirst()	head에 있는 값을 확인한다. 제거하지는 않는다. queue가 비어있을 경우 null 반환

Deque는 Stack의 기능도 지원한다. stack 역시, 아래 표의 1열이나 2열에 있는 메소드를 사용할 수 있다.

Stack Method	Equivalent Deque Method
push(e)	addFirst(e)	queue의 head에 요소 삽입
pop()	removeFirst()	queue의 head에 요소 제거
peek()	peekFirst()	queue의 head에 있는 값을 확인하나 제거하지는 않는다.

PriorityQueue : 우선순위가 있는 큐

ArrayDeque : 일반적인 deque 기능 지원. 자동으로 deque의 크기를 조정해준다.

LinkedList : 연결 리스트의 기능

java.util.ArrayDeque<E>

ArrayDeque의 주요 특징은 아래와 같다.

Queue와 달리, 양 쪽에서 요소를 삽입하고 삭제할 수 있다.
Null 값을 저장할 수 없다.
멀티 스레드 환경에 적합하지 않다.
최대 용량에 제한이 없다.
LinkedList, Stack보다 빠르다.

- 실행 예제

전체 코드는 아래와 같다.

public static void main(String[] args) {
        // 0. deque 생성
        Deque<Integer> deque = new ArrayDeque<>();

        // 1. insert 예제
        deque.offerFirst(3);
        deque.addFirst(2);
        deque.addFirst(1);
        deque.addLast(4);
        deque.add(5);
        deque.addLast(6);

        System.out.println("add all element");
        deque.stream().forEach(i->System.out.println(i));

        // 2. remove 예제
        deque.removeFirst();

        System.out.println("removeFirst()");
        deque.stream().forEach(i->System.out.println(i));

        deque.remove();

        System.out.println("remove()");
        deque.stream().forEach(i->System.out.println(i));

        deque.pollLast();

        System.out.println("pollLast()");
        deque.stream().forEach(i->System.out.println(i));

        deque.pollFirst();

        System.out.println("pollFirst()");
        deque.stream().forEach(i->System.out.println(i));

        // 3. examine 예제
        int first = deque.getFirst();
        int last = deque.getLast();
        int peek = deque.peek();
        int peekLast = deque.peekLast();

        System.out.println("first = " + first);
        System.out.println("last = " + last);
        System.out.println("peek = " + peek);
        System.out.println("peekLast = " + peekLast);
    }

1. insert

// 1. insert 예제
        deque.offerFirst(3);
        deque.addFirst(2);
        deque.addFirst(1);
        deque.offer(4);
        deque.add(5);
        deque.addLast(6);

        System.out.println("add all element");
        deque.stream().forEach(i->System.out.println(i));

offerFirst(), addFirst() : head로 요소를 삽입한다.

add(), offer(), addLast(), offerLast() : tail로 요소를 삽입한다.

그림으로 보면 어래와 같다.

노란 네모박스가 Deque에 삽입되는 요소 데이터, 빨간 테두리의 원이 삽입이 일어난 순서이다.

실행 결과)

1,2,3,4,5,6이 삽입되어 있음을 알 수 있다.

2. Remove

// 2. remove 예제
        deque.removeFirst();

        System.out.println("removeFirst()");
        deque.stream().forEach(i->System.out.println(i));

        deque.remove();

        System.out.println("remove()");
        deque.stream().forEach(i->System.out.println(i));

        deque.pollLast();

        System.out.println("pollLast()");
        deque.stream().forEach(i->System.out.println(i));

        deque.pollFirst();

        System.out.println("pollFirst()");
        deque.stream().forEach(i->System.out.println(i));

removeFirst(), remove(), pollFirst() : head의 맨 앞에 있는 요소를 제거한다.

removeLast(), pollLast() : tail의 맨 앞에 있는 요소를 제거한다.

실행 결과)

요소가 사라지는 순서를 확인할 수 있다.

3. examine

// 3. examine 예제
        int first = deque.getFirst();
        int last = deque.getLast();
        int peek = deque.peek();
        int peekLast = deque.peekLast();

        System.out.println("first = " + first);
        System.out.println("last = " + last);
        System.out.println("peek = " + peek);
        System.out.println("peekLast = " + peekLast);

getFirst(), peek() : head의 요소를 확인한다.

getLast(), peekLast() : tail의 요소를 확인한다.

실행 결과)

- reference

docs.oracle.com/javase/7/docs/api/java/util/Deque.html

docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html