Java 원형큐 구현

안녕들 하시죠!

이번시간에는 Java 언어를 이용하여 원형큐를 구현해보겠습니다.

아래에 인터페이스에 있는 메소드를 오버라이딩하여 사용해보겠습니다.

 

interface QueueInterface {
 
    public void newQueue(int Qsize); // 새로운 큐를 생성하는 메소드
 
    public abstract boolean isFull(); // 큐가 포화상태인지 검사하는 메소드
 
    public abstract boolean isEmpty(); // 큐가 비어있는지 검사하는 메소드
 
    public abstract boolean enqueue(Object ob); // 큐에 데이터를 삽입하는 메소드
 
    public abstract Object dequeue(); // 큐에 들어있는 데이터를 삭제하는 메소드
 
    public abstract Object peek(); // 다음번 dequeue 될 데이터 출력하는 메소드
}

 

- 변수 선언과 public void newQueue

 

private int front; // 출력 포인터
private int rear; // 삽입 포인터
private int Qsize; // 전체 큐의 사이즈
private char[] QArray; // Qsize를 이용하여 전체 배열 생성
 
@Override
public void newQueue(int Qsize) { // 큐를 생성하는 메소드
    front = 0; //
    rear = 0; // 맨처음 출력,삽입 포인터가 큐의 0번지를 가리키고 있다.
    this.Qsize = Qsize;
    QArray = new char[Qsize];
    System.out.println("사이즈는 : " + Qsize);
}

 

- public boolean isFull(), public boolean isEmpty()

 

@Override
public boolean isFull() { // 큐가 포화 상태인지 검사하는 메소드
    if (((rear + 1) % this.Qsize) == front) { // 원형큐의 핵심 코드, 아래에서 그림과 함께 설명.
        return true;
    } else {
        return false;
    }
}
@Override
public boolean isEmpty() { // 큐가 이어있는지 검사하는 메소드.
    return rear == front; // rear와 front는 데이터가 삽입되기 전에만 같은 위치를 가리키기 때문에 큐가 비어있는 상태검사에 사용.
}

 

 

 

- public boolean enqueue

 

@Override
public boolean enqueue(Object ob) {
    if (isFull()) { // 큐가 가득차 있지 않다면 삽입.
        System.out.println("큐가 꽉 차 있습니다.");
        return false;
    } else {
        rear = (++rear) % this.Qsize; // 아래 그림에서 설명
        QArray[rear] = (char) ob; // 삽입포인터 rear가 가리키는 공간에 데이터 삽입.
        System.out.println(ob + "를 " + rear + "번째에" + " 삽입");
        return true;
    }
}

 

- 원형큐의 원리

맨처음 삽입포인터(rear) 와 출력포인터(front)는 [0]번지를 가리키고 있습니다. ( 1번그림 )

맨처음 데이터가 삽입되게되면 삽입포인터(rear)가 [1]번지로 이동하게되고 출력포인터(front)는 [0]번지를 그대로 가리키고있습니다. ( 2번그림 )

 

1번, 2번 그림

 

데이터가 계속 삽입되며 [3]번지까지 차게되면 포화상태가 됩니다. ( 4번그림 )

 

3번, 4번 그림

이렇게 포화가 된 상태에서 dequeue() 메소드를 이용해 데이터를 삭제하려고 한다면,

출력포인터(front) 가 [1]번지로 이동하고 데이터를 삭제하게 됩니다. ( 5번그림 )

 

5번, 6번 그림

 

이제 [1]번지의 데이터가 삭제되었으니 데이터를 추가할 공간이 생겼습니다.

enqueue() 메소드를 이용해 데이터를 삽입하려고 한다면,

삽입포인터(rear) 가 [0]번지로 이동하고 데이터를 삽입하여 다시 포화상태가 됩니다. ( 6번그림 )

 

* 핵심코드

 

6번그림에서 [3]번지를 가리키고있던 삽입포인터(rear) 가 [0]번지로 이동하려면,

 

rear = (++rear) % this.Qsize;

 

이라는 코드가 필요하게됩니다.

[3]번지에 데이터를 삽입한 후 (++rear) 연산을 통해서 rear는 4가 되어있습니다.

4를 나머지연산(%)를 통해서 Qsize인 4로 나누게 되면 0이 나오기 때문에 다시 [0]번지로 이동하여 데이터를 삽입할 수 있습니다.

 

- public Object dequeue()

 

@Override
public Object dequeue() {
    if (isEmpty()) {
        System.out.println("큐가 비어있습니다.");
        return -1;
    } else {
        front = (++front) % this.Qsize;
        System.out.println(QArray[(front) % Qsize] + "를 삭제");
        return QArray[front];
    }
}
 

 

- public Object peek() 

 

@Override
public Object peek() {
    System.out.println(QArray[(front + 1) % this.Qsize]);
    return QArray[(front + 1) % this.Qsize];
}

 

원형큐 전체코드

interface QueueInterface {
    
    public void newQueue(int Qsize); // 새로운 큐를 생성하는 메소드
 
    public abstract boolean isFull(); // 큐가 포화상태인지 검사하는 메소드
 
    public abstract boolean isEmpty(); // 큐가 비어있는지 검사하는 메소드
 
    public abstract boolean enqueue(Object ob); // 큐에 데이터를 삽입하는 메소드
 
    public abstract Object dequeue(); // 큐에 들어있는 데이터를 삭제하는 메소드
 
    public abstract Object peek(); // 다음번 dequeue 될 데이터 출력하는 메소드
    
}
 
public class MyQueue implements QueueInterface {
 
    private int front; // 출력 포인터
    private int rear; // 삽입 포인터
    private int Qsize; // 전체 큐의 사이즈
    private char[] QArray; // Qsize를 이용하여 전체 배열 생성
 
    @Override
    public void newQueue(int Qsize) { // 큐를 생성하는 메소드
        front = 0; //
        rear = 0; // 맨처음 출력,삽입 포인터가 큐의 0번지를 가리키고 있다.
        this.Qsize = Qsize;
        QArray = new char[Qsize];
        System.out.println("사이즈는 : " + Qsize);
    }
 
    @Override
    public boolean isFull() { // 큐가 포화 상태인지 검사하는 메소드
        if (((rear + 1) % this.Qsize) == front) { // 원형큐의 핵심 코드, 아래에서 그림과 함께 설명.
            return true;
        } else {
            return false;
        }
    }
 
    @Override
    public boolean isEmpty() { // 큐가 이어있는지 검사하는 메소드.
        return rear == front; // rear와 front는 데이터가 삽입되기 전에만 같은 위치를 가리키기 때문에 큐가 비어있는 상태검사에 사용.
    }
 
    @Override
    public boolean enqueue(Object ob) {
        if (isFull()) { // 큐가 가득차 있지 않다면 삽입.
            System.out.println("큐가 꽉 차 있습니다.");
            return false;
        } else {
            rear = (++rear) % this.Qsize; // 아래 그림에서 설명
            QArray[rear] = (char) ob; // 삽입포인터 rear가 가리키는 공간에 데이터 삽입.
            System.out.println(ob + "를 " + rear + "번째에" + " 삽입");
            return true;
        }
    }
 
    @Override
    public Object dequeue() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다.");
            return -1;
        } else {
            front = (++front) % this.Qsize;
            System.out.println(QArray[(front) % Qsize] + "를 삭제");
            return QArray[front];
        }
    }
 
    @Override
    public Object peek() {
        System.out.println(QArray[(front + 1) % this.Qsize]);
        return QArray[(front + 1) % this.Qsize];
    }
}

 

오늘은 여기까지입니다 갑사합니다 !