Queue (큐)

📌 목차

❓ Queue 란 ❓

Queue 주요 동작

Queue의 사용 사례

Queue의 종류

Queue 구현

---

 

❓ Queue 란 ❓

큐(Queue)는 먼저 집어 넣는 데이터가 먼저 나오는 FIFO(First In First Out), 선입선출 방식입니다. 선입선출 구조이기 때문에 앞쪽을 나타내는 Front와 뒤쪽을 나타내는 Rear가 있습니다.

나중에 집어 넣는 데이터가 먼저 나오는 스택(stack)과는 반대되는 개념입니다.

 

🔶 Queue 주요 동작

• enQueue( ) : 큐에 데이터를 넣는 과정, Rear가 커진다. Push로 만들 수도 있지만 스택과 혼돈이 생길 수도 있으므로 지양한다.
• deQueue( ) : 큐에서 데이터를 빼는 과정, Front가 커진다. Pop으로 만들 수도 있지만 위와 마찬가지로 지양한다.
• isEmpty( ) : 큐가 비어있는지 확인한다.
• isFull( ) : 큐가 꽉 차 있는지 확인한다.
• peek( ) : 앞에 있는 원소를 삭제하지 않고 반환한다.

 

🔶 Queue의 사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 너비 우선 탐색 (BFS, Breath-First Search) 구현
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue) 를 사용한다.
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐(Queue)에 다시 저장한다.
  • 노드를 접근할 순서대로 처리할 수 있다.
• 캐시 (Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 ( 티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

 

🔶 Queue의 종류

• 선형 큐 : 1차원 배열을 이용한 큐 ( 큐의 크기가 배열의 크기가 되는 구조 ), front와 rear을 이용하여 공백과 포화 상태를 판단할 수 있다.
  • front = rear 인 경우 공백 상태이다.
  • rear = n - 1 ( n은 배열크키이다.)
• 원형 큐 : 메모리 공간을 아끼기 위해 이론적으로 원형적인 큐 (배열의 처음과 끝이 연결되어 있다고 가정)를 만들어 사용
  • 공백과 포화 상태 구분을 위해 front가 있는 자리는 사용하지 않고 빈자리로 둔다.
  • front가 잇는 자리는 데이터가 비어 있다고 생각한다.
  • rear가 마지막 부분에 있다면 mod연산을 이용하여 앞으로 보낸다. (Index의 순환)
  • front와 rear가 같다면 공백 상태이다.
  • rear의 다음 칸이 front라면 full 상태이다.
• 연결 리스트(Linked List)를 이용한 큐 : 연결 리스트를 이용하여 큐처럼 이용한다.
  • front는 첫번째 노드를 가리킨다. rear는 마지막 노드를 가리킨다.
  • 각각의 노드는 큐의 원소이다.
  • 초기 혹은 공백 상태는 front와 rear가 null이다.
  • front와 rear는 주소값을 가지고 있다.(포인터)
  • 빈 공간이 생기지 않으므로 메모리를 아낄 수 있다.
  • 대신 메모리를 잡는 시간, 구현 난이도가 있다.

 

🔶 Queue 구현

public class MyQueue {
  private static class QueueNode {
    private T data;
    private QueueNode next;

    public QueueNode(T data) {
      this.data = data;
    }
  }

  private QueueNode first;
  private QueueNode last;

  public void add(T item) {
    QueueNode t = new QueueNode(item);

    if (last != null) last.next = t;
    last = t;
    if (first == null) first = last;
  }

  public T remove() {
    if (first == null) throw new NoSuchElementException();
    T data = first.data;
    first = first.next;

    if (first == null) last = null;
    return data;
  }

  public T peek() {
    if (first == null) throw new NoSuchElementException();
    return first.data;
  }

  public boolean isEmpty() {
    return first == null;
  }
}

 

---

reference

https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html

[자료구조] 큐(Queue)란 - Heee's Development Blog

 

https://mungto.tistory.com/169

큐(Queue)란 무엇인가?

 

https://galid1.tistory.com/483

자료구조 - 큐(Queue)란?