Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] Circular Queue(์›ํ˜• ํ)๋ฅผ ๋ฐฐ์—ด๋กœ ๊ตฌํ˜„์‹œ rear๋ฅผ -1์œผ๋กœ ์„ค์ •ํ•˜์ง€ ์•Š๋Š” ์ด์œ .

๐Ÿ“ฆ[DS,Algorithm] Circular Queue(์›ํ˜• ํ)๋ฅผ ๋ฐฐ์—ด๋กœ ๊ตฌํ˜„์‹œ rear๋ฅผ -1์œผ๋กœ ์„ค์ •ํ•˜์ง€ ์•Š๋Š” ์ด์œ .
DataStructure Algorithm

1๏ธโƒฃ Circular Queue(์›ํ˜• ํ)๋ฅผ ๋ฐฐ์—ด๋กœ ๊ตฌํ˜„์‹œ rear๋ฅผ -1์œผ๋กœ ์„ค์ •ํ•˜์ง€ ์•Š๋Š” ์ด์œ .

Java์—์„œ ์›ํ˜• ํ๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ โ€˜rearโ€™ ์˜ ์ดˆ๊ธฐ๊ฐ’์„ โ€˜-1โ€™ ๋กœ ์„ค์ •ํ•˜์ง€ ์•Š๋Š” ์ด์œ ๋Š” ์—ฌ๋Ÿฌ ๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

์ฃผ์š” ์ด์œ ๋Š” ํ์˜ ์ธ๋ฑ์‹ฑ์„ ๋‹จ์ˆœํ™”ํ•˜๊ณ , ๋…ผ๋ฆฌ์ ์ธ ํ๋ฆ„์„ ์ผ๊ด€๋˜๊ฒŒ ์œ ์ง€ํ•˜๊ธฐ ์œ„ํ•จ์ž…๋‹ˆ๋‹ค.

๋‹ค์Œ์€ ๊ทธ ์ด์œ ๋ฅผ ์ž์„ธํžˆ ์„ค๋ช…ํ•œ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

1๏ธโƒฃ ์ธ๋ฑ์Šค์˜ ์ผ๊ด€์„ฑ ์œ ์ง€.

  • โ€˜rearโ€™ ๋ฅผ โ€˜0โ€™ ์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•˜๋ฉด ํ์˜ ์ธ๋ฑ์‹ฑ์ด ๋‹จ์ˆœํ•ด์ง‘๋‹ˆ๋‹ค.
    • โ€˜rearโ€™ ์™€ โ€˜frontโ€™ ๋ชจ๋‘ 0์—์„œ ์‹œ์ž‘ํ•˜์—ฌ, ํ์˜ ํฌ๊ธฐ๋ฅผ โ€˜capacityโ€™ ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ธ๋ฑ์Šค๋ฅผ ์ˆœํ™˜์‹œํ‚ต๋‹ˆ๋‹ค.
    • ์ด๋Š” ๋ชจ๋“ˆ๋กœ ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•˜์—ฌ ์ธ๋ฑ์Šค๋ฅผ ๊ด€๋ฆฌํ•˜๋Š” ๋ฐ ์žˆ์–ด ํŽธ๋ฆฌํ•ฉ๋‹ˆ๋‹ค.
  • โ€˜rearโ€™ ๋ฅผ โ€˜-1โ€™ ๋กœ ์„ค์ •ํ•  ๊ฒฝ์šฐ, ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•  ๋•Œ๋งˆ๋‹ค ๋งค๋ฒˆ โ€˜rearโ€™ ๋ฅผ โ€˜0โ€™ ์œผ๋กœ ์กฐ์ •ํ•˜๋Š” ํŠน๋ณ„ํ•œ ์ฒ˜๋ฆฌ๊ฐ€ ํ•„์š”ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
    • ์ด๋Š” ์ฝ”๋“œ์˜ ๋ณต์žก์„ฑ์„ ์ฆ๊ฐ€์‹œํ‚ค๊ณ  ์‹ค์ˆ˜์˜ ๊ฐ€๋Šฅ์„ฑ์„ ๋†’์ž…๋‹ˆ๋‹ค.

2๏ธโƒฃ ์ฝ”๋“œ์˜ ๋‹จ์ˆœํ™”.

  • โ€˜rearโ€™ ๋ฅผ โ€˜0โ€™ ์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•˜๋ฉด ์ดˆ๊ธฐ ์ƒํƒœ์™€ ์š”์†Œ ์ถ”๊ฐ€, ์‚ญ์ œ์‹œ ๋ณ„๋„์˜ ์กฐ๊ฑด ๊ฒ€์‚ฌ๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ์˜ˆ๋ฅผ ๋“ค์–ด โ€˜rearโ€™ ๊ฐ€ โ€˜-1โ€™ ์ธ์ง€ ํ™•์ธํ•˜๋Š” ์ถ”๊ฐ€ ์กฐ๊ฑด๋ฌธ์„ ํ”ผํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • โ€˜0โ€™ ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋ฉด โ€˜enqueueโ€™ ์™€ โ€˜dequeueโ€™ ์—ฐ์‚ฐ์—์„œ โ€˜rearโ€™ ์™€ โ€˜frontโ€™ ์ธ๋ฑ์Šค์˜ ์ฆ๊ฐ€์™€ ๊ฐ์†Œ๊ฐ€ ์ผ๊ด€๋˜๊ฒŒ ์ฒ˜๋ฆฌ๋ฉ๋‹ˆ๋‹ค.

3๏ธโƒฃ ํŽธ๋ฆฌํ•œ ์ดˆ๊ธฐ ์ƒํƒœ ์ฒ˜๋ฆฌ.

  • โ€˜rearโ€™ ๋ฅผ โ€˜0โ€™ ์œผ๋กœ ์„ค์ •ํ•˜๋ฉด ์ดˆ๊ธฐ ์ƒํƒœ์—์„œ ํ๊ฐ€ ๋น„์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๊ฒƒ์ด ๋” ์ง๊ด€์ ์ž…๋‹ˆ๋‹ค.
    • ์˜ˆ๋ฅผ ๋“ค์–ด โ€˜isEmptyโ€™ ๋ฉ”์„œ๋“œ๋Š” ๋‹จ์ˆœํžˆ โ€˜sizeโ€™ ๋ณ€์ˆ˜๋ฅผ ํ™•์ธํ•˜์—ฌ ํ๊ฐ€ ๋น„์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. โ€˜rearโ€™ ๊ฐ€ โ€˜-1โ€™ ์ด๋ฉด ์ถ”๊ฐ€์ ์ธ ์ƒํƒœ ๊ฒ€์‚ฌ๊ฐ€ ํ•„์š”ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

2๏ธโƒฃ ์˜ˆ์‹œ ์ฝ”๋“œ.

๋‹ค์Œ์€ โ€˜rearโ€™ ์˜ ์ดˆ๊ธฐ๊ฐ’์„ โ€˜0โ€™ ์œผ๋กœ ์„ค์ •ํ•˜๋Š” ์›ํ˜• ํ์˜ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.

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;
		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 peek() {
		if (isEmpty()) {
			throw new RuntimeException("Queue is empty");
		}
		return queue[front];
	}

	public int getSize() {
		return size;
	}

	public void displayCircularQueue() {
		if (isEmpty()) {
			throw new RuntimeException("Queue is empty");
		}
		int i = front;
		int count = 0;
		while (count < size) {
			System.out.print("["+ queue[i] + "]");
			i = (i + 1) % capacity;
			count++;
		}
		System.out.println();
	}

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

// Main
public class Main {

	public static void main(String[] args) {
		CircularQueue circularQueue = new CircularQueue(5);
		CircularQueue.enqueue(10);
		CircularQueue.enqueue(20);
		CircularQueue.enqueue(30);
		CircularQueue.enqueue(40);
		CircularQueue.enqueue(50);
		CircularQueue.displayCircularQueue();
		System.out.println();

		System.out.println("Middle element: " + circularQueue.getMiddle());
		circularQueue.displayCircularQueue();
		System.out.println();

		System.out.println("===DEQUEU===");
		System.out.println(circularQueue.dequeue());
		circularQueue.enqueue(60);
		circularQueue.displayCircularQueue();
		System.out.println();

		System.out.println("Middle element: " + circularQueue.getMiddle());
		circularQueue.displayCircularQueue();
	}
}

// === ์ถœ๋ ฅ ===
/*
[10][20][30][40][50]

Middle element: 30
[10][20][30][40][50]

===DEQUEU===
10
[20][30][40][50][60]

Middle element: 40
[20][30][40][50][60]
*/

์œ„ ์ฝ”๋“œ์—์„œ โ€˜rearโ€™ ๋ฅผ 0์œผ๋กœ ์„ค์ •ํ•จ์œผ๋กœ์จ ํ์˜ ์ธ๋ฑ์‹ฑ๊ณผ ์ƒํƒœ ์ฒ˜๋ฆฌ๊ฐ€ ๋‹จ์ˆœํ•ด์ง€๊ณ , ์ดํ•ดํ•˜๊ธฐ ์‰ฌ์›Œ์ง‘๋‹ˆ๋‹ค.
์ด๋Š” ์ฝ”๋“œ์˜ ๊ฐ€๋…์„ฑ๊ณผ ์œ ์ง€๋ณด์ˆ˜์„ฑ์„ ๋†’์ด๋Š” ๋ฐ ๋„์›€์ด ๋ฉ๋‹ˆ๋‹ค.