Queue

📌 Queue

 

 

Queue는 '대기열' 개념으로 선입선출(FIFO) 구조를 가진 자료구조다. 시간 순으로 어떤 작업 또는 데이터를 처리할 때
사용되며, 대표적으로 BFS(너비 우선 탐색)에 사용된다.

 

 

Method	Description
boolean add(Object o)	지정된 객체를 Queue에 추가 저장공간 부족 시 IllegalStateException 발생
Object remove()	Queue에서 객체를 꺼내 반환 비어있을 경우 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어온다. 비어있을 경우 NoSuchElementException 발생
boolean offer(Object o)	Queue의 마지막에 객체를 추가
Object poll()	Queue의 첫 번째 요소를 제거하고 반환
Object peek()	Queue의 첫 번째 요소를 제거없이 반환 비어있을 경우 null 반환

 

📌 Queue 종류

 

✅ PriorityQueue

 

각 요소들에 우선순위를 부여하여 우선순위가 높은 순으로 정렬하는 큐

 

🔍 특징

 

• 수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 사용된다. (네트워크 제어, 작업 스케줄링)
• 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야 한다.
• 저장공간으로 배열을 사용하며, 각 요소를 Heap 형태로 저장한다.
• Null 저장 불가능

 

👨‍💻 예시 1 (Comparable 구현)

 

 

package priorityQueue;

import java.util.Comparator;
import java.util.Random;

public class PriorityQueueApplication {

    public static void main(String[] args) {
    
        PriorityQueue<Student> pq1 = new PriorityQueue<>();
        PriorityQueue<Student> pq2 = new PriorityQueue<>(comp);
    
        Random rnd = new Random();
    
        char name = 'A';
        for (int i = 0; i < 10; i++) {
            int math = rnd.nextInt(10);
            int science = rnd.nextInt(10);

            pq1.offer(new Student(name, math, science));
            pq2.offer(new Student(name, math, science));
            name++;
        }
    
        System.out.println("[pq1 내부 배열 상태]");
        for (Object val : pq1.toArray()) {
            System.out.print(val);
        }
        System.out.println();
        System.out.println();
    
        System.out.println("[pq2 내부 배열 상태]");
        Object[] q = new Object[15];
        for (Object val : pq2.toArray(q)) {
            System.out.print(val);
        }
        System.out.println();
        System.out.println();
    
        System.out.println("[수학-과학-이름순 뽑기]");
        System.out.println("name\tmath\tscience");
        while (!pq1.isEmpty()) {
            System.out.print(pq1.poll());
        }
        System.out.println();
    
        System.out.println("[과학-수학-이름순 뽑기]");
        System.out.println("name\tmath\tscience");
        while (!pq2.isEmpty()) {
            System.out.print(pq2.poll());
        }
        
    }
    
    static class Student implements Comparable<Student> {
    
        char name;
        int math;
        int science;
        
        public Student(char name, int math, int science) {
            this.name = name;
            this.math = math;
            this.science = science;
        }
        
        /*
         * 수학점수가 높은 순
         * 수학점수가 같을 경우 과학 점수가 높은 순
         * 둘 다 같은 경우 이름순
         * */
        @Override
        public int compareTo(Student o) {
            if (this.math == o.math) {
                if (this.science == o.science) {
                    return this.name - o.name; //이름 오름차순
                }
                return o.science - this.science; //과학 내림차순(science -> math 교체하면 과학-수학-이름순)
            }
            return o.math - this.math; //수학 내림차순 (math -> science 교체하면 과학-수학-이름순)
        }
        
        @Override
        public String toString() {
            return name + "\t" + math + "\t" + science + "\n";
        }
        
    }
    
}

 

테스트 결과

 

👨‍💻 예시 2 (Comparator 인자)

 

우선순위 큐를 생성할 때 Comparator 인자를 넣어주면 그 인자의 내부 로직대로 정렬이 수행되므로 별도로 구현 코드를
작성하지 않아도 된다. 하지만 객체를 사용하고 커스터마이징 정렬을 원한다면 Comparable을 구현하는 것이 적합하다.

 

package priorityQueue;

import java.util.*;

public class PriorityQueueApplication {

    public static void main(String[] args) {
    
        //랜덤값 오름차순
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
        Random rnd = new Random();
        
        for (int i = 1; i <= 10; i++) {
            pq.offer(i, rnt.nextInt(10)); //<번호, 랜덤값>
        }
       
    }
    
}

 

✅ Deque(Double-ended queue)

 

출처:  https://st-lab.tistory.com/185

 

양방향 연결리스트와 유사한 개념으로 양방향 삽입/삭제 가능

 

Deque의 조상은 Queue이며, 구현체로 ArrayDeque와 LinkedList 등이 있다. 또한, offer()와 pollLast()를 조합하면 Stack으로도 사용할 수 있다.

 

🔍 메서드

 

출처:  https://st-lab.tistory.com/185

 

🔍 ArrayDeque

 

Deque 인터페이스를 구현한 클래스

 

 

• 스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다.
• 사이즈 조절이 가능
• Null 요소는 저장 불가능

 

🔍 LinkedList

 

List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있어 Deque/Stack/Queue 등을 구현할 수 있다.

 

🙋‍♂️ 큐 구현 (ArrayList vs LinkedList)

큐는 데이터를 꺼낼 때 항상 앞의 원소부터 삭제하므로 데이터를 이동 및 복사하는 작업이 동반된다. ArrayList는 배열
기반의 컬렉션 클래스이기 때문에 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 이동과 복사가 발생하므로 성능이 좋지
못하다. 따라서 큐는 데이터의 삽입/삭제가 용이한 LinkedList로 구현하는 것이 적합하다.

 

References:

 

https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-Collections-Framework-%EC%A2%85%EB%A5%98-%EC%B4%9D%EC%A0%95%EB%A6%AC#linkedlist_%ED%81%B4%EB%9E%98%EC%8A%A4-1

 

https://st-lab.tistory.com/181

 

https://st-lab.tistory.com/219

 

https://st-lab.tistory.com/185