[JAVA] 3. 큐(Queue) 직접 구현하기

큐(Queue) 직접 구현하기

지난 시간에서는 큐(Queue)와 스택(Stack)에 대해 사용법 및 간단한 예시를 살펴봤습니다. 이번 시간에서는 Queue를 직접 구현해보는 시간을 가져보도록 합시다.

연결 리스트(LinkedList)를 활용한 큐 구현하기

연결 리스트란, 유연하게 크기 변경이 가능한 자료구조를 일컫습니다. 이 자료구조는 리스트와 노드로 구성되어있는데, 집합의 단위를 리스트(List), 각 요소의 단위를 노드(Node)라고 생각하시면 됩니다[연결 리스트에 대한 설명은 다음 시간에 더 자세히 다뤄보도록 하겠습니다].

이러한 자료구조 특성을 이용하여 큐 구현을 해보도록 합시다.

// Node 클래스 정의
class Node<T> {
    T data;
    Node<T> next;

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

// Node를 사용하여 Queue를 구현하는 클래스
public class QueueUsingNode<T> {
    private Node<T> front; // 큐의 맨 앞 요소를 가리키는 포인터
    private Node<T> rear;  // 큐의 맨 뒤 요소를 가리키는 포인터
    private int size;      // 큐의 크기를 저장하는 변수

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

    // 큐에 요소를 추가하는 메서드
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 큐에서 요소를 제거하고 반환하는 메서드
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        T removedItem = front.data;
        front = front.next;
        size--;
        return removedItem;
    }

    // 큐의 맨 앞 요소를 반환하는 메서드
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data;
    }

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

    // 큐의 크기를 반환하는 메서드
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        QueueUsingNode<Integer> queue = new QueueUsingNode<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("Dequeue: " + queue.dequeue()); // 1
        System.out.println("Dequeue: " + queue.dequeue()); // 2
        System.out.println("Peek: " + queue.peek());       // 3
        System.out.println("Size: " + queue.size());       // 1
    }
}

배열(Array)을 활용한 큐 구현하기

다음으로는 배열을 활용하여 Queue를 구현해 보도록 하겠습니다.

public class QueueUsingArray<T> {
    private static final int DEFAULT_CAPACITY = 10;     // 크기 지정
    private Object[] array;
    private int size;
    private int front;
    private int rear;

    public QueueUsingArray() {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.front = 0;
        this.rear = -1;
    }

    public void enqueue(T item) {
        if (size == array.length) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % array.length;     // rear를 한 칸 옮긴다.
        array[rear] = item;
        size++;
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        T removedItem = (T) array[front];
        front = (front + 1) % array.length;   // front를 한 칸 옮긴다.
        size--;
        return removedItem;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return (T) array[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        QueueUsingArray<Integer> queue = new QueueUsingArray<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("Dequeue: " + queue.dequeue()); // 1
        System.out.println("Dequeue: " + queue.dequeue()); // 2
        System.out.println("Peek: " + queue.peek());       // 3
        System.out.println("Size: " + queue.size());       // 1
    }
}

마치며

이렇게 배열과 연결 리스트를 활용하여 큐를 직접 구현해 봤습니다. 두 가지 구현 방법에 대한 차이점은 다음과 같습니다:

1️⃣ 배열: 배열을 사용하면 크기가 고정되어 데이터 추가 및 제거에 제한이 있을 수 있으며, 데이터를 지우기 위해서는 배열의 모든 요소를 한칸 씩 이동시켜야 하기 때문에 비효율적 입니다. 다만, 연결 리스트에 비해서는 연산 속도가 빠릅니다.

2️⃣ 연결 리스트: 연결 리스트를 사용하면 크기에 제한이 없어 데이터를 유동적으로 추가 및 제거할 수 있지만, 연산 속도는 배열에 비해 느릴 수 있습니다.

아래는 Queue와 관련된 기술 면접 포스팅입니다. 참고하시고 다음 시간에는 더 유용한 정보를 들고 찾아뵙도록 하겠습니다.