[JAVA] 직접 구현해보는 ArrayQueue 와 LinkedQueue

Queue는 First in First Out의 규칙을 가진 자료구조로서 간단한 예로 식당 예약 줄(먼저 들어온사람이 먼저 먹어야함!)이 있다.  

 

자바의 Collection에 아주 잘 구현이 되어있지만 Queue의 내부 동작을 이해할 겸 Array 및 Node로 직접 구현해보았다. 

 

public interface Queue<E> {
    public boolean isEmpty();

    public void add(E element);

    public E element();

    public E remove();

    public int size();
}

Queue를 구현 하기 전에 필수로 구현해야할 메소드를 interface로 정해놓았다.

 

Array를 통해 구현한 Queue

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

    E[] arr;
    int defaultSize = 100;  // 최초 등록시 max로 사용 할 수 있는 큐의 사이즈를 지정해줌
    int head;
    int tail;

    boolean trace;

    public ArrayQueue() {
        this.arr = (E[]) new Object[defaultSize];
        head = 0;
        tail = 0;
        trace = false;
    }

    public void setTrace(boolean trace) {
        this.trace = trace;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public void add(E element) {
        this.arr[tail++]=element;
        if(this.trace){
            System.out.println(" @add " +this);
        }
    }

    @Override
    public E element() {
        return this.arr[head];
    }

    @Override
    public E remove() {
        E value;
        if (this.isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        value = this.arr[head];
        this.arr[head] = null;
        head++;

        if(this.trace){

            System.out.println("# remove " + this);
        }

        return value;
    }

    @Override
    public int size() {
        System.out.println("tail - head = " + (tail - head));
        return (tail - head) ; //circular queue가 되었을때, (defaultSize + tail - head)%defaultSize 를 return 하면 size 문제는 없음
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = head; i < tail; i++) {
            sb.append(this.arr[i]);
        }
        return sb.toString();
    }
}

제네릭을 사용하므로서 다양한 타입에 대처 할 수 있도록 하였고 boolean trace 변수를 통해 debug를 위한 println 메소드를 사용 여부를 제어하였다. 

 

해당 코드 중 주요하게 보아야할 코드는 add와 remove 이다.

@Override
public void add(E element) {
    this.arr[tail++]=element;
    if(this.trace){
        System.out.println(" @add " +this);
    }
}

add는 요소가 추가 될 때마다 tail을 증가 시켜 배열에 저장하였다. 

( = head 뒤로 추가된 요소들이 붙는다)

 

@Override
public E remove() {
    E value;
    if (this.isEmpty()) {
        throw new IllegalArgumentException("Queue is empty");
    }
    value = this.arr[head];
    this.arr[head] = null;
    head++;

    if(this.trace){

        System.out.println("# remove " + this);
    }

    return value;
}

remove는 head로 표시 되어 있는 요소(=먼저 들어온 요소)를 제거하기 위해 head의 인덱스를 가진 요소를 value라는 변수에 받은 뒤 배열의 해당 인덱스는 null로 초기화 한다. 

그 후 head를 증가시켜 다음으로 들어온 요소를 가리키게 한다. 

---

Node를 통해 구현한 Queue (LinkedQueue)

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

    static class LinkedNode<E> {
        E element;
        LinkedNode next;

        public LinkedNode(E element, LinkedNode next) {
            this.element = element;
            this.next = next;
        }

        public E getElement() {
            return element;
        }

        public LinkedNode getNext() {
            return next;
        }

        public void setNext(LinkedNode next) {
            this.next = next;
        }
    }

    LinkedNode<E> head;
    LinkedNode<E> tail;
    int count;
    boolean trace=false;

    public LinkedQueue() {
        head = null;
        tail = null;
        count = 0;
    }

    public void setTrace(boolean trace) {
        this.trace = trace;
    }

    @Override
    public boolean isEmpty() {
        return this.count==0;
    }

    @Override
    public void add(E element) {
        if(isEmpty()){
            head = new LinkedNode<>(element, null);
            tail = head;
        }else{
            tail.setNext(new LinkedNode(element,null)); //tail은 node가 아니라 표시 지점이다
            tail = tail.getNext();

        }
        if (this.trace) {
            System.out.println(this);
        }
        count++;
    }

    @Override
    public E element() {
        return head.element;
    }

    @Override
    public E remove() {
        if (this.isEmpty()) {
            throw new java.util.NoSuchElementException(); // 돌려줄 데이터가 없는 경우, 예외를 발생시킴
        }
        E value = head.element;
        if (isEmpty()) {
            head = null;
            tail = null;
        }else{
            head.element = null;
            head = head.getNext();
        }

        if (this.trace) {
            System.out.println(this);
        }

        count--;
        return value;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        LinkedNode<E> node = this.head;
        while (node != null) {
            sb.append(node.element + " ");
            node = node.getNext();
        }

        return sb.toString();
    }
}

 

Node는 아래의 코드와 같이 element 와 다음 element의 주소값으로 이루어져 있다. 

(다음 요소의 주소를 알고 있기 때문에 Linked라는 단어를 사용 할 수 있다.)

static class LinkedNode<E> {
    E element;
    LinkedNode next;

    public LinkedNode(E element, LinkedNode next) {
        this.element = element;
        this.next = next;
    }

    public E getElement() {
        return element;
    }

    public LinkedNode getNext() {
        return next;
    }

    public void setNext(LinkedNode next) {
        this.next = next;
    }
}

LinkedNode를 사용하여 Queue를 구현 하기 위해서는 LinkedNode로 구현되어 node를 가리키고 있을 head와 tail이 필요하다. 

LinkedQueue는 head와 tail이 node로 구현이 되었으므로 값(=요소)도 가지고 있고 주소도 가지고 있기에 add와 remove를 구현 하며 헷갈리기도 하였다.

@Override
public void add(E element) {
    if(isEmpty()){
        head = new LinkedNode<>(element, null);
        tail = head;
    }else{
        tail.setNext(new LinkedNode(element,null)); //tail은 node가 아니라 표시 지점이다
        tail = tail.getNext();

    }
    if (this.trace) {
        System.out.println(this);
    }
    count++;
}

해당 LinkedQueue가 비어있다면 head에 새로운 node를 생성하고 tail과 함께 새로 생성한 노드를 가리키고 있는다.

그 이후 추가로 add가 실행되면 null이던 tail의 next node를 새롭게 생성하여 tail을 옮긴다.

 

@Override
public E remove() {
    if (this.isEmpty()) {
        throw new java.util.NoSuchElementException(); // 돌려줄 데이터가 없는 경우, 예외를 발생시킴
    }
    E value = head.element;
    if (isEmpty()) {
        head = null;
        tail = null;
    }else{
        head.element = null;
        head = head.getNext();
    }

    if (this.trace) {
        System.out.println(this);
    }

    count--;
    return value;
}

 remove는 head에 있던 요소를 추출하고 head를 head의 다음 노드로 옮긴다. 

 

---

Array로 구현한 queue는 이해와 구현이 어렵지 않았지만 Node를 통해 구현한 linked queue는 head와 tail이 처음과 끝을 가리키고 있는 화살표 라고 깨우치기 전까지는 이해가 되지 않았다. 

 

너무 자연스럽게 그냥 썼던 queue를 직접 구현해보니 link 의 개념을 확고히 할 수 있어서 좋은 경험이었다.