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

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

1️⃣ μ›ν˜• 큐(Circular Queue).

μ›ν˜• 큐(Circular Queue)λž€, β€œκ³ μ •λœ 크기의 배열” 을 μ‚¬μš©ν•˜μ—¬ κ΅¬ν˜„λœ νλ‘œμ„œ, λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν•˜λ©΄ λ‹€μ‹œ λ°°μ—΄μ˜ μ‹œμž‘ λΆ€λΆ„μœΌλ‘œ λŒμ•„κ°€λŠ” ꡬ쑰λ₯Ό 가진 νμž…λ‹ˆλ‹€.

이λ₯Ό 톡해 큐가 꽉 μ°¨ μžˆλŠ”μ§€, λΉ„μ–΄ μžˆλŠ”μ§€λ₯Ό 효율적으둜 관리할 수 있으며, 곡간을 효율적으둜 μ‚¬μš©ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

1️⃣ μ›ν˜• 큐의 νŠΉμ§•.

    1. μ„ μž…μ„ μΆœ(FIFO, First In First Out) : 일반적인 큐와 λ§ˆμ°¬κ°€μ§€λ‘œ λ¨Όμ € λ“€μ–΄κ°„ 데이터가 λ¨Όμ € λ‚˜μ˜€λŠ” κ΅¬μ‘°μž…λ‹ˆλ‹€.
    1. μˆœν™˜ ꡬ쑰 : λ°°μ—΄μ˜ 끝에 λ„λ‹¬ν•˜λ©΄ λ‹€μ‹œ 처음으둜 λŒμ•„κ°‘λ‹ˆλ‹€. 이λ₯Ό 톡해 κ³ μ •λœ 크기의 배열을 μ΄μš©ν•˜μ—¬ λ©”λͺ¨λ¦¬λ₯Ό 효율적으둜 μ‚¬μš©ν•©λ‹ˆλ‹€.
  • 3 κ³ μ • 크기 : 큐의 μ΅œλŒ€ ν¬κΈ°λŠ” λ°°μ—΄μ˜ 크기둜 μ œν•œ λ©λ‹ˆλ‹€.

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

    1. Enqueue : 큐의 λ’€μͺ½(rear)에 μƒˆλ‘œμš΄ μš”μ†Œλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€.
    1. Dequeue : 큐의 μ•žμͺ½(front)μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
    1. Peek : 큐의 μ•žμͺ½(front) μš”μ†Œλ₯Ό μ œκ±°ν•˜μ§€ μ•Šκ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
    1. IsEmpty : 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€λ₯Ό ν™•μΈν•©λ‹ˆλ‹€.
    1. IsFull : 큐가 가득 μ°ΌλŠ”μ§€ μ—¬λΆ€λ₯Ό ν™•μΈν•©λ‹ˆλ‹€.

3️⃣ μ›ν˜• 큐의 μž₯점.

  • λ©”λͺ¨λ¦¬ νš¨μœ¨μ„± : κ³ μ •λœ 크기의 배열을 μ‚¬μš©ν•˜μ—¬ λ©”λͺ¨λ¦¬λ₯Ό 효율적으둜 μ‚¬μš©ν•©λ‹ˆλ‹€.
  • μ—°μ†λœ λ©”λͺ¨λ¦¬ μ‚¬μš© : 배열을 μ‚¬μš©ν•˜μ—¬ λ©”λͺ¨λ¦¬λ₯Ό μ—°μ†μ μœΌλ‘œ μ‚¬μš©ν•˜λ―€λ‘œ μΊμ‹œ νš¨μœ¨μ„±μ΄ λ†’μŠ΅λ‹ˆλ‹€.

4️⃣ μ›ν˜• 큐의 단점.

  • κ³ μ • 크기 μ œν•œ : 크기가 κ³ μ •λ˜μ–΄ μžˆμœΌλ―€λ‘œ, 큐가 가득 μ°¬ 경우 더 이상 μš”μ†Œλ₯Ό μΆ”κ°€ν•  수 μ—†μŠ΅λ‹ˆλ‹€. 이 문제λ₯Ό ν•΄κ²°ν•˜λ €λ©΄ λ™μ μœΌλ‘œ 크기λ₯Ό μ‘°μ ˆν•  수 μžˆλŠ” 방법을 μΆ”κ°€λ‘œ κ΅¬ν˜„ν•΄μ•Ό ν•©λ‹ˆλ‹€.

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

// CircularQueue
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 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 boolean isEmpty() {
    return size == 0;
  }

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

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

// Main
public class Main {

  public static void main(String[] args) {
    CircularQueue circularQueue = new CircularQueue(5);

    circularQueue.enqueue(1);
    circularQueue.enqueue(2);
    circularQueue.enqueue(3);
    circularQueue.enqueue(4);
    circularQueue.enqueue(5);

    System.out.println("Dequeue: " + circularQueue.dequeue());
    System.out.println("Dequeue: " + circularQueue.dequeue());

    circularQueue.enqueue(6);
    circularQueue.enqueue(7);

    System.out.println("Peek: " + circularQueue.peek());

    while (!circularQueue.isEmpty()) {
      System.out.println("Dequeue: " + circularQueue.dequeue());
    }
  }
}

// 좜λ ₯
/*
Dequeue: 1
Dequeue: 2
Peek: 3
Dequeue: 3
Dequeue: 4
Dequeue: 5
Dequeue: 6
Dequeue: 7
 */

μ½”λ“œ μ„€λͺ….

    1. CircularQueue 클래슀:
      • β€˜queue’ : 큐λ₯Ό μ €μž₯ν•˜λŠ” λ°°μ—΄.
      • β€˜front’ : 큐의 μ•žμͺ½ 인덱슀.
      • β€˜rear’ : 큐의 λ’€μͺ½ 인덱슀.
      • β€˜size’ : ν˜„μž¬ 큐에 μ €μž₯된 μš”μ†Œμ˜ 개수.
      • β€˜capacity’ : 큐의 μ΅œλŒ€ 크기.
    1. λ©”μ„œλ“œ:
      • β€˜enqueue(int element)’ : 큐가 가득 차지 μ•Šμ•˜μœΌλ©΄ μš”μ†Œλ₯Ό 큐에 μΆ”κ°€ν•©λ‹ˆλ‹€.
      • β€˜dequeue()’ : 큐가 λΉ„μ–΄ μžˆμ§€ μ•ŠμœΌλ©΄ 큐의 μ•žμͺ½ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
      • β€˜peek()’ : 큐의 μ•žμͺ½ μš”μ†Œλ₯Ό μ œκ±°ν•˜μ§€ μ•Šκ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
      • β€˜isEmpty()’ : 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.
      • β€˜isFull()’ : 큐가 가득 μ°ΌλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.
      • β€˜getSize()’ : 큐의 ν˜„μž¬ 크기λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
    1. main λ©”μ„œλ“œ:
      • μ›ν˜• 큐λ₯Ό μƒμ„±ν•˜κ³  μ—¬λŸ¬ 연산을 μˆ˜ν–‰ν•˜μ—¬ 큐의 λ™μž‘μ„ ν…ŒμŠ€νŠΈν•©λ‹ˆλ‹€.