Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] 큐(Queue)

πŸ“¦[DS,Algorithm] 큐(Queue)
DataStructure Algorithm

1️⃣ 큐(Queue).

큐(Queue)λŠ” μ„ ν˜• 자료ꡬ쑰 쀑 ν•˜λ‚˜λ‘œ, 데이터가 λ“€μ–΄μ˜¨ μˆœμ„œλŒ€λ‘œ μ²˜λ¦¬λ˜λŠ” μ„ μž…μ„ μΆœ(FIFO, First In First Out) ꡬ쑰λ₯Ό κ°€μ§‘λ‹ˆλ‹€.

1️⃣ 큐(Queue).

큐(Queue)λŠ” κ°€μž₯ λ¨Όμ € μ‚½μž…λœ 데이터가 κ°€μž₯ λ¨Όμ € μ œκ±°λ©λ‹ˆλ‹€.

2️⃣ 큐(Queue)의 μ—°μ‚°.

  1. Enqueue : 큐의 λ’€(rear) 끝에 데이터λ₯Ό μΆ”κ°€ν•˜λŠ” μ—°μ‚°μž…λ‹ˆλ‹€.

  1. Dequeue : 큐의 μ•ž(front) λμ—μ„œ 데이터λ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•˜λŠ” μ—°μ‚°μž…λ‹ˆλ‹€.

  2. front λ˜λŠ” Peek : 큐의 μ•ž 끝에 μžˆλŠ” 데이터λ₯Ό μ œκ±°ν•˜μ§€ μ•Šκ³  λ°˜ν™˜ν•˜λŠ” μ—°μ‚°.

  3. isEmpty : 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” μ—°μ‚°.

  4. Size : 큐에 μ €μž₯된 λ°μ΄ν„°μ˜ 개수λ₯Ό λ°˜ν™˜ν•˜λŠ” μ—°μ‚°.

3️⃣ 큐(Queue)의 μ‹€μ œ μ‘μš© 사둀.

  • ν”„λ¦°ν„° μž‘μ—… λŒ€κΈ°μ—΄.
  • CPU μž‘μ—… μŠ€μΌ€μ€„λ§.
  • BFS(Breath-First Search, λ„ˆλΉ„ μš°μ„  탐색)

νλŠ” λ°°μ—΄μ΄λ‚˜ μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν•  . μˆ˜μžˆμŠ΅λ‹ˆλ‹€.

4️⃣ 큐의 μ‹œκ°„ λ³΅μž‘λ„.

큐의 각 연산은 λ‹€μŒκ³Ό 같은 μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§‘λ‹ˆλ‹€.

  1. Enqueue : O(1)
    • 큐의 λ’€ 끝에 데이터λ₯Ό μΆ”κ°€ν•˜λŠ” 연산은 항상 μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  2. Dequeue : O(1)
    • 큐의 μ•ž λμ—μ„œ 데이터λ₯Ό μ œκ±°ν•˜λŠ” 연산도 항상 μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  3. Front λ˜λŠ” Peek : O(1)
    • 큐의 μ•ž 끝에 μžˆλŠ” 데이터λ₯Ό ν™•μΈν•˜λŠ” 연산은 데이터 μ ‘κ·Όλ§Œ ν•„μš”ν•˜κΈ° λ•Œλ¬Έμ— μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  4. isEmpty : O(1)
    • 큐가 λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” 연산은 큐의 크기만 ν™•μΈν•˜λ©΄ λ˜λ―€λ‘œ μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  5. Size : O(1)
    • 큐에 ν˜„μž¬ μ €μž₯된 λ°μ΄ν„°μ˜ 개수λ₯Ό λ°˜ν™˜ν•˜λŠ” 연산도 μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.

5️⃣ 큐의 κ΅¬ν˜„

  • 배열을 μ΄μš©ν•œ νλŠ” κ³ μ •λœ 크기λ₯Ό 가지며, μ›ν˜• 큐(Circular Queue)둜 κ΅¬ν˜„ν•˜μ—¬ λ°°μ—΄μ˜ λμ—μ„œ μ‹œμž‘μœΌλ‘œ μˆœν™˜ν•  수 μžˆλ„λ‘ ν•©λ‹ˆλ‹€.

배열을 μ΄μš©ν•œ 큐 κ΅¬ν˜„.

// ArrayQueue
public class ArrayQueue {
  private int maxSize; // 큐의 μ΅œλŒ€ 크기
  private int front; // 큐의 μ•ž 끝을 κ°€λ¦¬ν‚€λŠ” 인덱슀
  private int rear; // 큐의 λ’€ 끝을 κ°€λ¦¬ν‚€λŠ” 인덱슀
  private int[] queueArray; // 큐λ₯Ό μ €μž₯ν•  λ°°μ—΄
  private int nItems; // 큐에 μ €μž₯된 λ°μ΄ν„°μ˜ 개수

  // μƒμ„±μž
  public ArrayQueue(int size) {
    maxSize = size;
    queueArray = new int[maxSize];
    front = 0;
    rear = -1;
    nItems = 0;
  }

  // 큐의 값을 Enqueueν•˜λŠ” λ©”μ†Œλ“œ.
  public void enqueue(int value) {
    if (isFull()) {
      System.out.println("큐가 가득 μ°ΌμŠ΅λ‹ˆλ‹€.");
      return;
    }

    if (rear == maxSize - 1) {
      rear = -1; // μ›ν˜• 큐 처리
    }

    queueArray[++rear] = value;
    nItems++;
  }

  // νμ—μ„œ 값을 dequeueν•˜λŠ” λ©”μ†Œλ“œ.
  public int dequeue() {
    if (isEmpty()) {
      System.out.println("큐가 λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.");
      return -1; // μ—λŸ¬λ₯Ό λ‚˜νƒ€λ‚΄κΈ° μœ„ν•΄ -1 λ°˜ν™˜.
    }
    int temp = queueArray[front++];

    if (front == maxSize) {
      front = 0; // μ›ν˜• 큐 처리.
    }
    nItems--;
    return temp;
  }

  // 큐의 μ•ž 끝 값을 λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ
  public int peekFront() {
    if (isEmpty()) {
      System.out.println("큐가 λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.");
      return -1; // μ—λŸ¬λ₯Ό λ‚˜νƒ€λ‚΄κΈ° μœ„ν•΄  -1 λ°˜ν™˜.
    }
    return queueArray[front];
  }

  // 큐가 λΉ„μ–΄μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” λ©”μ†Œλ“œ.
  public boolean isEmpty() {
    return (nItems == 0);
  }

  // 큐가 가득 μ°ΌλŠ”μ§€ ν™•μΈν•˜λŠ” λ©”μ†Œλ“œ.
  public boolean isFull() {
    return (nItems == maxSize);
  }

  // 큐의 크기λ₯Ό λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ.
  public int size() {
    return nItems;
  }
}

// Main
public class Main {

  public static void main(String[] args) {
    ArrayQueue queue = new ArrayQueue(5); // 크기가 5인 큐 생성.

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

    System.out.println("=== 좜λ ₯ ===");
    System.out.println();
    System.out.println("Queue의 μ•ž 끝 κ°’: " + queue.peekFront());
    System.out.println("Queue의 크기: " + queue.size());

    // while 문의 쑰건은 queueκ°€ λΉ„μ–΄μžˆμ„ 경우 false μ΄λ―€λ‘œ μˆœνšŒν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
    // κ·ΈλŸ¬λ‚˜ queueκ°€ λΉ„μ–΄μžˆμ§€ μ•Šμ„ 경우 trueκ°€ λ˜λ―€λ‘œ while 블둝을 λ“€μ–΄κ°€ queueκ°€ λΉ„μ–΄μžˆμ„ λ•ŒκΉŒμ§€(!queue.isEmpty()) λ™μž‘ν•©λ‹ˆλ‹€.
    while (!queue.isEmpty()) {
      System.out.println("Dequeue : " + queue.dequeue());
    }

    System.out.println("Queue의 크기 : " + queue.size());

  }
}

/*
=== 좜λ ₯ ===

Queue의 μ•ž 끝 κ°’: 1
Queue의 크기: 5
Dequeue : 1
Dequeue : 2
Dequeue : 3
Dequeue : 4
Dequeue : 5
Queue의 크기 : 0
*/

7️⃣ 큐(Queue) κΈ°λ³Έ ꡬ쑰.

큐(Queue)λŠ” μ„ ν˜• 자료ꡬ쑰 쀑 ν•˜λ‚˜λ‘œ, 데이터λ₯Ό μ„ μž…μ„ μΆœ(FIFO, First In First Out) λ°©μ‹μœΌλ‘œ μ²˜λ¦¬ν•©λ‹ˆλ‹€.

πŸ‘‰ 1️⃣ 큐의 κΈ°λ³Έ ꡬ성 μš”μ†Œ.

  1. Front : 큐의 κ°€μž₯ μ•žμͺ½μ„ κ°€λ¦¬ν‚€λŠ” 포인터 μž…λ‹ˆλ‹€. Dequeue 연산이 λ°œμƒν•  λ•Œ 데이터λ₯Ό μ œκ±°ν•˜λŠ” μœ„μΉ˜λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€.

  2. Rear : 큐의 κ°€μž₯ λ’€μͺ½μ„ μΉ΄λ¦¬ν‚€λŠ” 포인터 μž…λ‹ˆλ‹€. Enqueue 연산이 λ°œμƒν•  λ•Œ 데이터λ₯Ό μΆ”κ°€ν•˜λŠ” μœ„μΉ˜λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€.

  3. Queue Array(λ˜λŠ” List) : 큐의 데이터λ₯Ό μ €μž₯ν•˜λŠ” 자료ꡬ쑰. λ°°μ—΄μ΄λ‚˜ μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

πŸ‘‰ 2️⃣ μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•œ 큐의 κ΅¬ν˜„ 방법.

  • μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•œ νλŠ” λ™μ μœΌλ‘œ 크기λ₯Ό μ‘°μ ˆν•  수 있으며, 각 λ…Έλ“œκ°€ 데이터와 λ‹€μŒ λ…Έλ“œλ₯Ό κ°€λ¦¬ν‚€λŠ” 포인터λ₯Ό ν¬ν•¨ν•©λ‹ˆλ‹€.
// LinkedListQueue
public class LinkedListQueue {
  private class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
    }
  }

  private Node front; // 큐의 μ•žμͺ½ λ…Έλ“œ.
  private Node rear; // 큐의 λ’€μͺ½ λ…Έλ“œ.
  private int size; // 큐에 μ €μž₯된 λ°μ΄ν„°μ˜ 개수.

  // μƒμ„±μž
  public LinkedListQueue() {
    front = null;
    rear = null;
    size = 0;
  }

  // 큐의 값을 μΆ”κ°€ν•˜λŠ” λ©”μ†Œλ“œ.
  public void enqueue(int value) {
    Node newNode = new Node(value);

    if (isEmpty()) {
      front = newNode;
    } else {
      rear.next = newNode;
    }
    rear = newNode;
    size++;
  }

  // νμ—μ„œ 값을 μ œκ±°ν•˜κ³  λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ.
  public int dequeue() {
    if (isEmpty()) {
      System.out.println("큐가 λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.");
      return -1; // μ—λŸ¬λ₯Ό λ‚˜νƒ€λ‚΄κΈ° μœ„ν•΄ -1 λ°˜ν™˜.
    }

    int value = front.data;
    front = front.next;

    if (front == null) {
      rear = null;
    }

    size--;

    return value;
  }

  // 큐의 μ•žμͺ½ 값을 λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ.
  public int peekFront() {
    if (isEmpty()) {
      System.out.println("큐가 λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.");
      return -1; // μ—λŸ¬λ₯Ό λ‚˜νƒ€λ‚΄κΈ° μœ„ν•΄  -1 λ°˜ν™˜.
    }
    return front.data;
  }

  // 큐가 λΉ„μ–΄μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” λ©”μ†Œλ“œ.
  public boolean isEmpty() {
    return (front == null);
  }

  // 큐의 크기λ₯Ό λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ.
  public int size() {
    return size;
  }
}

// Main
public class Main {

  public static void main(String[] args) {
    LinkedListQueue queue = new LinkedListQueue();

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

    System.out.println("=== 좜λ ₯ ===");
    System.out.println();
    System.out.println("Queue의 μ•ž 끝 κ°’ : " + queue.peekFront());
    System.out.println("Queue의 크기 : " + queue.size());

    // while 문의 쑰건은 queueκ°€ λΉ„μ–΄μžˆμ„ 경우 false μ΄λ―€λ‘œ μˆœνšŒν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
    // κ·ΈλŸ¬λ‚˜ queueκ°€ λΉ„μ–΄μžˆμ§€ μ•Šμ„ 경우 trueκ°€ λ˜λ―€λ‘œ while 블둝을 λ“€μ–΄κ°€ queueκ°€ λΉ„μ–΄μžˆμ„ λ•ŒκΉŒμ§€(!queue.isEmpty()) λ™μž‘ν•©λ‹ˆλ‹€.
    while (!queue.isEmpty()) {
      System.out.println("Dequeue : " + queue.dequeue());
    }

    System.out.println("Queue의 크기 : " + queue.size());
  }
}
/*
=== 좜λ ₯ ===

Queue의 μ•ž 끝 κ°’: 1
Queue의 크기: 5
Dequeue : 1
Dequeue : 2
Dequeue : 3
Dequeue : 4
Dequeue : 5
Queue의 크기 : 0
*/

이와 같이 νλŠ” μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

큐λ₯Ό λ°°μ—΄ λ˜λŠ” μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν–ˆμ„ λ•Œ 각각의 μž₯단점.

λ°°μ—΄ 기반 νλŠ” κ°„λ‹¨ν•˜κ³  λΉ λ₯΄μ§€λ§Œ κ³ μ •λœ 크기 문제λ₯Ό ν•΄κ²°ν•΄μ•Ό ν•©λ‹ˆλ‹€.

μ—°κ²° 리슀트 기반 νλŠ” λ™μ μœΌλ‘œ 크기λ₯Ό μ‘°μ ˆν•  수 μžˆμ§€λ§Œ λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ 더 λ§Žμ„ 수 μžˆμŠ΅λ‹ˆλ‹€.