Queue 개념정리

Queue

 

선입선출(FIFO, First-In-First-Out) 방식

Queue는 특이하게 contains() 함수를 통해 어떠한 값이 포함되어있는지는 확인할 수 있지만
Index의 개념이 없어서 어떠한 값이 몇번째에 있는지는 알 수 없습니다.

 

 

선언방법

Queue<Integer> que = new LinkedList<Integer>();

Queue<객체> 변수명 = new LinkedList<객체>();
Queue와 LinkedList 유틸을 모두 import해줘야 정상적으로 사용 가능

 

 

 

• enqueue (offer): 큐의 끝에 요소를 추가합니다.
• dequeue (poll): 큐의 앞에서 요소를 제거하고 반환합니다.
• peek: 큐의 앞에 있는 요소를 제거하지 않고 반환합니다.
• isEmpty: 큐가 비어 있는지 확인합니다.
• size: 큐의 요소 개수를 반환합니다.

 

1. LinkedList를 이용한 큐 구현 예제

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

public class Main {
	public static void main(String[] args) {
    	Queue queue = new LinkedList();
        
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        
        queue.poll(); // 1 (가장 먼저 들어갔던 원소)
        queue.peek(); // 2
        
        queue.contains(3); // true
        queue.size()) // 3
        queue.isEmpty() // false
}

 

 

2. arrayList를 이용한 queue 구현

import java.util.*;

public class MyQueue {
    private ArrayList<Integer> listQueue = new ArrayList<Integer>();

    // 큐에 데이터 추가
    public void add(Integer data) {
        // ArrayList에 데이터 추가
        listQueue.add(data);
    }

    // 가장 먼저 추가된 데이터를 큐에서 삭제하고, 삭제한 데이터 반환
    public Integer poll() {
        // 큐가 비어있으면 null 반환
        if (this.size() == 0) {
            return null;
        } else {
            // 큐가 비어있지 않으면 가장 앞에 있는 데이터를 삭제하고 반환
            return listQueue.remove(0);
        }
    }

    // 큐에 추가된 데이터의 크기 반환
    public int size() {
        // ArrayList의 크기 반환
        return listQueue.size();
    }

    // 큐에 가장 먼저 추가된 데이터 반환 (삭제하지 않음)
    public Integer peek() {
        // 큐가 비어있으면 null 반환
        if (this.size() == 0) {
            return null;
        } else {
            // 큐가 비어있지 않으면 가장 앞에 있는 데이터 반환
            return listQueue.get(0);
        }
    }

    // 큐에 들어있는 모든 데이터를 문자열로 변환하여 반환
    public String show() {
        // ArrayList를 문자열로 변환하여 반환
        return listQueue.toString();
    }

    // 큐에 들어있는 모든 데이터 삭제
    public void clear() {
        // ArrayList의 모든 요소 삭제
        listQueue.clear();
    }
}

 

큐의 응용

큐는 다양한 문제 해결에 유용하게 쓰입니다. 대표적인 예로는 다음과 같습니다:

1. 프린터 대기열: 인쇄 작업이 도착한 순서대로 처리됩니다.
2. 멀티스레딩: 작업 스케줄링을 위해 작업들을 큐에 넣어 순차적으로 처리합니다.
3. BFS (Breadth-First Search): 그래프나 트리의 너비 우선 탐색을 수행할 때 사용됩니다.
4. 캐시 구현: 순환 버퍼(circular buffer)나 최근 사용되지 않은 페이지 제거 알고리즘(LRU, Least Recently Used) 등을 구현할 때 사용됩니다.