LinkedListQueue 구현 with Java

Queue를 구현하는 방식은 크게 두가지로 나뉜다.
앞서 구현했던 Array방식과 오늘 포스팅할 Node방식이다.

Array방식으로 Queue를 구현하면 배열에 쏠림 현상이 발생한다. 그래서 원형으로 배열을 생각해서 순환구조를 이루게 했다.

Node로 구현하면 위의 작업을 안해줘도 된다는 장점이 있다.

1. offer(E data)

비어있을 때는 연산을 다르게 해주어야 한다.
큐는 선입선출이므로 remove와 poll의 연산이 head에서 일어나게 된다.
앞서 구현했던 LinkedList는 모든 곳에서 연산이 일어날 수 있으므로 만약 비어있는 상황에서 요소를 넣을 땐 head와 tail 둘다 node의 주소를 초기화시켰지만, 큐는 head에서만 데이터를 빼내므로 head만 초기화시켜주면 된다.

그리고 비어있지 않은 경우에는 tail을 연결해주면 된다.

2. remove(), poll()

두 함수의 연산은 똑같지만, 예외를 처리하는 방식이 다르다.
poll함수는 만약 큐가 비어있을 경우 null을 리턴하고, remove함수는 예외를 던진다.

3. peek(), element()

두 함수도 연산은 똑같지만, 예외를 처리하는 방식이 다르다.
peek에서는 만약 큐가 비어있을 경우 null을 리턴하고, element에서는 예외를 던진다.

4. isEmpty(), contains(Object value), clear()

isEmpty()함수는 식별자 그대로 비어있는지 확인하고 boolean을 리턴한다.

contains()함수는 매개변수로 받은 value값이 큐에 들어있는지 확인하고 boolean을 리턴하는 함수이다.

clear()함수도 식별자 그대로 큐를 초기화시키는 작업을 해준다.

5. toArray(), toArray(T[] a)

toArray(T[] a) 함수는 매개변수로 받은 배열에 큐의 요소들을 넣는다
만약 매개변수 배열의 사이즈가 큐의 사이즈보다 클 경우엔 큐의 사이즈만큼 배열의 요소들이 덮어씌워진다. 남은 매개변수 배열의 요소들은 그대로 남겨서 리턴해야한다.

반대로 큐의 사이즈가 매개변수 배열의 사이즈보다 클 경우엔 매개변수 배열의 사이즈만큼 큐의 요소들이 덮어씌워진다.
매개변수 배열의 요소들이 모두 큐의 요소들로 바뀌는것이다.

> 전체코드

package Queue;

import java.util.NoSuchElementException;

public class MyLinkedListQueue<E> implements CustomLinkedListQueue<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size;

    MyLinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public E remove() {
        if(isEmpty())
            throw new NoSuchElementException("비어있음.");

        return poll();
    }

    @Override
    public E poll() {
        if(isEmpty())
            return null;

        E returnData = head.data;
        head = head.next;
        size--;
        return returnData;
    }

    @Override
    public E peek() {
        if(isEmpty())
            return null;

        return head.data;
    }

    @Override
    public E element() {
        if(isEmpty())
            throw new NoSuchElementException("비어있음.");

        return peek();
    }

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

    @Override
    public boolean contains(Object value) {
        Node<E> node = head;

        while(node != null){
            if(node.data.equals(value))
                return true;

            node = node.next;
        }
        return false;
    }

    @Override
    public void clear() {
        Node<E> node = head;
        Node<E> nextNode;
        while(node!= null){
            node.data = null;
            nextNode = node.next;
            node.next = null;
            node = nextNode;
        }
        size = 0;
        head = tail = null;
    }


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

        if(isEmpty())
            head = node;

        else{
            tail.next = node;
            tail = node;
        }
        return true;
    }

    @Override
    public Object[] toArray() {
        return toArray(new Object[size]);
    }

    @Override
    public <T> T[] toArray(T[] a) {
        Node<E> node = head;
        int iterLength = a.length;
        if(size < a.length)
            iterLength = size;

        for(int i = 0; i < iterLength; i++){
            a[i] = (T)node.data;
            node = node.next;
        }
        return a;
    }

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

    class Node<E>{
        E data;
        Node<E> next;

        Node(){

        }
        Node(E data){
            this.data = data;
        }
    }


}