[DataStructure] Queue

기본적인 자료구조인 큐에 대해서 작성한 소스를 통해 알아보도록 하겠습니다.

 

이미지출처: https://velog.io/@suitepotato/00004

전체소스

import java.util.NoSuchElementException;

class Queue<T> {

    private Node<T> front;
    private Node<T> rear;

    public void add(T item) {
        Node<T> node = new Node<T>(item);

        if(rear != null)
            rear.next = node;
        rear = node;
        if(front == null)
            front = rear;
    }

    public T remove() {
        if(front == null)
            throw  new NoSuchElementException();

        T data = front.data;
        front = front.next;

        if(front == null)
            rear = null;

        return data;
    }

    public T peek() {
        if(front == null)
            throw new NoSuchElementException();
        return front.data;
    }

    public boolean isEmpty() {
        return front == null;
    }

    class Node<T> {
        private T data;
        private Node<T> next;

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

Inner Class Node<T>

  class Node<T> {
    private T data;
    private Node<T> next;

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

Queue클래스는 내부클래스로 구현된 노트타입의 first와 rear필드를 갖습니다.

내부클래스 Node<T>에 대해 먼저 알아보겠습니다.

 

내부클래스 Node클래스는 data와 Node타입의 next필드를 갖습니다.

Node클래스는 기본 생성자로 전달받은 data를 필드변수 data에 초기화해줍니다. 

 

Method add(T item)

    public void add(T item) {
        Node<T> node = new Node<T>(item);

        if(rear != null)
            rear.next = node;
        rear = node;
        if(front == null)
            front = rear;
    }

 

add 메소드는 전달받은 item 매개변수로 Node 타입의 변수 node를 생성합니다.

Node 타입 변수 node의 참조변수 data 즉, node.data는 item 값으로 초기화됩니다. node.next는 여전히 null값을 갖습니다.

 

최초 생성 후 값 1을 넘겨받았다고 가정해보겠습니다.

node.data = 1;
node.next = null;

rear에 node를 넣어주고, first에는 rear를 넣어줍니다.

rear.data = 1;
rear.next = null;

front.data = 1;
front.next = null;

첫 번째 add 한 이후로는 계속 rear을 통해서 데이터를 저장합니다.

rear에만 데이터를 저장한다고 해서, front가 고정된 값을 갖는 것이 아닙니다.

front는 rear 필드의 주소를 갖고 있기 때문에, rear를 통해 정보가 이어진다는 점에 주목해야 합니다.

 

다음으로 값 2를 넘겨받았다고 가정해보겠습니다.

rear.next.data = 2;
rear.next.next = null;

rear.data = 2;

이렇게 되면 front는 data는 최초의 1을 갖고 next 변수에 Node 객체가 들어가,

next.data에 2, next.next에 다시 Node객체... 와 같은 형식으로 데이터가 이어지게 됩니다.

 

Method remove()

    public T remove() {
        if(front == null)
            throw  new NoSuchElementException();

        T data = front.data;
        front = front.next;

        if(front == null)
            rear = null;

        return data;
    }

간단히 데이터 스왑을 통하여 삭제 메소드를 구현합니다.

 

Method peek()

    public T peek() {
        if(front == null)
            throw new NoSuchElementException();
        return front.data;
    }

Method isEmpty()

    public boolean isEmpty() {
        return front == null;
    }