[자료구조] 원형 큐(CircularQueue)

Queue를 구현하는 방법

1. 이전 포스트의 선형 큐 LinkedList를 이용한 구현

2. 배열을 이용한 원형 큐 구현

  ● 배열을 이용한 선형 큐 구현은 너무 비효율적

 

원형 큐 (CircularQueue)

1. 우선 Queue 구현에 사용할 IQueue 인터페이스를 생성

package queue;

public interface IQueue<T> {
    void offer(T data);
    T poll();
    T peek();
    int size();
    void clear();
    boolean isEmpty();
}

 

2. IQueue를 구현할 MyCircularQueue클래스를 생성 후 메서드를 생성

package queue;

public class MyCircularQueue<T> implements IQueue<T> {
    @Override
    public void offer(T data) {
        
    }

    @Override
    public T poll() {
        return null;
    }

    @Override
    public T peek() {
        return null;
    }

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

    @Override
    public void clear() {

    }

    @Override
    public boolean isEmpty() {
        return false;
    }
}

 

3. 멤버변수 설정 및 생성자 생성

private T[] elements;
    private int front;
    private int rear;
    private int maxSize;

    public MyCircularQueue(int size) {
        this.elements = (T[]) new Object[size + 1]; // isEmpty와 isFull 상태를 구분하기 위해서 더미 공간 한칸을 두기 위해 +1을 해줌
        this.front = 0;
        this.rear = 0;
        this.maxSize = size + 1;
    }

 

전체 코드

package queue;

public class MyCircularQueue<T> implements IQueue<T> {

    private T[] elements;
    private int front;
    private int rear;
    private int maxSize;

    public MyCircularQueue(int size) {
        this.elements = (T[]) new Object[size + 1]; // isEmpty와 isFull 상태를 구분하기 위해서 더미 공간 한칸을 두기 위해 +1을 해줌
        this.front = 0;
        this.rear = 0;
        this.maxSize = size + 1;
    }

    @Override
    public void offer(T data) {
        if (this.isFull()) {
            throw  new IllegalStateException();
        }

        this.rear = (this.rear + 1) % this.maxSize;
        this.elements[this.rear] = data;
    }

    @Override
    public T poll() {
        if (this.isEmpty()) {
            throw  new IllegalStateException();
        }

        this.front = (this.front + 1) % this.maxSize;
        return this.elements[this.front];
    }

    @Override
    public T peek() {
        if (this.isEmpty()) {
            throw  new IllegalStateException();
        }

        return this.elements[this.front + 1];
    }

    @Override
    public int size() {
        if (this.front <= this.rear) {
            return this.rear - this.front;
        }

        return this.maxSize - this.front + this.rear;
    }

    @Override
    public void clear() {
        this.front = 0;
        this.rear = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.front == this.rear;
    }

    private boolean isFull() {
        return (this.rear + 1) % this.maxSize == this.front;
    }
}