9. 큐(Queue) - 원형 큐(Circular Queue)

1. 원형 큐(Circular Queue)의 개념

FIFO은 동일하다.

고정된 크기의 배열로 구현한다.

배열의 Index를 원형 큐의 큐 사이즈로 치환하는 연산이 필요하다. (모듈러 연산)

[Index % QueueSize]

front / rear Node로 표현하고, rear가 앞으로 나가면서 데이터를 추가한다.

front가 앞으로 나가면서 데이터를 내보낸다.

isFull() / isEmpty() 동작 조건 확인 필요

 

초기상태

enqueue / dequeue 연산

---

2. 원형 큐(Circular Queue) 구현 (JAVA)

package queue;

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

    private T[] elements;       // 배열 선언
    private int front;          // front, rear 포인터 선언
    private int rear;
    private int maxSize;        // maxsize 변수 선언

    public MyCircularQueue(int size) {      // 생성자 초기화
        this.elements = (T[]) new Object[size + 1]; // 데이터 사이즈 +1 의 더미 포함한 크기의 배열 선언
        this.front = 0;                             
        this.rear = 0;
        this.maxSize = size + 1;
    }

    @Override
    public void offer(T data) {     // rear를 한칸 이동시키고 거기에 데이터를 넣는 동작
        if (isFull()) {             // 큐가 꽉찾다면 예외 발생
            throw new IllegalStateException();
        }

        this.rear = (this.rear + 1) % this.maxSize; // rear 한칸 이동 이 때, 모듈러 연산
        this.elements[this.rear] = data;            // 이동한 rear에 데이터 삽입
    }

    @Override
    public T poll() {              // front를 한칸 옮기고 데이터를 읽어주는 동작 (데이터를 삭제할 필요없음)
        if (isEmpty()) {            // 큐가 비어 있다면 예외 발생
            throw new IllegalStateException();
        }
        this.front = (this.front + 1) % this.maxSize;
        return this.elements[this.front];           // front를 옮기고 별도로 값을 빼지 않아도 
    }                                               // 나중에 rear가 쓰게 될 때 덮어 쓰기 때문에 배열의 데이터를 비워주는 작업을 하지 않아도 된다.

    @Override
    public T peek() {           //front를 옮기지 않고 front +1의 데이터만 반환하는 동작
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        return this.elements[this.front + 1];
    }

    @Override
    public int size() {         // 현재 큐안에 데이터 사이즈를 확인하는 동작
        if (this.front <= this.rear) {      // front의 값이 rear 보다 작으면 rear-front가 데이터 개수
            return this.rear - this.front;
        }
        return this.maxSize - this.front + this.rear;   // front값이 rear보다 크면 
    }

    @Override
    public void clear() {       /// 배열의 값을 삭제하지 않아도 front,rear의 포인터만 0으로 맞춰줘도
        this.front = 0;            // 모두 삭제한 효과와 동일하다. poll에서 데이터 삭제가 필요없는 이유와 동일
        this.rear = 0;
    }

    @Override
    public boolean isEmpty() {              // front 와 rear가 같으면 비어 있는 상태
        return this.front == this.rear;
    }

    private boolean isFull() {              // rear+1 값에 모듈러 연산을 하여 front 값과 같으면 full 
        return (this.rear + 1) % this.maxSize == this.front;
    }
}

---

3. 원형 큐(Circular Queue) 구현 (Python)

class CircularQueue:
    def __init__(self, max_size):
        self.elements = [None] * (max_size + 1)
        self.front = 0
        self.rear = 0
        self.max_size = max_size + 1

    def is_full(self):
        return (self.rear + 1) % self.max_size == self.front

    def is_empty(self):
        return self.front == self.rear

    def clear(self):
        self.front = 0
        self.rear = 0

    def offer(self, data):
        if self.is_full():
            raise RuntimeError("Queue is full")

        self.rear = (self.rear + 1) % self.max_size
        self.elements[self.rear] = data

    def poll(self):
        if self.is_empty():
            raise RuntimeError("Queue is empty")
        self.front = (self.front + 1) % self.max_size
        return self.elements[self.front]

    def size(self):
        if self.front <= self.rear:
            return self.rear - self.front
        return self.max_size - self.front + self.rear


if __name__ == "__main__":
    q = CircularQueue(5)
    for e in range(5):
        print(f"is_full: {q.is_full()}, is_empty: {q.is_empty()}, size: {q.size()}")
        q.offer(e)
        print(f"q.offer({e})")
        print(f"is_full: {q.is_full()}, is_empty: {q.is_empty()}, size: {q.size()}")

    print("--------------------------------------------")
    while q.size() > 0:
        print(f"is_full: {q.is_full()}, is_empty: {q.is_empty()}, size: {q.size()}")
        print(f"q.poll(): {q.poll()}")