큐(Queue) 란?

• FIFO(선입선출)구조의 자료구조

• 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림

  

• JAVA에서 구현

  1. LinkedList

     • LinkedList는 List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있기 때문에, 스택 / 큐 로서도 응용이 가능하다.
     • 실제로 LinkedList 클래스에 큐 동작과 관련된 메서드를 지원함 (push, pop, poll, peek, offer ..등)

  2. ArrayDeque

     • Deque(Double-Ended Queue)는 양쪽으로 넣고 빼는 것이 가능한 큐
     • 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있음
     • 스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠름
     • 사이즈에 제한이 없음
     • null 저장 불가능

  3. PriorityQueue

     • 우선 순위를 가지는 큐 (우선 순위 큐)
     • 일반적인 큐와는 조금 다르게, 원소에 우선 순위(priority)를 부여하여 우선 순위가 높은 순으로 정렬되고 꺼냄
     • 수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행할때 쓰임 (네트워크 제어, 작업 스케쥴링)
     • 우선순위 큐에 저장할 객체는 필수적으로Comparable인터페이스를 구현해야함
     • compareTo() 메서드 로직에 따라 자료 객체의 우선순위를 결정하는 식으로 동작되기 때문
     • 저장공간으로 배열을 사용, 각 요소를 힙(heap) 형태로 저장
     • null 저장 불가능

     🧱 Java Collections Framework 종류 💯 총정리