자료 구조 (5) : 큐(Queue)

큐

먼저 넣은 자료가 먼저 나오는 선형 자료 구조

 

• 주요 연산
  • enqueue(offer, add) : 큐의 뒤쪽(Rear)에서 데이터를 삽입
  • dequeue(poll, remove)  : 큐의 앞쪽(Front)에서 데이터를 제거 후 반환
  • peek(element, peek) : 큐의 앞쪽 데이터(다음에 나올 데이터)를 반환(제거하지 않음)
    
    

* Java에서 offer, poll, element는 값이 없을 때 예외를, add, remove, peek은 값이 없을 때 null과 같은 특수 값을 반환

• 특징
  • 선입선출(FIFO) : 먼저 들어간 데이터가 먼저 제거
  • 단방향성: 보통 뒤쪽(Rear)에서 삽입, 앞쪽(Front)에서 삭제(Deque는 양쪽에서 가능)
• 사용 상황(시간 순서대로 작업을 진행해야 하는 경우)
  • BFS
  • 작업 스케줄러
  • 대기열
• 종류
  • 일반 큐(Queue)
  • 원형 큐(Circular Queue) : 배열의 끝(Rear)이 꽉 차면 다시 배열의 앞(Front)으로 돌아오는 큐
  • 우선순위 큐(Priority Queue) : 삽입된 데이터마다 우선순위를 두고, 우선순위가 높은 데이터부터 꺼낼 수 있도록 만든 큐
  • 이중 큐(Deque, Double-Ended Queue) : 큐의 앞과 뒤 양쪽에서 삽입과 삭제가 모두 가능한 큐
• 시간 복잡도

	일반
삽입(enqueue)	O(1)
삭제(dequeue)	O(1)
조회(peek)	O(1)
조회(전체)	O(n)
크기(size)	O(1)

 

Queue 구현 예시

 

import java.util.*;

public class LinkedQueue<T> {

  private LinkedList<T> list = new LinkedList<T>();

  public LinkedQueue() {}

  public LinkedQueue(T elem) {
    offer(elem);
  }

  public int size() {
    return list.size();
  }

  public boolean isEmpty() {
    return size() == 0;
  }

  public T peek() {
    if (isEmpty()) throw new RuntimeException("Queue is Empty");
    return list.peekFirst();
  }

  public T poll() {
    if (isEmpty()) throw new RuntimeException("Queue is Empty");
    return list.removeFirst();
  }

  public void offer(T elem) {
    list.addLast(elem);
  }
}