Queue 직접 구현해보기 (JAVA)

Queue는 FIFO(First In Fisrt Out) 방식으로 동작하는 자료구조입니다. 삽입 연산은 front, 제거 연산은 rear라는 특정 위치에서 수행되므로 O(1)의 시간 복잡도를 갖고 탐색 연산은 해당 데이터를 찾을 때까지 수행해야 하므로 O(n)의 시간 복잡도를 갖습니다. enqueue, dequeue, offer, poll, peek, isEmpty, size 등의 메소드를 지원합니다.

구현

class Node {
    int data;
    Node next;

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

public class MyQueue {
    private Node front;
    private Node rear;
    private int size;

    public MyQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    // offer 메소드: 큐의 끝에 요소를 추가합니다.
    public boolean offer(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
        return true;
    }

    // enqueue 메소드: 큐의 끝에 요소를 추가합니다. (offer와 동일)
    public void enqueue(int data) {
        offer(data);
    }

    // poll 메소드: 큐의 앞에서 요소를 제거하고 반환합니다.
    public Integer poll() {
        if (isEmpty()) {
            return null;
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return data;
    }

    // dequeue 메소드: 큐의 앞에서 요소를 제거하고 반환합니다. (poll과 동일)
    public int dequeue() {
        Integer result = poll();
        if (result == null) {
            throw new RuntimeException("Queue is empty");
        }
        return result;
    }

    // peek 메소드: 큐의 앞에 있는 요소를 반환하지만 제거하지는 않습니다.
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return front.data;
    }

    // isEmpty 메소드: 큐가 비어있는지 확인합니다.
    public boolean isEmpty() {
        return front == null;
    }

    // size 메소드: 큐의 크기를 반환합니다.
    public int size() {
        return size;
    }
}