Queue란 무엇인가?

Queue란?

정의 : Queue란 컴퓨터의 기본 자료구조 중 하나로 먼저 들어온 데이터가 먼저 나가는 구조로 되어 있는 FIFO(First In First Out) 형식의 자료구조 이다.

---

Queue의 특징

• 가장 최근 들어온 자료가 가장 먼저 나가는 FIFO(First-In First-Out) 선입선출 형태를 갖는다.

• Queue는 한쪽에서는 데이터가 추가되고 한쪽에서는 데이터가 삭제되는 구조를 가지고 있다.

• Queue의 용어

  • 삽입(Enqueue) 이 일어나는 곳을 Rear
  • 삭제(Dequeue) 가 일어나는 곳을 Front
  
  

• 장점

  • 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 유리하다.
  • 데이터 접근 삽입 삭제가 빠르다.

• 단점

  • 크기가 제한적이다.

  • 중간에 위치한 데이터에 대한 접근이 불가능 하다.

    
    

• Queue의 종류

  • Linear Queue(선형 큐)

    

    • 기본적인 큐의 형태
    • 막대 모양으로 된 Queue로, 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸 씩 옮겨야 한다는 단점이 있다.
    
    

  • Circular Queue (원형 큐)

    

    • 선형 큐의 문제점을 보완한 큐
    • 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때
      (index+1) % 배열의 사이즈를 통해 0으로 순환되는 구조를 가진다.
    
    

  • Priority Queue (우선순위 큐)

    

    • 우선순위 큐는 마치 매직패스를 들고 있으면 가장 먼저 놀이기구를 탈 수 있는 것 처럼
    • 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 큐
    • 우선순위가 높은 데이터를 먼저 Dequeue 하는 특성을 위해
      • 내부의 heap이라는 완전 이진트리 자료구조를 통해 우선순위를 유지한다.
  
  

---

Queue은 왜 사용하는가

Queue는 주로 데이터가 입력된 순서대로 데이터를 처리해야할 상황에 사용이 되어진다.

• 콜센터 고객 대기 시간

• 우선순위가 동일한 작업 예약 (프린터 인쇄 대기)

• 캐시(Cache) 구현

• 선입선출이 필요한 대기열 (티켓 카운터)

• 너비 우선 탐색(BFS, Breadth-First Search) 구현

  
  

---

Queue의 구현

• Queue의 구현 방법

  • 배열(Array) 을 이용해 구현

    • 장점
      - 배열 내 요소의 주소를 나타내는 인덱스를 통해 원하는 데이터를 빠르게 검색하여 접근가능
    • 단점
      - 선언할 때 크기가 고정되어 배열에 들어있는 데이터 양에 따라 배열의 크기 조정이 필요
      - 데이터를 중간에 삽입하거나 삭제할 경우 해당 데이터 뒤에 있는 요소들의 위치를 모두 이동시켜야하는 비효율적인 상황이 발생
    
    

  • 연결리스트(LinkedList) 를 이용해 구현

    • 장점
      - 데이터의 양에 상관없이 크기가 동적으로 변경
      - 인덱스 대신 이전 데이터 그리고 다음 데이터의 위치를 기억하는 노드 형태를 이용하여 데이터 삽입, 삭제시 노드들 사이에 연결된 링크들을 끊거나 이어주면 되기에 과정이 용이하다.
    • 단점
      -데이터에 접근할 때 연결되어 있는 노드들을 따라 양 끝에서부터 순차적으로 접근해야하기 때문에 데이터 접근속도가 배열에 비해 느림
  
  

• Queue의 구현 자료구조 선택
  • 모든 원소의 값을 필요로 하거나 중간 데이터를 삽입 삭제할 경우
    ⇒ 연결리스트를 사용하여 구현
    
  • 특정한 데이터에 접근할 경우
    ⇒ 배열을 사용하여 구현
    
    
    

---

Java의 Queue 사용

• 선언

  import java.util.LinkedList; 
   import java.util.Queue; 
   Queue<Integer> queue = new LinkedList<>(); 
   Queue<String> queue = new LinkedList<>(); 

  Queue는 LinkedList를 통해 선언이 가능하다

  
  

• 주요 메소드

  메소드	설명
  add(Object item)	해당 큐의 맨 뒤에 전달된 요소를 삽입, (성공시 true를 반환, 큐가 full일 경우 IllegalStateException을 발생)
  element()	해당 큐의 맨 앞에 있는 요소를 반환
  offer(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입
  peek()	해당 큐의 맨 앞에 있는 요소를 반환. Empty일 경우 null을 반환
  poll()	해당 큐의 맨 앞에 있는 요소를 반환하고, 해당 요소를 큐에서 제거, Empty일 경우 null을 반환
  remove()	해당 큐의 맨 앞에 있는 요소를 제거

  
  

---

Queue의 시간복잡도

• LinearQueue

  add             : O(1)
  poll            : O(1)
  peek            : O(1)
  remove          : O(n)
  

  
  

• PriorityQueue

  add()      : O(log n)
  poll()     : O(log n)
  peek()     : O(1)