Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] Circular Queue(์›ํ˜• ํ)์˜ ์ค‘๊ฐ„ ์ง€์  ์ฐพ๊ธฐ.

๐Ÿ“ฆ[DS,Algorithm] Circular Queue(์›ํ˜• ํ)์˜ ์ค‘๊ฐ„ ์ง€์  ์ฐพ๊ธฐ.
DataStructure Algorithm

1๏ธโƒฃ Circular Queue(์›ํ˜• ํ)์˜ ์ค‘๊ฐ„ ์ง€์  ์ฐพ๊ธฐ.

Java์—์„œ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•œ ์›ํ˜• ํ์—์„œ ์ค‘๊ฐ„ ์ง€์ ์„ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์€ ํ์˜ ์‹œ์ž‘ ์œ„์น˜(โ€˜frontโ€™)์™€ ๋ ์œ„์น˜(โ€˜rearโ€™)๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ค‘๊ฐ„ ์ง€์ ์„ ์ฐพ๋Š” ๊ณต์‹์€ ์›ํ˜• ํ์˜ ํŠน์„ฑ์„ ๊ณ ๋ คํ•˜์—ฌ ์ ์ ˆํžˆ ์กฐ์ •๋˜์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

2๏ธโƒฃ ์ค‘๊ฐ„ ์ง€์ ์„ ์ฐพ๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•.

1๏ธโƒฃ ์ค‘๊ฐ„ ์ง€์  ๊ณ„์‚ฐ ๊ณต์‹.

์ค‘๊ฐ„ ์ง€์ ์„ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์€ ํ์˜ ์‹œ์ž‘์ ๊ณผ ๋์ ์„ ์ด์šฉํ•˜์—ฌ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์›ํ˜• ํ์˜ ํฌ๊ธฐ, ์‹œ์ž‘ ์ธ๋ฑ์Šค(front), ๋ ์ธ๋ฑ์Šค(rear)๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ค‘๊ฐ„ ์ธ๋ฑ์Šค๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด๋•Œ ์ค‘๊ฐ„ ์ง€์ ์„ ๊ณ„์‚ฐํ•˜๋Š” ๊ณต์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

(front + size / 2) % capacity

์—ฌ๊ธฐ์„œ โ€˜sizeโ€™ ๋Š” ํ์— ํ˜„์žฌ ์ €์žฅ๋œ ์š”์†Œ์˜ ์ˆ˜์ด๊ณ , โ€˜capacityโ€™ ๋Š” ํ์˜ ์ „์ฒด ํฌ๊ธฐ์ž…๋‚˜๋‹ค.

3๏ธโƒฃ ์˜ˆ์‹œ

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

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void enqueue(int data) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        queue[rear] = data;
        rear = (rear + 1) % capacity;
        size++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int data = queue[front];
        front = (front + 1) % capacity;
        size--;
        return data;
    }

    public int getMiddle() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int middleIndex = (front + size / 2) % capacity;
        return queue[middleIndex];
    }

    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);
        
        System.out.println("Middle element: " + cq.getMiddle());  // Output: Middle element: 30
        
        cq.dequeue();
        cq.enqueue(60);
        
        System.out.println("Middle element: " + cq.getMiddle());  // Output: Middle element: 40
    }
}

์ด ์ฝ”๋“œ์—์„œ๋Š” โ€˜CircularQueueโ€™ ํด๋ž˜์Šค๋ฅผ ์ •์˜ํ•˜๊ณ , โ€˜enqueueโ€™, โ€˜dequeueโ€™, โ€˜isFullโ€™, โ€˜isEmptyโ€™ ๋ฉ”์„œ๋“œ๋ฅผ ํฌํ•จํ•ฉ๋‹ˆ๋‹ค.

๋˜ํ•œ, ํ์˜ ์ค‘๊ฐ„ ์š”์†Œ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” โ€˜getMiddleโ€™ ๋ฉ”์„œ๋“œ๋ฅผ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.

์ด ๋ฉ”์„œ๋“œ๋Š” ํ˜„์žฌ ํ์˜ ํฌ๊ธฐ์™€ ์‹œ์ž‘ ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ค‘๊ฐ„ ์ธ๋ฑ์Šค๋ฅผ ๊ณ„์‚ฐํ•œ ํ›„ ํ•ด๋‹น ์ธ๋ฑ์Šค์˜ ์š”์†Œ๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.