큐(Queue)

Kkd·2024년 12월 26일

매일메일 개념정리

목록 보기

46/93

큐(Queue)

큐(Queue)는 선형 자료구조 중 하나로, 데이터를 선입선출(FIFO, First In First Out) 방식으로 관리합니다. 즉, 먼저 삽입된 데이터가 가장 먼저 제거되거나 사용됩니다. 큐는 양쪽 끝에서 작동하며, 한쪽 끝에서는 데이터를 삽입하고 다른 쪽 끝에서는 데이터를 제거합니다.

큐의 주요 연산

enqueue: 큐의 끝(Rear)에 데이터를 삽입.
dequeue: 큐의 앞(Front)에서 데이터를 제거하고 반환.
peek (또는 front): 큐의 앞(Front) 데이터를 제거하지 않고 반환.
isEmpty: 큐가 비어 있는지 확인.
isFull: 큐가 꽉 찼는지 확인 (고정 크기 큐인 경우).

큐의 특징

선입선출(FIFO): 먼저 삽입된 데이터가 먼저 사용됨.
양쪽 끝 활용: 삽입과 삭제 작업이 각각 Rear와 Front에서 이루어짐.
연속적 저장: 일반적으로 배열(Array) 또는 연결 리스트(Linked List)로 구현.

큐의 구현

1. 배열 기반 큐

class Queue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public Queue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    // 데이터 삽입
    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("큐가 가득 찼습니다.");
        }
        rear = (rear + 1) % capacity; // 순환 큐 구현
        queue[rear] = value;
        size++;
    }

    // 데이터 제거 및 반환
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어 있습니다.");
        }
        int value = queue[front];
        front = (front + 1) % capacity; // 순환 큐 구현
        size--;
        return value;
    }

    // 큐의 맨 앞 요소 반환
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어 있습니다.");
        }
        return queue[front];
    }

    // 큐가 비어 있는지 확인
    public boolean isEmpty() {
        return size == 0;
    }

    // 큐가 가득 찼는지 확인
    public boolean isFull() {
        return size == capacity;
    }
}

public class Main {
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println(queue.dequeue()); // 출력: 10
        System.out.println(queue.peek()); // 출력: 20
        System.out.println(queue.isEmpty()); // 출력: false
    }
}

2. 연결 리스트 기반 큐

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListQueue {
    private Node front;
    private Node rear;

    public LinkedListQueue() {
        this.front = null;
        this.rear = null;
    }

    // 데이터 삽입
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear != null) {
            rear.next = newNode;
        }
        rear = newNode;
        if (front == null) {
            front = rear;
        }
    }

    // 데이터 제거 및 반환
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어 있습니다.");
        }
        int value = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return value;
    }

    // 큐의 맨 앞 요소 반환
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어 있습니다.");
        }
        return front.data;
    }

    // 큐가 비어 있는지 확인
    public boolean isEmpty() {
        return front == null;
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println(queue.dequeue()); // 출력: 10
        System.out.println(queue.peek()); // 출력: 20
        System.out.println(queue.isEmpty()); // 출력: false
    }
}