컬렉션 프레임워크 - Deque (Stack, Queue)

참고자료:

김영한의 실전 자바 - 중급 2편 | 김영한 - 인프런

 

이제 Deque라는 자료구조를 알아보자. 왜 Stack, Queue를 Deque로 사용할 수 있을까? 

우선, Deque는 "Double Ended Queue"의 약자로 이름에서 알 수 있듯 양쪽 끝에서 요소를 추가하거나 제거할 수 있다. 그래서 큐와 스택의 기능을 모두 포함하고 있어 매우 유연한 자료구조이다. 보통 '덱'이라고 많이 불린다.

 

Deque의 구조

 

Queue에서는 전통적으로 넣을 때 `offer` 라는 단어를 사용하고 꺼낼 때 `poll`이라는 단어를 사용한다.

이 Deque가 결국 DE`Queue`이기 때문에 역시 같은 단어를 사용한다. 근데 Stack의 기능도 가질 수 있기 때문에 Stack에서 전통적으로 넣을 때 `push`라는 단어를 사용하고 꺼낼 때 `pop`이라는 단어를 사용하는데 이 메서드또한 Deque는 지원한다.

• `offerFirst()`: 앞에 추가한다.
• `offerLast()`: 뒤에 추가한다.
• `pollFirst()`: 앞에서 꺼낸다.
• `pollLast()`: 뒤에서 꺼낸다.

 

결국 이 Deque로 Stack, Queue를 모두 해결할 수 있기 때문에 이 자료구조를 사용하면 된다. 그리고 또한 Deque의 대표적인 구현체로 `ArrayDeque`와 `LinkedList`가 있는데 이 `ArrayDeque`가 성능상으로도 훨씬 유리하기 때문에 그냥 ArrayDeque를 Stack이나 Queue자료구조를 사용해야 할 때 사용하면 된다.

 

Deque를 Stack으로 사용해보기

DequeStackMain

package org.example.collection.dequeue;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeStackMain {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // Stack을 Deque로 사용하기
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque);

        System.out.println("deque.peek() = " + deque.peek());

        System.out.println("deque.pop() = " + deque.pop());
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println(deque);
    }
}

실행결과

[3, 2, 1]
deque.peek() = 3
deque.pop() = 3
deque.pop() = 2
deque.pop() = 1
[]

 

Stack에서 전통적으로 사용하는 단어인 `pop`과 `push`를 제공한다.

 

Deque를 Queue로 사용해보기

DequeQueueMain

package org.example.collection.dequeue;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeQueueMain {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // Queue를 Deque로 사용하기
        deque.offer(1);
        deque.offer(2);
        deque.offer(3);
        System.out.println(deque);

        System.out.println(deque.peek());

        System.out.println("deque.poll() = " + deque.poll());
        System.out.println("deque.poll() = " + deque.poll());
        System.out.println("deque.poll() = " + deque.poll());
        System.out.println(deque);
    }
}

실행결과

[1, 2, 3]
1
deque.poll() = 1
deque.poll() = 2
deque.poll() = 3
[]

Queue에서 전통적으로 사용하는 `offer`와 `poll`을 제공한다.

 

Deque로 앞과 뒤 원하는 곳에 데이터 넣고 빼기

DequeMain

package org.example.collection.dequeue;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeMain {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        deque.offerFirst(1);
        System.out.println(deque);
        deque.offerFirst(2);
        System.out.println(deque);
        deque.offerLast(3);
        System.out.println(deque);
        deque.offerLast(4);
        System.out.println(deque);

        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque.peekLast() = " + deque.peekLast());

        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println(deque);
    }
}

실행결과

[1]
[2, 1]
[2, 1, 3]
[2, 1, 3, 4]
deque.peekFirst() = 2
deque.peekLast() = 4
deque.pollFirst() = 2
deque.pollFirst() = 1
deque.pollLast() = 4
deque.pollLast() = 3
[]

 

 

 

결론

Deque는 굉장히 유연하게 사용할 수 있기 때문에 Stack으로도 Queue로도 사용이 가능하다.

그래서 Stack, Queue를 고려한다면 Deque를 사용하면 되는데 Deque의 대표적인 구현체는 `ArrayDeque`와 `LinkedList`다.

이 중에서 성능적으로 `ArrayDeque`가 훨씬 유리하기 때문에 이 구현체를 사용하면 된다.