Queue 구현 해보기 (자바)

1. 배열로 구현

public class ArrayQueue<T> {
    int front;
    int rear;
    int capacity;
    T[] queue;

    @SuppressWarnings("unchecked")
    ArrayQueue(int capacity){
        this.front = -1;
        this.rear = -1;
        this.capacity = capacity;
        queue = (T[]) new Object[this.capacity];
    }

    public boolean isFull() {
        return (this.rear == this.capacity-1);
    }

    public boolean isEmpty() {
        if(front == rear) {
            front = -1;
            rear = -1;
        }
        return this.front == this.rear;
    }

    public void enqueue(T element) {
        if(isFull()) {
            System.out.println("Queue is Full!");
            return;
        }

        rear = (rear+1) % this.capacity;
        queue[rear] = element;
    }

    public T dequeue() {
        if(isEmpty()) {
            System.out.println("Queue is empty");
            return null;
        }

        front = (front + 1) % this.capacity;
        return queue[front];
    }

    public T peek() {
        if(isEmpty()) {
            System.out.println("Queue is empty");
            return null;
        }

        return queue[front+1];
    }

    public int size() {
        return Math.abs( (rear+1) - (front+1) );
    }

    @SuppressWarnings("unchecked")
    public void clear() {
        if(isEmpty()) {
            System.out.println("Queue is already empty!");
        }
        else {
            front = -1;
            rear = -1;
            queue = (T[]) new Object[this.capacity];
            System.out.println("Queue has cleared!");
        }
    }
}

2. LinkedList 방식 구현

public class QueueNode<T> {
    T data;
    QueueNode<T> next;

    public QueueNode() {
        this.next = null;
    }

    public QueueNode(T data){
        this.data = data;
        next = null;
    }

    public T getData(){
        return this.data;
    }
}

public class ListQueue<T> {
    private QueueNode<T> front;
    private QueueNode<T> rear;

    public ListQueue() {
        this.front = null;
        this.front = null;
    }

    public void enQueue(T item) {
        QueueNode<T> node = new QueueNode<>(item);

        if(isEmpty()){
            front = node;
        }else{
            rear.next = node;
        }
        rear = node;
    }

    public T deQueue() {
        if(isEmpty()){
            throw new ArrayIndexOutOfBoundsException();
        }else{
            T item = front.data;
            front = front.next;
            if(front == null){
                rear = null;
            }
            return item;
        }
    }

    public T peek() {
        if(isEmpty()){
            throw new ArrayIndexOutOfBoundsException();
        }else{
            return front.data;
        }
    }

    public void clear() {
        if(isEmpty()) {
            System.out.println("Queue is already empty!");
        }
        else {
            front = null;
            rear = null;
        }
    }

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

 

배열 구현은 처음 사이즈를 정하면 해당 사이즈를 변경하기 어려움 - > front와 rear가 사이즈의 %로 구해지기 때문

동적할당 및 리사이즈 편의로 LinkedList방식이 좋다고 생각됨