Queue

큐(Queue) 란?

큐는 FIFO(First in First Out) 구조를 가진 자료구조. 즉, 먼저 들어간 데이터가 먼저 나오는 원리

Queue 주요 연산자

-offer(E e) : 큐의 맨 끝에 요소를 추가
-poll() : 큐의 맨 앞에서 요소를 제거하고 반환
-peek() : 큐의 맨 앞에 있는 요소를 제거하지 않고 반환
-isEmpty() : 큐가 비어있는지 확인
+)비어있으면 true, 가득 차 있으면 false
-size() : 큐의 요소 개수를 반환

Queue의 시간복잡도

-offer(E e) : O(1)
-poll() : O(1)
-peek() : O(1)
-isEmpty() : O(1)
-size() : O(1)

Queue 사용법

-LinkedList : 일반적인 큐 구현에 많이 사용됨. 요소의 삽입/삭제가 빈번히 발생하는 상황에도 성능이 좋음
-ArrayDeque : 내부적으로 배열을 사용하기 때문에 큐의 크기가 제한되어 있는 상황에서 유리할 수 있음. 성능면에서 일반적으로 더 우수함

우선순위 큐(Priority Queue)

-각 요소는 우선순위를 가지고 있으며, 우선순위가 높은 요소가 낮은 요소보다 먼저 처리됨
-일반 큐와 달리 요소를 삽입할 때 우선수위에 따라 자동으로 정렬되거나 최소/최대 값이 빠져나감

Priority Queue 주요 연산자

-offer(E e) : 요소를 큐에 추가. 이 때 요소는 우선순위에 따라 적절한 위치에 삽입
-poll() : 우선순위가 가장 높은 요소를 큐에서 제거하고 반환
-peek() : 우선순위가 가장 높은 요소를 제거하지않고 반환
-isEmpty() : 큐가 비어있는지 확인
+)비어있으면 true, 가득 차 있으면 false

Priority Queue의 시간복잡도

-offer(E e) : O(log n)
-poll() : O(log n)
-peek() : O(1)
-isEmpty() : O(1)

+)우선순위에 따라 요소가 정렬되어 삽입되고 삭제되기에 O(log n)의 시간 복잡도를 가짐

Priority Queue 사용법

이진 힙(Binary Heap) 을 기반으로 구현하는 것이 일반적. 최소 힙은 루트 노드가 최소값을 가지며, 최대 힙은 루트 노드가 최대값을 가짐

BAEKJOON

1021 회전하는 큐 문제풀이

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        LinkedList<Integer> queue = new LinkedList<>();
        if (N <= 50) {
            for (int i = 1; i <= N; i++) {
                queue.offer(i);
            }
        }
        int[] pickNum = new int[M];
        for (int i = 0; i < M; i++) {
            pickNum[i] = sc.nextInt();
        }

        int move = 0;
        for (int i : pickNum) {
            int target = queue.indexOf(i);
            int left = target;
            int right = queue.size() - target;

            move += Math.min(left, right);

            if (left <= right) {
                for (int j = 0; j < left; j++) {
                    queue.offer(queue.poll());
                }
            } else {
                for (int j = 0; j < right; j++) {
                    queue.offerFirst(queue.pollLast());
                }
            }
            queue.poll();
        }
        System.out.println(move);
    }
}