Queue

Queue?

구현

queue에서 구현해야 하는 기능은 아래의 인터페이스와 같다.

public interface Queue<E> {

    int size();

    boolean isEmpty();

    void enqueue(E e);

    E first();

    E dequeue();

}

queue를 구현하는 방법에는 배열을 사용하는 방법, linked list를 사용하는 방법이 있다.

배열을 사용한 Queue, Array Queue

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

    private E[] data;
    private int f = 0;
    private int sz = 0;

    public ArrayQueue(){
        this(CAPACITY);
    }

    public ArrayQueue(int capacity){
        data = (E[]) new Object[capacity];
    }

    public int size(){
        return (sz == 0);
    }

    public void enqueue(E e) throws IllegalStateException{
        if(sz == data.length)
            throw new IllegalStateException("Queue is full");
        int avail = (f + sz)%data.length;
        data[avail] = e;
        sz++;
    }

    public E first(){
        if(isEmpty())
            return null;
        return data[f];
    }

    public E dequeue(){
        if(isEmpty())
            return null;
        E answer = data[f];
        data[f] = null;
        f = (f+1)%data.length;
        sz--;
        return answer;
    }

}

linked list를 사용한 queue, Linked Queue

public class LinkedQueue<E> implements Queue<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
    public LinkedQueue(){};
    public int size(){
        return list.size();
    }
    public boolean isEmpty(){
        return list.isEmpty();
    }
    public void enqueue(E element){
        list.addLast(element);
    }
    public E first(){
        return list.first();
    }
    public E dequeue(){
        return list.removeFirst();
    }
}

linked list를 구현한 코드는 여기에서 확인할 수 있다.