java로 큐(Queue)를 구현할 수 있다.

Goal

  • 큐(Queue)의 기본 연산을 이해한다.
  • java로 큐(Queue)를 구현할 수 있다.

큐(Queue)의 개념

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식

큐(Queue)의 연산

큐(Queue)는 FIFO(First-In-First-Out) 를 따른다.

큐(Queue)의 구현

큐(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;
  }
}

큐(Queue)의 사용 사례

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

java 라이브러리 큐(Queue) 관련 메서드

  1. 수행이 실패했을 때 exception을 발생하는 메서드
    • boolean add(E item)
      • 해당 item을 Queue에 삽입
      • 삽입에 성공하면 true를 반환, 삽입할 공간이 없는 경우는 예외(IllegalStateException)를 발생
    • E element()
      • Queue의 Head에 있는 item을 삭제하지않고 해당 item을 반환
      • 만약 Queue가 비어있으면 예외를 발생
    • E remove()
      • Queue의 Head에 있는 item을 삭제하고 해당 item을 반환
      • 만약 Queue가 비어있으면 예외를 발생
  2. 수행이 실패했을 때 null 또는 false를 반환하는 메서드
    • boolean offer(E item)
      • add(e)와 동일한 기능
      • 삽입에 성공하면 true를 반환, 실패하면 false를 반환
    • E peek()
      • element()와 동일한 기능
      • 만약 Queue가 비어있으면 null을 반환
    • E poll()
      • remove()와 동일한 기능
      • 만약 Queue가 비어있으면 null을 반환

java 라이브러리 큐(Queue) 사용법

관련된 Post

References