[자료구조] 큐(Queue)의 이해와 구현 with 자바

 

🤔 Queue?

'대기열'이라고 생각하면 이해가 쉬울 것 입니다.

흔히 게임에서 '큐 돌린다', '큐 잡혔다' 같은 말을 들은적이 있을 것 입니다 이때 큐는 Queue를 의미합니다.

큐는 FIFO(First In First Out)선입선출 즉, 먼저 들어간것이 먼저 빠진다 라는 특징이 있습니다.

즉 대기열처럼 데이터를 시간 순서에 따라 순차적으로 처리할때 쓰일 수 있습니다.

한쪽 끝에서는 삽입, 반대쪽 끝에서는 삭제 작업이 이루어지는 자료구조 입니다.

 

✔ Queue 인터페이스 만들기

실제 자바의 큐 인터페이스 에는 더 많은 메소드들이 있지만 큐의 특징적인 메소드만 우선 만들어보고 추후에 큐의 기능을 확장한 덱(Deque) 자료구조도 만들어보기 위해 최소한의 메소드만 만들어 보겠습니다.

메소드

메소드명	리턴 타입	설명
offer(E e)	boolean	큐의 마지막(Rear)에 요소를 추가합니다.
poll()	E	큐의 첫 번째(Front)요소를 제거하고 제거 된 요소를 반환합니다.
peek()	E	큐의 첫 번째(Front) 요소를 제거하지 않고 반환합니다.

 

public interface Queue<E> {
    boolean offer(E e);
    E poll();
    E peek();
}

 

✔ Queue 구현하기

LinkedList를 기반으로  큐를 구현하려고 합니다.

그러기 위해서 데이터를 담을 Node를 구현해 보겠습니다.

Node

public class Node<E> {
     E data;
     Node<E> link;

    public Node(E data){
        this.data = data;
        this.link = null;
    }
}

 

앞서만든 큐 인터페이스와 노드 클래스를 사용하여 LinkedList기반으로 큐를 구현해 보겠습니다.

LinkedListQueue

public class LinkedListQueue<E> implements Queue<E> {

    private Node<E> front; // 큐의 가장 앞 노드
    private Node<E> rear; // 큐의 가장 뒤 노드
    private int size; // 큐의 전체 요소의 개수

    //생성자를 통해 초기화
    public LinkedListQueue(){
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    @Override
    public boolean offer(E e) {
        Node<E> newNode = new Node<>(e);

        //큐가 비어있을 경우
        if(size == 0){
            front = newNode; //노드를 가장 앞(front)에 설정
        } else {
            // 큐가 비어있지 않을 경우
            // 큐의 가장 뒤(rear)의 노드와 추가할 노드를 연결(link)합니다.
            rear.link = newNode;
        }

        rear = newNode; //추가할 노드를 가장 뒤(rear)의 노드로 설정
        size++; // 큐의 요소 개수 증가

        return true;
    }

    @Override
    public E poll() {
        if( size == 0 ){
            return null;
        }

        E data = front.data; // 큐의 가장 앞(front)노드의 데이터를 변수에 저장합니다.
        Node<E> prevNode = front.link; // 큐의 가장 앞 노드와 연결되어 있는 노드를 변수에 저장합니다.

        //가장 앞에 있던 노드를 삭제 합니다
        front.data = null;
        front.link = null;

        //위에서 저장했던 가장 앞 노드와 연결되었던
        //즉, 가장 앞 노드 다음으로 추가(offer)된 노드를 가장 앞 노드로 설정합니다.
        front = prevNode;
        size--; // 큐의 요소 개수 감소

        return data;
    }

    @Override
    public E peek() {
        if( size == 0 ){
            return null;
        }

        return front.data;
    }

    public int size(){
        return size;
    }

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

 

📌

더많은 메소드가 있지만 큐의 핵심적인 메소드만 구현해 보았습니다.

노드클래스를 사용하여 추가되는 노드들을 한쪽방향으로 연결(link)하는걸 생각한다면 쉽게 이해가 될것입니다.

또한 큐의 구현체에 가장 앞(front)과 가장 뒤(rear)를 선언하여 front를 통해 값을 추출하고, rear를 통해 값을 추가하는 방법으로 큐의 특징적인 기능을 구현 해보았습니다.