240315 TIL - Queue

오늘은 자료구조 중 Queue에 대해 정리를 해 보았다. 

큐(Queue) 란?

• FIFO(선입선출)구조의 자료구조
• 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림

기본적인 Queue의 메서드

• 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 저장 불가능

이렇게 Queue에 대해 정리를 해보았는데 최근 알고리즘 풀이에서 다양한 자료구조를 사용하려고 하고 있고 시간복잡도에 대한 부분도 중요하기 때문에 내가 정리한 큐와 다른 분들이 정리한 다른 자료구조에 대해서도 제대로 알고 적재적소에 사용할 수 있게 되면 좋겠다.