[Queue & Deque & PriorityQueue] 큐 & 덱 & 우선순위 큐

큐 (Queue)

Queue 라는 단어의 사전적 의미는 '대기줄', '줄을 서서 기다리다'

먼저 줄을 선 사람이 먼저 서비스를 받듯이

Queue도 먼저 들어온 자료가 먼저 빠져 나가는 FIFO(First In First Out) 구조이다. 

 

 

Offer 과 Poll 대신 Enqueue, Dequeue 등으로도 표현된다. 

---

Queue의 특징

정해진 한 곳을 통해서 삽입과 삭제가 이루어지는 스택과는 달리

큐의 삽입과 삭제는 양 끝에서 이루어진다. 

 

새로운 원소의 삽입은 항상 큐의 뒤쪽에서,

원소의 삭제는 큐의 앞쪽에서 이루어지며

프론트와 리어라는 용어를 다음과 같이 정의한다. 

프론트(front) : 큐의 삭제 연산이 이루어지는 곳
리어(rear) : 큐의 삽입 연산이 이루어지는 곳

 

---

큐의 연산자

메서드	설 명
boolean add(Object o)	삽입 성공 시 true 반환 실패 시 IllegalStateException 발생
boolean offer(Object o)	삽입 성공 시 true, 실패 시 false 반환
Object remove()	삭제 된 value를 반환 공백 큐인 경우 NoSuchElementException 반환
boolean remove(Object o)	큐에 해당 value가 존재하면 값 삭제 후 true 존재하지 않으면 false 반환
Object poll()	삭제 된 value 반환 공백 큐이면 null 반환
Object element()	큐 head에 위치한 value 반환 값을 삭제하지 않음 공백 큐이면 NoSuchElementException 발생
Object peek()	큐 head에 위치한 value 반환 공백 큐이면 null 반환
void clear()	큐 초기화 (= 공백 큐 만들기)
int size()	큐 사이즈 반환
boolean contains(Object o)	큐에 해당 원소가 존재하는지 확인 해당 값이 존재할 때 true, 없을 때 false를 반환
boolean isEmpty()	공백 큐인지 확인 공백 큐이면 true, 아니면 false를 반환

 

Queue 인터페이스

자바에서 Queue는 인터페이스로 제공되며 필요에 따라 큐 컬렉션을 골라 사용할 수 있다.

---

Deque 인터페이스

 

Deque (Double-Ended Queue)는 양쪽으로 넣고 빼는 것이 가능한 큐를 말한다. 

스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다. 

 

Deque의 조상은 Queue이며, 구현체로는 ArrayDeque, LinkedList 등이 있다. 

---

ArrayDeque 클래스

 

스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다. 

사이즈에 제한이 없다. 

null 요소는 저장되지 않는다. 

 

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()	-
peekLask()	-	peek()

 

 

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(100); // [100]
deque.offerFirst(10); // [10, 100]
deque.offerFirst(20); // [20, 10, 100]
deque.offerLast(30); // [20, 10, 100, 30]

deque.pollFirst(); // 20 <- [10, 100, 30]
deque.pollLast(); // [10, 100] -> 30
deque.pollFirst(); // 10 <- [100]
deque.pollLast(); // [] -> 100

---

PriorityQueue 클래스

 

우선 순위를 가지는 큐 (= 우선 순위 큐)

원소에 우선 순위를 부여하여 우선 순위가 높은 순으로 정렬된다. 

 

네트워크 제어, 작업 스케줄링 등

수행할 작업이 여러 개 있고, 시간이 제한되어 있을 경우 우선 순위가 높은 것부터 수행하기 위해 쓰인다. 

 

compareTo() 메서드 로직에 따라 자료 객체의 우선순위를 결정하는 식으로 동작되기 때문에

우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야 한다. 

 

저장공간으로 배열을 사용하며, 각 요소를 힙(heap) 형태로 저장한다. 

 

null은 저장이 불가능하다. 

 

// 우선순위 큐에 저장할 객체는 필수적으로 Comparable를 구현
class Student implements Comparable<Student> {
    String name; // 학생 이름
    int priority; // 우선순위 값

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

    @Override
    public int compareTo(Student user) {
        // Student의 priority 필드값을 비교하여 우선순위를 결정하여 정렬
        if (this.priority < user.priority) {
            return -1;
        } else if (this.priority == user.priority) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", priority=" + priority +
                '}';
    }
}

 

public static void main(String[] args) {

    // 오름차순 우선순위 큐
    Queue<Student> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(new Student("주몽", 5));
    priorityQueue.add(new Student("세종", 9));
    priorityQueue.add(new Student("홍길동", 1));
    priorityQueue.add(new Student("임꺽정", 2));

    // 우선순위 대로 정렬되어 있음
    System.out.println(priorityQueue);
    // [Student{name='홍길동', priority=1}, Student{name='임꺽정', priority=2}, Student{name='주몽', priority=5}, Student{name='세종', priority=9}]

    // 우선순위가 가장 높은 값을 참조
    System.out.println(priorityQueue.peek()); // Student{name='홍길동', priority=1}

    // 차례대로 꺼내기
    System.out.println(priorityQueue.poll()); // Student{name='홍길동', priority=1}
    System.out.println(priorityQueue.poll()); // Student{name='임꺽정', priority=2}
    System.out.println(priorityQueue.poll()); // Student{name='주몽', priority=5}
    System.out.println(priorityQueue.poll()); // Student{name='세종', priority=9}
}

 

 

참고 자료

https://ttl-blog.tistory.com/170

[JAVA] Stack과 Queue + Deque, 우선순위 큐(PriorityQueue )

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#queue_%EC%9D%B8%ED%84%B0%ED%8E%98%EC%9D%B4%EC%8A%A4

🧱 Java Collections Framework 종류 💯 총정리