[TIL] Day12_자료구조 Queue

Today I Learned

자료구조 Queue

선입선출 자료구조(FIFO)
먼저 들어온 데이터가 먼저 나가는 구조이다. 줄을 서는 것, 빨대와 자주 비유된다.

큐의 한 쪽 끝은 프런트(front), 삭제 연산만 수행
다른 한 쪽 끝은 리어(rear), 삽입 연산만 수행

1. Queue의 선언

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

Queue<자료형> q = new LinkedList<>();

2. 삽입

q.add(삽입할 value);
// 반환 값(boolean): 삽입 성공 시 true / 실패 시  Exception발생

q.offer(삽입할 value);
// 반환 값(boolean): 삽입 성공 시 true / 실패 시 false 반환

3. 삭제

q.remove(); 
// 반환 값(삭제된 value의 자료형): 삭제된 value / 삭제할 값이 없으면Exception("NoSuchElementException") 발생

q.remove(삭제할 value); 
// 반환 값(boolean): 큐에 해당 value가 존재하면 해당 값 삭제 후 true / 존재하지 않으면 false 반환

q.poll();
// 반환 값(삭제된 value의 자료형): 삭제된 value를 반환 / 삭제할 값이 없으면 null 반환

4. 가장 먼저 들어간 값 반환

q.element();
// 반환 값(큐 head에 위치한 value의 자료형): 큐 head에 위치한 value / 반환할 값이 없으면 Exception("NoSuchElementException") 발생

q.peek();
// 반환 값(큐 head에 위치한 value의 자료형): 큐 head에 위치한 value / 반환할 값이 없으면 null 반환

5. 초기화

q.clear();
// 반환 값 : void(X)

6. 크기

q.size();
// 반환 값(int) : 큐의 사이즈 반환

7. 검색

q.contains(찾을 value);
// 반환 값(boolean): 해당 값이 존재할 때 true / 해당 값이 없을 때 false 반환

8. 비어있는지 확인

q.isEmpty();
// 반환 값(boolean): 공백 큐이면 true / 공백 큐가 아니면 false 반환

Queue를 이용해서 푼 프로그래먼스 코딩테스트 <카드 뭉치>

import java.util.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
    	// 기본 값을 yes로 설정
        String answer = "Yes";

		// 큐를 이용해 카드를 순서대로 사용하는 법칙 적용
        Queue<String> q1 = new LinkedList<>(Arrays.asList(cards1));
        Queue<String> q2 = new LinkedList<>(Arrays.asList(cards2));
		
        // goal의 내용과 같은지 확인
        for (int i = 0; i < goal.length; i++) {
            if (goal[i].equals(q1.peek())) {
            	// card1에 같은 내용이 있으면 하나씩 지움
                q1.poll();
            } else if (goal[i].equals(q2.peek())) {
            	// card2에 같은 내용이 있으면 하나씩 지움
                q2.poll();
            } else {
            	// 두 곳 모두에 없을 때에는 goal에 도달하지 못하므로 answer값을 No로 변환
                answer = "No";
            }
        }
		
        // 답을 리턴
        return answer;
    }
}

9. Priority Queue

1) 정의

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

2) 특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조. (우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.)

• 내부 요소는 힙으로 구성된 이진트리 구조.

• 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN).

• 우선순위를 중요시해야 하는 상황에서 주로 쓰임.

3) 선언

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

Priority Queue를 이용하여 푼 프로그래머스 코딩테스트 <명예의 전당>

https://school.programmers.co.kr/learn/courses/30/lessons/138477

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
       int[] answer = new int[score.length];
       
       	// priority Queue를 이용하면
       	// 굳이 sort할 필요 없이 가장 작은 값을 구할 수 있음
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        // 스코어 개수만큼 반복
        for (int i = 0; i < score.length; i++) {
        	// 큐에 스코어를 하나씩 넣음
            q.add(score[i]);
            // k개만큼 들어갔을 때 FIFO이용 값 삭제
            if (q.size() > k) {
                q.poll();
            }
            // answer에 가장 작은 값을 차례대로 넣어줌
            answer[i] = q.peek();
        }
        
        return answer;
    }
}