1️⃣ 큐(Queue).

큐(Queue)는 선형 자료구조 중 하나로, 데이터가 들어온 순서대로 처리되는 선입선출(FIFO, First In First Out) 구조를 가집니다.

1️⃣ 큐(Queue).

큐(Queue)는 가장 먼저 삽입된 데이터가 가장 먼저 제거됩니다.

2️⃣ 큐(Queue)의 연산.

Enqueue : 큐의 뒤(rear) 끝에 데이터를 추가하는 연산입니다.

Dequeue : 큐의 앞(front) 끝에서 데이터를 제거하고 반환하는 연산입니다.
front 또는 Peek : 큐의 앞 끝에 있는 데이터를 제거하지 않고 반환하는 연산.
isEmpty : 큐가 비어 있는지 확인하는 연산.
Size : 큐에 저장된 데이터의 개수를 반환하는 연산.

3️⃣ 큐(Queue)의 실제 응용 사례.

프린터 작업 대기열.
CPU 작업 스케줄링.
BFS(Breath-First Search, 너비 우선 탐색)

큐는 배열이나 연결 리스트를 이용하여 구현할 . 수있습니다.

4️⃣ 큐의 시간 복잡도.

큐의 각 연산은 다음과 같은 시간 복잡도를 가집니다.

Enqueue : O(1)
- 큐의 뒤 끝에 데이터를 추가하는 연산은 항상 일정한 시간 내에 완료됩니다.
Dequeue : O(1)
- 큐의 앞 끝에서 데이터를 제거하는 연산도 항상 일정한 시간 내에 완료됩니다.
Front 또는 Peek : O(1)
- 큐의 앞 끝에 있는 데이터를 확인하는 연산은 데이터 접근만 필요하기 때문에 일정한 시간 내에 완료됩니다.
isEmpty : O(1)
- 큐가 비어 있는지 확인하는 연산은 큐의 크기만 확인하면 되므로 일정한 시간 내에 완료됩니다.
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️⃣ 큐의 기본 구성 요소.

Front : 큐의 가장 앞쪽을 가리키는 포인터 입니다. Dequeue 연산이 발생할 때 데이터를 제거하는 위치를 나타냅니다.
Rear : 큐의 가장 뒤쪽을 카리키는 포인터 입니다. Enqueue 연산이 발생할 때 데이터를 추가하는 위치를 나타냅니다.
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
*/

이와 같이 큐는 연결 리스트를 이용하여 구현할 수 있습니다.

큐를 배열 또는 연결 리스트를 이용하여 구현했을 때 각각의 장단점.

배열 기반 큐는 간단하고 빠르지만 고정된 크기 문제를 해결해야 합니다.

연결 리스트 기반 큐는 동적으로 크기를 조절할 수 있지만 메모리 사용량이 더 많을 수 있습니다.

devkobe24.com

Contact

1️⃣ 큐(Queue).

1️⃣ 큐(Queue).

2️⃣ 큐(Queue)의 연산.

3️⃣ 큐(Queue)의 실제 응용 사례.

4️⃣ 큐의 시간 복잡도.

5️⃣ 큐의 구현

7️⃣ 큐(Queue) 기본 구조.

👉 1️⃣ 큐의 기본 구성 요소.

👉 2️⃣ 연결 리스트를 이용한 큐의 구현 방법.