[Java API] Queue, Deque 인터페이스(ArrayDeque, LinkedList)

https://claremont.tistory.com/entry/Java-API-%EC%BB%AC%EB%A0%89%EC%85%98-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%ACCollection-Framework

[Java API] 컬렉션 프레임워크(Collection Framework)

https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep6-1-%ED%81%90Queue

[자료구조] ep6-1) 큐(Queue)

큐(Queue)의 개념은 위의 게시글을 참고하자

Java에서는 enqueue 가 offer, dequeue가 poll 이다

"FIFO"

 

 

컬렉션 프레임워크 - 컬렉션 인터페이스 - 큐 인터페이스 - 데크 인터페이스

(참고) LinkedList는 List 인터페이스와 Deque 인터페이스 둘 다 구현한다

 

 

(Queue 인터페이스 사용 예시 코드)

package collection.deque;

import java.util.ArrayDeque;
import java.util.Queue;

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        // Queue<Integer> queue = new Linkedlist<>();

        // 데이터 추가: offer()
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue);

        // 조회: peek()
        System.out.println("queue.peek() = " + queue.peek());

        // 데이터 꺼내기: poll()
        System.out.println("poll = " + queue.poll());
        System.out.println("poll = " + queue.poll());
        System.out.println("poll = " + queue.poll());
        System.out.println(queue);
    }
}

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

 

https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep6-3-%EB%8D%B0%ED%81%ACDeque

[자료구조] ep6-3) 데크(Deque)

데크(Deque) 개념은 위의 게시글을 참고하자

데크는 큐와 스택의 기능을 모두 포함하고 있어 매우 유용하다

왼쪽이 First 이고, 오른쪽이 Last 이다

 

- offerFirst(): 앞에 추가한다

- offerLast(): 뒤에 추가한다

- pollFirst(): 앞에서 꺼낸다

- pollLast(): 뒤에서 꺼낸다

 

 

(Deque 인터페이스 사용 예시 코드)

package collection.deque;

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

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

        // 데이터 추가: offer()
        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);

        // 조회: peek()
        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque.peekLast() = " + deque.peekLast());

        // 데이터 꺼내기: poll()
        System.out.println("pollFirst = " + deque.pollFirst());
        System.out.println("pollFirst = " + deque.pollFirst());
        System.out.println("pollLast = " + deque.pollLast());
        System.out.println("pollLast = " + deque.pollLast());
        System.out.println(deque);
    }
}

 

 

 

[ArrayDeque vs LinkedList] - 모든 면에서 ArrayDeque가 승리

앞, 뒤 100만 건 입력 평균

- ArrayDeque: 110ms (승)

- LinkedList: 480ms (패)

 

앞, 뒤 100만 건 조회 평균

- ArrayDeque: 9ms (승)

- LinkedList: 20ms (패)

 

둘의 차이는 ArrayList vs LinkedList의 차이와 비슷한데, 작동 원리가 하나는 배열을 하나는 동적 노드 링크를 사용하기 때문이다. ArrayDeque는 추가로 특별한 원형 큐 자료 구조를 사용하는데 덕분에 앞, 뒤 입력 모두 O(1)의 성능을 제공한다. 물론 LinkedList도 앞, 뒤 입력 모두 O(1)의 성능을 제공한다.
이론적으로 LinkedList가 삽입 삭제가 자주 발생할 때 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화 등을 고려할 때 배열을 사용하는 ArrayDeque가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

그냥 ArrayDeque만 사용하면 된다고 생각하자

 

 

 

ㅁDeque와 Stack, Queue

Deque는 양쪽으로 데이터를 입력하고 출력할 수 있으므로, 스택과 큐의 역할을 모두 수행할 수 있다

Deque를 Stack과 Queue로 사용하기 위한 메서드까지 제공한다

 

ㅇStack

앞부분에서 push()와 pop()이 모두 이루어진다!

- push(): 앞에서 추가한다

- pop(): 앞에서 꺼낸다

자바의 Stack 클래스는 성능이 좋지 않고 하위호환을 위해서 남겨져 있다. Stack 자료구조가 필요하면 Deque에 ArrayDeque 구현체를 사용하자.

package collection.deque;

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

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

        // 데이터 추가: push()
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque);

        // 조회: peek()
        System.out.println("deque.peek() = " + deque.peek());

        // 데이터 꺼내기: pop()
        System.out.println("pop = " + deque.pop());
        System.out.println("pop = " + deque.pop());
        System.out.println("pop = " + deque.pop());
        System.out.println(deque);
    }
}

 

 

ㅇQueue

앞부분에서 poll()이 이루어진다!

- offer(): 뒤에서 추가한다

- poll(): 앞에서 꺼낸다

Deque 인터페이스는 Queue 인터페이스의 자식이기 때문에, 단순히 Queue의 기능만 필요하면 Queue 인터페이스를 사용하고, 더 많은 기능이 필요하다면 Deque 인터페이스를 사용하면 된다.

package collection.deque;

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

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

        // 데이터 추가: offer()
        deque.offer(1);
        deque.offer(2);
        deque.offer(3);
        System.out.println(deque);

        // 조회: peek()
        System.out.println("deque.peek() = " + deque.peek());

        // 데이터 꺼내기: poll()
        System.out.println("poll = " + deque.poll());
        System.out.println("poll = " + deque.poll());
        System.out.println("poll = " + deque.poll());
        System.out.println(deque);
    }
}

 

 

 

 

 

 

 

참고 및 출처: 김영한의 실전 자바 - 중급 2편

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2