[Java] Collection Framework - Queue Interface

Queue Interface

• 처음 들어온 원소(객체)가 먼저 나가는 First-In First-Out (FIFO) 구조입니다.

• LinkedList가 여기서 또 한번 나오는데 LinkedList는 List 인터페이스와 Queue를 상속한 인터페이스인 Deque를 구현한 클래스입니다.

Queue

PriorityQueue Class

우선순위 큐

• 우선순위 큐는 들어간 순서에 상관없이 우선순위 높은 데이터가 먼저 나오는 큐입니다.
• 일반적인 큐와 다르게, 원소(객체)에 우선순위를 부여하여 우선순위가 높은 순으로 정렬되고 꺼냅니다.
• 수행할 작업이 여러개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행할 때 사용되는 클래스로 주로 네트워크 제어나, 작업 스케쥴링에 사용됩니다.

공식문서를 살펴보면 필드에 Comparator 인터페이스가 선언되어 있습니다. 즉 우선순위 큐에 객체를 넣기 위해서 먼저, 우선순위를 설정하기 위해서 객체에 이 Comparable 인터페이스 compareTo() 메소드로 로직에 따라 자료 객체의 우선순위를 결정하여야 합니다.

 

• 객체이므로 null도 저장할 수 있을 것 같지만, 우선순위 큐에는 null을 저장할 수 없습니다.
• 저장 공간으로 Array를 사용하고, 각 요소(객체)를 힙 형태로 저장합니다.
  • 이진 트리의 한 종류인 힙을 사용함으로써, 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있습니다.

public class Student implements Comparable<Student> {

    private String name;
    private int priority;

    public Student(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compareTo(Student o) {
        // 우선순위 숫자가 낮은 것부터 뽑기
        if (this.priority < o.priority) { 
            return -1;
        } else if (this.priority == o.priority) { 
            return 0;
        }
        return 1;
    }
}

• 우선순위 큐에 객체를 넣기 전, 넣을 객체의 클래스에 Comparable 인터페이스의 compareTo() 메소드로 우선순위를 결정해줍니다.

public class Main {
    public static void main(String[] args) {
        Queue<Student> pq = new PriorityQueue<>();

        pq.add(new Student("kim", 1));
        pq.add(new Student("park", 4));
        pq.add(new Student("choi", 2));
        pq.add(new Student("na", 3));

        System.out.println(pq);

        // 차례대로 꺼내기 poll
        System.out.println(pq.poll().getName());
        System.out.println(pq.poll().getName());
        System.out.println(pq.poll().getName());
        System.out.println(pq.poll().getName());
    }
}

---

Deque Interface (extends Queue)

• Deque(Double-Ended Queue, 입구가 양쪽으로 열려있는 큐 형태)는 양쪽으로 넣고 빼는 것이 가능한 큐입니다.
• 스택 + 큐로 스택으로 사용도 가능하고, 큐로 사용도 가능합니다. 
• LinkedList와, ArrayDeque가 이 Deque 인터페이스를 구현한 클래스로, Deque는 Queue를 상속받은 인터페이스

---

ArrayDeque Class 

• Stack으로 사용하는 경우 Stack 클래스보다 빠른 속도를 지원하며, 어레이로 사용하는 경우 LinkedList보다 빠르다는 특징이 있습니다.
• 컬렉션에 null 저장이 불가능.

public class ArrayDequeTest {
    public static void main(String[] args) {
        Deque<String> adq = new ArrayDeque<>();
        adq.offerLast("KIM"); // [KIM]
        adq.offerFirst("PARK"); // [PARK, KIM]
        adq.offerFirst("CHOI"); // [CHOI, PARK, KIM]
        adq.offerLast("NA"); // [CHOI, PARK, KIM, NA]

        System.out.println(adq.pollFirst()); // CHOI <- [ PARK, KIM, NA ]
        System.out.println(adq.pollLast()); // NA <- [ PARK, KIM ]
    }
}

• offerLast()로 Array의 뒤에 요소를 채울 수 있고, offerFirst()로 Array의 앞에 요소를 채울 수 있습니다.
• pollLast()로 Array의 뒤에 요소를 뺄 수 있고, pollFirst()로 Array의 앞에 요소를 채울 수 있습니다.

---

LinkedList Class

• LinkedList 또한 Deque를 상속받아 스택, 큐처럼 사용할 수 있습니다.

• ~First(), ~Last() 메소드는 Deque에 구현되어 있으므로 Deque를 구현해야 합니다.

public class LinkedListTest {
    public static void main(String[] args) {
        Deque<String> ll = new LinkedList<>();
        ll.offer("Hello");
        ll.offer("World");
        ll.offerFirst("HI");
        System.out.println(ll.pollFirst());
    }
}

---

<참고 자료>

 

🧱 Java Collections Framework 종류 💯 총정리