[JAVA] Queue를 LinkedList/ArrayDeque로 구현했을 때 차이점

*작성자는 공부 중인 학생으로 잘못 된 정보가 있을 수 있음을 알려드립니다.

 

Queue와 관련된 문제들의 풀이를 보면서

Queue를 정의할 때 두가지 방법으로 나뉘는 것을 발견했다.

 

//방법1 : LinkedList 이용
Queue<Integer> queue = new LinkedList<>();

//방법2 : ArrayDeque 이용
Queue<Integer> queue = new ArrayDeque<>();

 

위 두가지 방법의 차이점은 무엇일까?

그리고 왜 Queue<Integer> queue = new Queue<>();로 생성할 수 없는 것일까?

 

1. new Queue<>()를 사용할 수 없는 이유

결론부터 말하자면 Queue는 클래스가 아닌 인터페이스이기 때문이다.

 

인터페이스는 메서드의 선언만 포함하고 실제 구현은 포함하지 않는다.

public interface Animal {
    void speak();
    String getName();
}

메서드의 선언만 포함하고 있기 때문에 각 클래스에서 메서드에 대한 정의를 해줘야한다.

 

이 과정에서 또 의문이 들 수 있다. 

결국 클래스에서 메서드에 대한 정의가 필요하면 굳이 인터페이스가 필요할까?

 

인터페이스를 사용하면 동일한 인터페이스를 구현한 여러 클래스가 동일한 방식으로 동작할 수 있다.

 

아래 예제를 통해 더 자세히 알아보자.

public interface Animal {
    void speak();
}

public class Dog implements Animal {
    public void speak() {
        System.out.println("The dog barks.");
    }
}

public class Cat implements Animal {
    public void speak() {
        System.out.println("The cat meows.");
    }
}

public class AnimalHandler {
    public void makeAnimalSpeak(Animal animal) {
        animal.speak();
    }

    public static void main(String[] args) {
        Animal dog = new Dog();
        Animal cat = new Cat();

        AnimalHandler handler = new AnimalHandler();
        handler.makeAnimalSpeak(dog);
        handler.makeAnimalSpeak(cat);
    }
}

 

만약 cat과 dog 클래스가 animal 인터페이스를 상속받지 않으면

animal.speak();가 아닌, dog.speak(), cat.speak()라고 사용해야 한다.

 

이것이 얼마나 편한 것인지 감을 잡기 위해서는 배열로 생각해보자.

dog와 cat으로 이루어진 배열이 있을 때, 모두가 한번씩 speak()할 때

for문을 사용해야 할 것이다.

 

만약 interface가 없다고 한다면

for문 안에서는 if문을 이용해 dog인지 확인한 후 dog.speak()를 하고

if-else를 이용해 cat인지 확인한 후 cat.speak()를 할 것이다.

 

하지만 interface를 사용하면

for문 안에서는 animal.speak()를 사용하면

각 클래스에서 정의된 speak()함수를 자동으로 불러오게 된다.

 

이를 우리는 다형성이라고 한다.

 

즉, 우리가 가장 첫 문장에서 말했던

Queue<Integer> queue = new LinkedList<>();에서

Queue는 메서드의 선언만 가지고 있는 Interface이고

LinkedList는 메서드에 대한 구체적인 내용을 담고있는 Class이다.

 

클래스(Class)와 인터페이스(Interface)의 차이를 표로 나타내면 다음과 같다.

특징	클래스(Class)	인터페이스(Interface)
인스턴스화 (New ~가능?)	가능	불가능
상속	단일 상속	다중 상속
구현	메서드와 필드의 구현을 가짐	메서드 선언만 가짐. 자바 8 이후 기본 메서드 허용
용도	객체의 상태와 동작을 정의	클래스가 구현해야 할 메서드의 명세를 정의

 

2. 클래스에 따른 Queue의 차이점

위에서 말했듯이 Queue는 Interface이기 때문에

어떤 클래스를 사용하느냐에 따라 연산의 방법이 달라질 수 있다.

 

일단 Queue의 Interface에서 가지는 기본 함수는 다음과 같은 것들이 있다.

삽입연산	boolean add(E e)	큐의 맨 끝에 요소를 추가한다. 큐의 용량 제한을 초과하면 예외를 던진다.
	boolean offer(E e)	큐의 맨 끝에 요소를 추가한다. 큐의 용량 제한을 초과하면 'false'를 반환한다.
삭제 연산	E remove()	큐의 맨 앞에 있는 요소를 제거하고 반환한다. 큐가 비어있으면 예외를 던진다.
	E poll()	큐의 맨 앞에 있는 요소를 제거하고 반환한다. 큐가 비어 있으면 null을 반환한다.
탐색 연산	E element()	큐의 맨 앞에 있는 요소를 반환한다. 큐가 비어 있으면 예외를 던진다.
	E peek()	큐의 맨 앞에 있는 요소를 반환한다. 큐가 비어 있으면 null을 반환한다.

 

Queue 구현 클래스에는 LinkedList, ArrayDeque, PriorityQueue 등이 있는데

어떤 구현 클래스를 사용하느냐에 따라 각 연산의 방법이 달라지기 때문에

상황에 맞게 구현 클래스를 사용하여 성능을 향상시킬 수 있다.

 

LinkedList

👍적합한 상황

양쪽 끝에서 자주 삽입/삭제가 발생하는 경우

메모리 할당을 미리 예측할 수 없고, 큐의 크기가 동적으로 변경되는 경우

 

👎비적합한 상황

인덱스 기반 접근이 필요한 경우

메모리 사용이 중요한 경우 (노드당 추가 메모리를 사용하기 때문)

 

ArrayDeque

👍적합한 상황

대부분의 큐 연산이 큐의 끝에서 발생하고, 빠른 인덱스 접근이 필요한 경우

메모리 효율성이 중요한 경우(연속된 배열을 사용하기 때문)

 

👎비적합한 상황

큐의 중간에서 자주 삽입/삭제가 발생하는 경우(배열 크기 조정이 필요할 수 있기 때문)

 

PriorityQueue

👍적합한 상황

우선순위에 따라 요소를 처리해야 하는 경우

우선순위가 높은 요소를 빠르게 찾아야 하는 경우

 

👎비적합한 상황

순서가 중요한 FIFO 큐가 필요한 경우

(우선순위에 따라 정렬되어 순서가 바뀔 수 있기 때문)