Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] Circular Queue(μ›ν˜• 큐)λž€?

πŸ“¦[DS,Algorithm] Circular Queue(μ›ν˜• 큐)λž€?
DataStructure Algorithm

1️⃣ Circular Queue(μ›ν˜• 큐)λž€?

μ›ν˜• νλŠ” 큐의 μΌμ’…μœΌλ‘œ, 배열을 μ‚¬μš©ν•˜μ—¬ κ΅¬ν˜„λ˜λ©°, 큐의 λ§ˆμ§€λ§‰ μœ„μΉ˜κ°€ 처음 μœ„μΉ˜μ™€ μ—°κ²°λ˜μ–΄ μ›ν˜• ꡬ쑰λ₯Ό κ°€μ§€λŠ” νμž…λ‹ˆλ‹€.

μ›ν˜• νλŠ” κ³ μ •λœ 크기의 배열을 μ‚¬μš©ν•˜μ—¬ κ΅¬ν˜„λ˜λ―€λ‘œ, 큐의 λ§ˆμ§€λ§‰ μΈλ±μŠ€κ°€ λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν•˜λ©΄ λ‹€μŒ μΈλ±μŠ€κ°€ λ°°μ—΄μ˜ μ‹œμž‘ λΆ€λΆ„μœΌλ‘œ μ΄λ™ν•©λ‹ˆλ‹€.

이λ₯Ό 톡해 λ©”λͺ¨λ¦¬λ₯Ό 효율적으둜 μ‚¬μš©ν•  수 있으며, 큐의 처음과 끝을 κ΄€λ¦¬ν•˜λŠ” 데 도움이 λ©λ‹ˆλ‹€.

2️⃣ μ›ν˜• 큐의 원리.

  1. κ³ μ •λœ 크기 : μ›ν˜• νλŠ” κ³ μ •λœ 크기의 배열을 μ‚¬μš©ν•˜μ—¬ κ΅¬ν˜„λ©λ‹ˆλ‹€. λ”°λΌμ„œ λ°°μ—΄μ˜ 크기λ₯Ό μ΄ˆκ³Όν•˜μ—¬ μš”μ†Œλ₯Ό μΆ”κ°€ν•  수 μ—†μŠ΅λ‹ˆλ‹€.

  2. μ—°κ²°λœ 인덱슀 : 큐의 λ§ˆμ§€λ§‰ μΈλ±μŠ€κ°€ λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν•˜λ©΄, λ‹€μŒ μΈλ±μŠ€λŠ” λ°°μ—΄μ˜ 처음 λΆ€λΆ„μœΌλ‘œ μ΄λ™ν•©λ‹ˆλ‹€.

  3. 두 개의 포인터 : μ›ν˜• νλŠ” 두 개의 포인터λ₯Ό μ‚¬μš©ν•˜μ—¬ κ΅¬ν˜„λ©λ‹ˆλ‹€.
    • β€˜front’ : 큐의 첫 번째 μš”μ†Œλ₯Ό κ°€λ¦¬ν‚΅λ‹ˆλ‹€.
    • β€˜rear’ : 큐의 λ§ˆμ§€λ§‰ μš”μ†Œλ₯Ό κ°€λ¦¬ν‚΅λ‹ˆλ‹€.
  4. λΉ„μ–΄ μžˆλŠ” μƒνƒœμ™€ 가득 μ°¬ μƒνƒœ : 큐가 λΉ„μ–΄ μžˆλŠ” μƒνƒœμ™€ 가득 μ°¬ μƒνƒœλ₯Ό ꡬ별해야 ν•©λ‹ˆλ‹€. 이λ₯Ό μœ„ν•΄ 좔가적인 λ³€μˆ˜λ₯Ό μ‚¬μš©ν•˜κ±°λ‚˜ ν¬μΈν„°μ˜ μœ„μΉ˜λ₯Ό λΉ„κ΅ν•˜μ—¬ μƒνƒœλ₯Ό ν™•μΈν•©λ‹ˆλ‹€.

3️⃣ μ›ν˜• 큐의 μ£Όμš” μ—°μ‚°.

  1. μ΄ˆκΈ°ν™” : 큐의 크기λ₯Ό μ„€μ •ν•˜κ³ , β€˜front’ 와 β€˜rear’ 포인터λ₯Ό μ΄ˆκΈ°ν™”ν•©λ‹ˆλ‹€.

  2. isEmpty() : 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.

  3. isFull() : 큐가 가득 μ°ΌλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.

  4. enqueue() : 큐에 μš”μ†Œλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€. β€˜rear’ 포인터λ₯Ό μ—…λ°μ΄νŠΈν•©λ‹ˆλ‹€.

  5. dequeue() : νμ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€. β€˜front’ 포인터λ₯Ό μ—…λ°μ΄νŠΈν•©λ‹ˆλ‹€.

  6. peek() : 큐의 첫 번째 μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

4️⃣ μ›ν˜• 큐의 예제 κ΅¬ν˜„.

public class CircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    // μƒμ„±μž
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    // 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ 확인
    public boolean isEmpty() {
        return size == 0;
    }

    // 큐가 가득 μ°ΌλŠ”μ§€ 확인
    public boolean isFull() {
        return size == capacity;
    }

    // 큐에 μš”μ†Œ μΆ”κ°€
    public void enqueue(int element) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        rear = (rear + 1) % capacity;
        queue[rear] = element;
        size++;
    }

    // νμ—μ„œ μš”μ†Œ 제거
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        int element = queue[front];
        front = (front + 1) % capacity;
        size--;
        return element;
    }

    // 큐의 첫 번째 μš”μ†Œ 확인
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return queue[front];
    }

    // 큐의 크기 λ°˜ν™˜
    public int getSize() {
        return size;
    }

    // 큐의 λͺ¨λ“  μš”μ†Œ 좜λ ₯
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        int i = front;
        int count = 0;
        while (count < size) {
            System.out.print(queue[i] + " ");
            i = (i + 1) % capacity;
            count++;
        }
        System.out.println();
    }

    // 메인 λ©”μ„œλ“œ (ν…ŒμŠ€νŠΈμš©)
    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5);

        cq.enqueue(10);
        cq.enqueue(20);
        cq.enqueue(30);
        cq.enqueue(40);
        cq.enqueue(50);

        cq.display(); // 좜λ ₯: 10 20 30 40 50

        System.out.println("Dequeued: " + cq.dequeue()); // 좜λ ₯: Dequeued: 10
        System.out.println("Dequeued: " + cq.dequeue()); // 좜λ ₯: Dequeued: 20

        cq.display(); // 좜λ ₯: 30 40 50

        cq.enqueue(60);
        cq.enqueue(70);

        cq.display(); // 좜λ ₯: 30 40 50 60 70

        System.out.println("Front element: " + cq.peek()); // 좜λ ₯: Front element: 30
    }
}

πŸ™‹β€β™‚οΈ μ„€λͺ….

  1. 큐 μ΄ˆκΈ°ν™”:
    • β€˜capacity’ : 큐의 μ΅œλŒ€ ν¬κΈ°μž…λ‹ˆλ‹€.
    • β€˜queue’ : 큐λ₯Ό μ €μž₯ν•  λ°°μ—΄μž…λ‹ˆλ‹€.
    • β€˜front’ : 큐의 첫 번째 μš”μ†Œλ₯Ό κ°€λ¦¬ν‚€λŠ” μΈλ±μŠ€μž…λ‹ˆλ‹€.
    • β€˜rear’ : 큐의 λ§ˆμ§€λ§‰ μš”μ†Œλ₯Ό κ°€λ¦¬ν‚€λŠ” μΈλ±μŠ€μž…λ‹ˆλ‹€.
    • β€˜size’ : 큐에 μžˆλŠ” μš”μ†Œμ˜ κ°œμˆ˜μž…λ‹ˆλ‹€.
  2. λ©”μ„œλ“œ:
    • β€˜isEmpty()’ : 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.
    • β€˜isFull()’ : 큐가 가득 μ°ΌλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.
    • β€˜enqueue(int element)’ : 큐에 μš”μ†Œλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€.
    • β€˜dequeue()’ : νμ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
    • β€˜peek()’ : 큐의 첫 번째 μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
    • β€˜getSize()’ : 큐에 μžˆλŠ” μš”μ†Œμ˜ 개수λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
    • β€˜display()’ : 큐의 λͺ¨λ“  μš”μ†Œλ₯Ό 좜λ ₯ν•©λ‹ˆλ‹€.

5️⃣ κ²°λ‘ .

μ›ν˜• νλŠ” 배열을 효율적으둜 μ‚¬μš©ν•˜μ—¬ 큐의 크기λ₯Ό κ³ μ •ν•˜κ³ , 처음과 끝이 μ—°κ²°λœ ν˜•νƒœλ‘œ 큐λ₯Ό κ΄€λ¦¬ν•˜λŠ” μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.

이λ₯Ό 톡해 큐의 곡간을 μ΅œλŒ€ν•œ ν™œμš©ν•˜κ³ , 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ 가득 μ°ΌλŠ”μ§€λ₯Ό μ‰½κ²Œ 확인할 수 μžˆμŠ΅λ‹ˆλ‹€.

πŸ€” κΆκΈˆν–ˆλ˜ λΆ€λΆ„.

rear = (rear + 1) % capacity;

1️⃣ 이 μ½”λ“œμ—μ„œ % capacity λ₯Ό ν•˜λŠ” μ΄μœ λŠ” λ¬΄μ—‡μΌκΉŒ?

μ›ν˜• νμ—μ„œ β€˜rear’ 포인터λ₯Ό μ—…λ°μ΄νŠΈ ν•  λ•Œ % capacity λ₯Ό μ‚¬μš©ν•˜λŠ” μ΄μœ λŠ” 큐가 λ§ˆμ§€λ§‰ μΈλ±μŠ€μ— λ„λ‹¬ν•œ ν›„, λ‹€μ‹œ 처음 인덱슀둜 λŒμ•„κ°€λ„λ‘ ν•˜κΈ° μœ„ν•΄μ„œμž…λ‹ˆλ‹€.

이λ₯Ό 톡해 큐가 μ›ν˜•μœΌλ‘œ λ™μž‘ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

ꡬ체적으둜 λ§ν•˜λ©΄, 큐의 크기λ₯Ό κ³ μ •λœ 크기의 λ°°μ—΄λ‘œ κ΅¬ν˜„ν•  λ•Œ, λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν–ˆμ„ λ•Œ λ‹€μ‹œ 처음으둜 λŒμ•„κ°€λŠ” κΈ°λŠ₯을 μ œκ³΅ν•©λ‹ˆλ‹€.

2️⃣ % μ—°μ‚°μžμ˜ μ—­ν• .

λ°°μ—΄μ˜ μΈλ±μŠ€λŠ” 0λΆ€ν„° μ‹œμž‘ν•˜μ—¬ λ°°μ—΄μ˜ 크기보닀 1 μž‘μ€ κ°’κΉŒμ§€μž…λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, λ°°μ—΄μ˜ 크기가 5라면 μΈλ±μŠ€λŠ” 0λΆ€ν„° 4κΉŒμ§€μž…λ‹ˆλ‹€.

μ›ν˜• νμ—μ„œ μƒˆλ‘œμš΄ μš”μ†Œλ₯Ό μΆ”κ°€ν•  λ•Œλ§ˆλ‹€ β€˜rear’ 포인터λ₯Ό μ¦κ°€μ‹œν‚€λŠ”λ°, 이 포인터가 λ°°μ—΄μ˜ 끝을 λ„˜μ–΄κ°€μ§€ μ•Šλ„λ‘ ν•΄μ•Ό ν•©λ‹ˆλ‹€.

이λ₯Ό μœ„ν•΄ % capacity 연산을 μ‚¬μš©ν•©λ‹ˆλ‹€.

  • rear = (rear + 1) % capacity;

이 연산은 β€˜rear’ 포인터λ₯Ό 1μ”© μ¦κ°€μ‹œν‚€λ‹€κ°€, λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν•˜λ©΄ λ‹€μ‹œ 0으둜 λŒμ•„κ°€κ²Œ ν•©λ‹ˆλ‹€.

즉, λ°°μ—΄μ˜ μΈλ±μŠ€κ°€ λ°°μ—΄μ˜ 크기λ₯Ό λ„˜μ–΄κ°€λ©΄, λ‹€μ‹œ 처음 인덱슀(0)둜 μˆœν™˜λ˜κ²Œ ν•©λ‹ˆλ‹€.

πŸ‘‰ 예제.

λ°°μ—΄μ˜ 크기가 5인 μ›ν˜• 큐λ₯Ό μƒκ°ν•΄λ΄…μ‹œλ‹€.

  • 초기 μƒνƒœ: β€˜rear = -1’
  • μš”μ†Œ μΆ”κ°€ μ‹œ, β€˜rear’ ν¬μΈν„°μ˜ λ³€ν™”λ₯Ό 관찰해보면
    • 첫 번째 μΆ”κ°€: β€˜rear = (rear + 1) % 5 -> rear = 0’
    • 두 번째 μΆ”κ°€: β€˜rear = (rear + 1) % 5 -> rear = 1’
    • μ„Έ 번째 μΆ”κ°€: β€˜rear = (rear + 1) % 5 -> rear = 2’
    • λ„€ 번째 μΆ”κ°€: β€˜rear = (rear + 1) % 5 -> rear = 3’
    • λ‹€μ„― 번째 μΆ”κ°€: β€˜rear = (rear + 1) % 5 -> rear = 4’
    • μ—¬μ„― 번째 μΆ”κ°€: β€˜rear = (rear + 1) % 5 -> rear = 0’ (λ‹€μ‹œ 처음으둜 λŒμ•„κ°)

μ΄λ ‡κ²Œ β€˜rear’ 포인터가 λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν•˜λ©΄ λ‹€μ‹œ λ°°μ—΄μ˜ μ‹œμž‘ λΆ€λΆ„μœΌλ‘œ μˆœν™˜λ˜λ―€λ‘œ, 배열을 효율적으둜 μ‚¬μš©ν•  수 있게 λ©λ‹ˆλ‹€.

πŸ’» μ½”λ“œ 예제.

μœ„ κ°œλ…μ„ μ΄μš©ν•œ μ›ν˜• 큐의 β€˜enqueue’ λ©”μ„œλ“œ κ΅¬ν˜„

public void enqueue(int element) {
    if (isFull()) {
        System.out.println("Queue is full");
        return;
    }
    rear = (rear + 1) % capacity; // rear 포인터λ₯Ό μ¦κ°€μ‹œν‚€κ³ , λ°°μ—΄μ˜ 처음으둜 μˆœν™˜μ‹œν‚΄.
    queue[rear] = element;
    size++;
}

6️⃣ 정리.

μ›ν˜• νμ—μ„œ ’% capacity’ 연산은 β€˜rear’ 포인터와 β€˜front’ 포인터가 λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν–ˆμ„ λ•Œ, λ‹€μ‹œ λ°°μ—΄μ˜ μ‹œμž‘ λΆ€λΆ„μœΌλ‘œ λŒμ•„κ°€κΈ° μœ„ν•΄ μ‚¬μš©λ©λ‹ˆλ‹€.

이λ₯Ό 톡해 λ°°μ—΄μ˜ κ³ μ •λœ 크기λ₯Ό 효율적으둜 ν™œμš©ν•˜λ©°, μ›ν˜• 큐의 νŠΉμ„±μ„ μœ μ§€ν•  수 μžˆμŠ΅λ‹ˆλ‹€.