자료구조 - Queue 인터페이스의 이해 및 사용법

Queue란 무엇인가?

• Queue는 데이터를 선입선출(FIFO, First-In-First-Out) 순서로 처리하는 자료 구조이다.

• 대기열을 상상하면 이해하기 쉽다. 먼저 도착한 데이터가 먼저 처리된다.

Queue의 주요 연산

• Enqueue: 큐에 데이터를 추가하는 연산.

• Dequeue: 큐에서 데이터를 제거하고 반환하는 연산.

• Front: 큐의 맨 앞에 있는 원소를 반환하는 연산.

• IsEmpty: 큐가 비어 있는지 확인하는 연산.

Queue의 종류

• 일반적인 큐: 기본적인 큐 구조.

• 우선순위 큐: 각 데이터에 우선순위가 할당되어 우선순위가 높은 데이터가 먼저 처리되는 큐.

• 환형 큐: 큐의 처음과 끝이 연결되어 있는 구조.

자바에서 Queue는 인터페이스로 정의되어 있으며, 다양한 구현체들이 제공되고 있다. 주로 사용되는 구현체로는 LinkedList나 ArrayDeque가 있다. 아래에서 간단한 예시 코드를 통해 자바에서의 Queue 사용법을 알아보겠다.

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

public class QueueExample {

    public static void main(String[] args) {
        // LinkedList를 사용한 Queue 생성
        Queue<String> queue = new LinkedList<>();

        // 데이터 추가 (Enqueue)
        queue.add("Apple");
        queue.add("Banana");
        queue.add("Cherry");

        System.out.println("Queue: " + queue);

        // 데이터 제거 및 반환 (Dequeue)
        String removedElement = queue.poll();
        System.out.println("Removed Element: " + removedElement);
        System.out.println("Queue after Dequeue: " + queue);

        // 맨 앞에 있는 원소 반환 (Front)
        String frontElement = queue.peek();
        System.out.println("Front Element: " + frontElement);

        // 큐가 비어 있는지 확인 (IsEmpty)
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is Queue Empty? " + isEmpty);
    }
}

이 코드에서 LinkedList를 사용하여 Queue를 생성하고, add() 메서드로 데이터를 Enqueue하고, poll() 메서드로 Dequeue를 수행한다. peek() 메서드를 사용하여 Front의 원소를 확인하고, isEmpty() 메서드로 큐가 비어 있는지 확인한다.

더 나아가, Java에서는 ArrayDeque를 사용하여도 Queue를 구현할 수 있다. ArrayDeque는 동적으로 크기를 조절할 수 있고, 큐의 양 끝에서 빠르게 데이터를 추가하거나 제거할 수 있는 자료 구조이다.

백준 1021 회전하는 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int N, M; // 큐의 크기 N, 뽑아내려는 원소의 개수 M
    static StringBuilder sb = new StringBuilder(); // 출력을 위한 StringBuilder
    static int count = 0; // 뽑아내는 횟수를 저장할 변수
    static LinkedList<Integer> q = new LinkedList<>(); // 큐를 구현할 LinkedList

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 초기 큐 생성
        st = new StringTokenizer(br.readLine());
        int[] temp = new int[M];
        for (int i = 0; i < M; i++)
            temp[i] = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++)
            q.add(i);

        // 큐에서 원소 뽑아내는 과정
        for (int i = 0; i < M; i++) {

            if (check(temp[i])) {
                // 뽑아내려는 원소가 큐의 첫 번째 위치에 있을 경우
                while (temp[i] != q.get(0)) {
                    q.addLast(q.pollFirst());
                    count++;
                }
            } else {
                // 뽑아내려는 원소가 큐의 첫 번째 위치에 없을 경우
                while (temp[i] != q.get(0)) {
                    q.addFirst(q.pollLast());
                    count++;
                }
            }
            q.poll(); // 뽑아낸 원소는 큐에서 제거
        }

        // 결과 출력
        System.out.println(count);
    }

    // 큐에서 특정 원소가 첫 번째 위치에 있는지 확인하는 메서드
    public static boolean check(int a) {

        for (int i = 0; i <= q.size() / 2; i++) {
            if (a == q.get(i))
                return true;
        }
        return false;
    }
}

추천 게시글
https://velog.io/@zdlwoaud/Stack (Stack 이란?)