Queue(선형 큐)

특징

  • 줄 서있는 것처럼 선입선출(FIFO) 형태의 자료구조
  • 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과 달리 큐는 한쪽 끝에서 삽입 작업, 다른 쪽에서 삭제 작업이 양쪽으로 이루어진다.
  • 큐의 뒤(rear)에서만 삽입(enqueue)하고, 큐의 앞(front)에서는 삭제(dequeue)만 이루어진다.
  • 자바에서는 스택을 Stack 클래스로 구현하여 제공하지만, 큐는 Queue 인터페이스만 있고 별도의 클래스가 없다. 그래서 Queue 인터페이스를 구현한 클래스를 사용해야 한다.

단점

  • 선형 큐에서 삽입/삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고 앞에는 비어있을 수 있지만 이를 꽉 찼다고 인식한다. 데이터를 삭제할 때마다 한 칸 앞으로 이동시키는 것이 아니라 인덱스 단위로 큐의 연산을 진행하기 때문에 이러한 문제점이 있다. 이러한 단점을 보완하기 위해 Circular Queue(원형 큐)가 생겨났다.

메소드

Queue<자료형> queue = new LinkedList<>();

boolean add(E value)

  • value 삽입 성공 시 true, 실패 시 Exception 발생

boolean offer(E value)

  • value 삽입 성공 시 true, 실패 시 false 리턴

E remove(E value)

  • value 삭제 성공 시 삭제된 value, 공백 큐라면 Exception(NoSuchElementException) 발생

boolean remove(E value)

  • 해당 value가 존재하면 삭제 후 true, 존재하지 않으면 false 리턴

E poll(E value)

  • value 삭제 성공 시 삭제된 value, 공백 큐라면 null 리턴

E element()

  • head에 위치한 value를 리턴하거나, 공백 큐라면 Exception(NoSuchElementException) 발생

E peek()

  • head에 위치한 value를 리턴하거나, 공백 큐라면 null 리턴

void clear()

  • 해당 큐를 초기화 함(공백 큐로 만듦)

int size()

  • 큐의 사이즈를 리턴

boolean contains(E value)

  • value가 존재하면 true, 없으면 false 리턴

boolean isEmpty()

  • 공백 큐라면 true, 아니라면 false 리턴

활용

  • 큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
  • 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
    • 작업 스케줄링
  • 은행 업무
  • 콜센터 고객 대기 시간
  • 프로세스 관리
  • 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 캐시(Cache) 구현
  • 버퍼: 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역 (입출력 및 네트워크에서 사용)

Circular Queue

특징

  • 1차원 배열을 사용하여 구현한다.
  • 초기 front와 rear는 맨 처음 인덱스에 위치한다.
  • front와 rear를 회전시키기 위해서 모듈러(%) 연산을 사용한다.

주요 연산

  • enQueue: (rear + 1) % (배열의 크기)
    • 만약 rear + 1이 front와 같으면 해당 큐는 꽉 찬 것이다.
    • 배열의 크기가 11인 배열의 index 10까지 모두 채우면, 다음 rear는 11이 아니라 0이 된다.
  • deQueue: (front + 1) % (배열의 크기)
  • size: (배열의 크기 + rear - front) % (배열의 크기)
    • 주의사항: rear == front(가득 찼을 때)도 마찬가지로 0이 된다.
  • full: (rear + 1) % (배열의 크기) == front
  • empty: rear == front

Priority Queue

특징

  • Queue 인터페이스를 구현하였다.
  • 저장한 순서에 상관없이 우선순위(priority)가 높은 것부터 꺼낸다.
  • null을 저장하면 NPE가 발생한다.
  • 배열을 사용하며, 각 요소를 힙이라는 자료구조의 형태로 저장한다. (JVM의 힙과 자료구조의 힙은 다르다!)
  • 지정하지 않으면 숫자가 작을 수록 우선순위가 높다.
  • Priority Queue API

구현 방법

  • 배열을 기반으로 구현하는 방법
  • 연결 리스트를 기반으로 구현하는 방법
  • 힙(heap)을 이용하는 방법
  • 배열이나 연결 리스트로 구현할 경우 간단하게 구현이 가능하지만, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속해야 한다. 또 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.
  • 연결 리스트의 경우, 삽입의 위치를 찾기 위해 첫번째 노트부터 싲가하여 마지막 노드에 저장된 데이터와 우선순위를 비교해야 할 수도 있다. (성능 저하) 그래서 일반적으로 힙을 이용하여 구현한다.

Dequeue

특징

  • 데이터의 추가와 삭제를 양쪽 끝에서 가능하게 하는 자료구조 (큐와 스택을 합친 형태로 생각할 수 있음)
  • 연속적인 메모리를 기반으로 하는 ‘시퀀스 컨테이너’이다. 따라서 임의 접근 반복자를 제공한다.
  • Deque API

유형

  • scroll: 입력 제한 덱, 입력이 한쪽으로만 일어나도록 제한
  • self: 출력 제한 덱, 출력이 한쪽으로만 일어나도록 제한

활용

  • 스케줄링: 스케줄링이 복잡해질 수록 스택과 덱보다 효율이 잘 나오는 경우가 있다.
  • 우선순위 조절: 한 방향으로만 삽입/삭제가 가능한 스택과 큐와 달리 양방향으로 삽입/삭제가 자유롭다.

Stack과 Queue의 차이점

  • 아이템을 삭제할 때 가장 큰 차이점이 있다.
  • 스택은 가장 마지막에 추가된 item을 삭제하고, 큐는 가장 처음 들어와있던 item을 삭제한다.
  • 스택과 큐 모두 Peek을 사용할 수 있다. Peak 연산은 자료구조의 변화를 주지 않고, pop이나 dequeue를 할 때 리턴되는 item을 리턴할 수 있다.

참고