Queue

Jan 04, 2024

Contents

큐(Queue) : 데이터를 처리하기 전에 잠시 저장하고 있는 자료구조

FIFO(first-in-first-out) 형식

끝에 추가 됨

인터페이스

deque : 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있음

인터페이스 >ArrayDeque와 LinkedList 클래스들로 구현됨

Queue 메서드

add() : 큐 용량을 넘어서지 않는 선에서 원소를 추가

넘어가면 IllegalStateException이 발생

offer() : 큐 용량을 넘어서지 않는 선에서 원소를 추가

원소 추가에 실패하면 false가 반환

remove(), poll() : 큐의 처음에 있는 원소를 제거하거나 가져옴

어떤 원소가 제거되느냐는 큐의 정렬 정책에 따라 달라짐

큐에 원소가 없으면 remove() > NoSuchElementException 발생

poll() : null 반환

element(), peek() : 큐의 처음에 있는 원소를 삭제하지 않고 가져옴

큐에 원소가 없으면 element() > NoSuchElementException 발생

peek() : null 반환


package ex13;

import java.util.LinkedList;
import java.util.Queue;

public class QueueTest {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            q.add(i);
        }
        System.out.println("큐의 요소: " + q);

        int e = q.remove();
        System.out.println("삭제된 요소: " + e);
        System.out.println(q);
    }
}

우선 순위 큐(priority queues) : 우선순위에 따라 저장

기본적인 우선순위 - 원소들의 값

무작위로 삽입되었더라고 정렬된 상태로 원소들을 추출함

항상 정렬된 상태로 원소들을 저장하고 있는 것은 아님

heap라는 자료구조를 내부적으로 사용함

가장 높은 우순 순위의 작업이 큐에서 먼저 추출되어서 시작됨

대표적인 예시) 작업 스케줄링(job scheduling)

** heap : 이진트리의 일종

add()와 remove()를 호출 > 가장 작은 원소가 효율적으로 트리의 루트로 이동


package ex13;

import java.util.PriorityQueue;

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(30);
        pq.add(80);
        pq.add(20);

        System.out.println(pq);
        System.out.println("삭제된 원소: " + pq.remove());
    }
}

See more posts

Queue

Queue 메서드

More articles

람다식

Collections 클래스

Map

Set