devkobe24.com

homepage

Contact

Copyright Β© 2024 | Yankos
Contents

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

πŸ“¦[DS,Algorithm] 큐(Queue)
Backend 2024-05-23 -
DataStructure Algorithm

1️⃣ 큐(Queue)

큐(Queue)λŠ” 컴퓨터 κ³Όν•™μ—μ„œ ν”νžˆ μ‚¬μš©λ˜λŠ” 자료ꡬ쑰 쀑 ν•˜λ‚˜λ‘œ, μ„ μž…μ„ μΆœ(FIFO, First In First Out) λ°©μ‹μœΌλ‘œ λ™μž‘ν•©λ‹ˆλ‹€.

즉, 큐에 λ¨Όμ € λ“€μ–΄κ°„ 데이터가 λ¨Όμ € λ‚˜μ˜€λŠ” κ΅¬μ‘°μž…λ‹ˆλ‹€.

큐의 μ£Όμš”μ—°μ‚°.

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

큐가 μœ μš©ν•˜κ²Œ μ‚¬μš©λ˜λŠ” 상황.

  • ν”„λ¦°ν„° λŒ€κΈ°μ—΄ : 인쇄 μž‘μ—…μ„ μˆœμ„œλŒ€λ‘œ μ²˜λ¦¬ν•©λ‹ˆλ‹€.
  • ν”„λ‘œμ„ΈμŠ€ μŠ€μΌ€μ€„λ§ : 운영 μ²΄μ œμ—μ„œ ν”„λ‘œμ„ΈμŠ€λ“€μ΄ CPU μ‹œκ°„μ„ μ–»κΈ° μœ„ν•΄ λŒ€κΈ°ν•˜λŠ” μˆœμ„œλ₯Ό μœ μ§€ν•©λ‹ˆλ‹€.
  • λ„ˆλΉ„ μš°μ„  탐색(BFS) : κ·Έλž˜ν”„ 탐색 μ•Œκ³ λ¦¬μ¦˜μ—μ„œ 각 λ…Έλ“œλ₯Ό λ°©λ¬Έν•  μˆœμ„œλ₯Ό μœ μ§€ν•©λ‹ˆλ‹€.

큐의 κ΅¬ν˜„.

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

배열을 μ‚¬μš©ν•œ 큐 κ΅¬ν˜„ 예제

public class QueueArray {
  private int[] elements;
  private int front;
  private int rear;
  private int size;
  private int capacity;

  public QueueArray(int capacity) {
    this.capacity = capacity;
    elements = new int[capacity];
    front = 0;
    rear = -1;
    size = 0;
  }

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

    rear = (rear + 1) % capacity;
    elements[rear] = element;
    size++;
  }

  // νμ—μ„œ μš”μ†Œ 제거 및 λ°˜ν™˜
  public int dequeue() {
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return -1;
    }

    int element = elements[front];
    front = (front + 1) % capacity;
    size--;
    return element;
  }

  // 큐의 μ•žμͺ½ μš”μ†Œ λ°˜ν™˜
  public int peek() {
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return -1;
    }
    return  elements[front];
  }

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

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

// Main 클래슀
public class Main {

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

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

    System.out.println("Front element: " + queue.peek());
    System.out.println("Dequeue element: " + queue.dequeue());
    System.out.println("Front element after dequeue: " + queue.peek());

    queue.enqueue(4);
    queue.enqueue(5);
    queue.enqueue(6);

    while (!queue.isEmpty()) {
      System.out.println("Dequeued element: " + queue.dequeue());
    }
  }
}

// 좜λ ₯
/*
Front element: 1
Dequeue element: 1
Front element after dequeue: 2
Dequeued element: 2
Dequeued element: 3
Dequeued element: 4
Dequeued element: 5
Dequeued element: 6
 * /

μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•œ 큐 κ΅¬ν˜„ 예제

// Node
public class Node {
  int data;
  Node next;

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

// QueueLinkedList
public class QueueLinkedList {
  private Node front;
  private Node rear;
  private int size;

  public QueueLinkedList() {
    front = null;
    rear = null;
    size = 0;
  }

  // 큐에 μš”μ†Œ μΆ”κ°€
  public void enqueue(int data) {
    Node newNode = new Node(data);

    if (rear != null) {
      rear.next = newNode;
    }
    rear = newNode;

    if (front == null) {
      front = newNode;
    }
    size++;
  }

  // νμ—μ„œ μš”μ†Œ 제거 및 λ°˜ν™˜
  public int dequeue() {
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return -1;
    }

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

    if (front == null) {
      rear = null;
    }
    size--;
    return data;
  }

  // 큐의 μ•žμͺ½ μš”μ†Œ λ°˜ν™˜
  public int peek() {
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return -1;
    }
    return front.data;
  }

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

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

// Main 클래슀
public class Main {

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

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

    System.out.println("Front element: " + queue.peek());
    System.out.println("Dequeue element: " + queue.dequeue());
    System.out.println("Front element after dequeue: " + queue.peek());

    queue.enqueue(4);
    queue.enqueue(5);

    while (!queue.isEmpty()) {
      System.out.println("Dequeued element: " + queue.dequeue());
    }
  }
}

// 좜λ ₯
/*
Front element: 1
Dequeue element: 1
Front element after dequeue: 2
Dequeued element: 2
Dequeued element: 3
Dequeued element: 4
Dequeued element: 5
 * /