밤둘레

연결리스트를 이용해서 Queue를 구현해보겠습니다.

1. Node.java

데이터를 저장하는 클래스입니다.
데이터를 저장할 T data 멤버변수와 다음 노드를 가리키는 Node<T> next 멤버변수로 구성됩니다.

public class Node<T> {

    private T data;
    private Node<T> next;

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

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

}

2. Queue.java

queue를 연결리스트로 구현한 소스입니다. 

import java.util.NoSuchElementException;

public class Queue<T> {

    private Node<T> first; // 첫번째 노드가 저장되어 있음
    private Node<T> last; // 마지막 노드가 저장되어 있음

    //노드 삽입
    public void add(T data) {
        Node<T> node = new Node<T>(data);

        if (last != null) {
            //마지막 노드와 추가할 노드와 연결한다.
            last.setNext(node);
        }

        //마지막 노드를 추가할 노드로 갱신한다.
        last = node;

        if (isEmpty()) {
            first = last;
        }
    }
   
    //노드 삭제
    public T remove() {

        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        T data = first.getData();
        //첫번째 노드를 다음에 저장된 노드로 교체한다.
        first = first.getNext();

        //교체한 노드가 null이면 last도 null처리 해준다.
        if (first == null) {
            last = null;
        }

        return data;
    }
  
    //노드가 비어있는지 확인
    public boolean isEmpty() {
        //첫번째 노드가 없다는 것은 비어있다는 의미
        return first == null;
    }
    
    // 노드 검색
    public T peek() {
        if (first == null) {
            throw new NoSuchElementException();
        } else {
            return first.getData();
        }
    }

}

3. Main.java

public class Main {

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

        System.out.println(queue.remove()); //1
        System.out.println(queue.remove()); //2
        System.out.println(queue.peek());   //3
        System.out.println(queue.remove()); //3
        System.out.println(queue.remove()); //4
        System.out.println(queue.isEmpty()); //true
        System.out.println(queue.peek());   //Exception in thread "main" java.util.NoSuchElementException
    }
}