[자료구조] 큐(Queue)란?

큐란?

• 큐(Queue)는 데이터를 일렬로 나열한 선형구조로 되어있다.
• 일시적으로 데이터를 저장하고 처리할 때 사용되며, 다양한 컴퓨터 애플리케이션에 사용된다.
• 나중에 들어간 데이터가 가장 먼저 나오는 스택과는 반대되는 개념이다.

큐의 특징

• 먼저 들어간 데이터가 먼저 나오는 선입선출(FIFO, First In First Out)구조로 이루어져있다.
• 큐가 꽉차서 데이터를 더 넣을 수 없는 상태를 오버플로우(Overflow), 큐가 비어있어서 더 꺼낼 수 없는 상황을 언더플로우(Underflow)라고 한다.
• 큐는 상황에 따라 배열을 사용해서 구현할 수도, 연결리스트를 이용해서 구현할 수도 있다.
• 큐의 연산은 삽입, 삭제, 맨 앞의 데이터 읽기, 큐가 비어있는지 확인, 큐의 사이즈 확인, 검색이 있다.

큐의 시간복잡도

1. 삽입(Enqueue)
   • 큐의 맨 뒤에 요소를 추가한다.
   • 따라서 시간복잡도는 O(1)이다.
2. 삭제(Dequeue)
   • 큐의 맨 앞에 있는 요소를 큐에서 제거한다.
   • 따라서 시간복잡도는 O(1)이다.
3. 맨 앞의 데이터 읽기(Peek)
   • 큐의 맨 앞에 있는 요소의 정보를 읽는다.
   • 따라서 시간복잡도는 O(1)이다.
4. 큐가 비어있는지 확인(IsEmpty)
   • 큐가 비어있는지 확인한다.
   • 따라서 시간복잡도는 O(1)이다.
5. 큐의 사이즈 확인(Size)
   • 큐의 사이즈를 확인한다.
   • 따라서 시간복잡도는 O(1)이다.
6. 큐의 데이터 탐색(Search)
   
   • 큐를 탐색하며 원하는 데이터를 찾는다.
   • 따라서 시간복잡도는 O(n)이다.

큐의 장단점

1. 장점
   • 선입선출 구조로 먼저 들어간 데이터가 먼저 나오는 순서가 보장되어 있다.
   • 구현이 쉽다.
   • 모델링을 통해 대기줄, 스케줄링 등에 활용할 수 있다.
2. 단점
   • 순차적인 구조이기에 데이터를 조회하려면 순차적으로 처리해야 한다.
   • 크기가 정해져있기 때문에 연산이 일어나면서 오버플로우(Overflow)가 발생할 수 있다.

예제

import java.util.*

fun main() {
    var queue: Queue<Int> = LinkedList<Int>()
    queue.add(1)
    queue.add(2)
    queue.add(3)

    println(queue.size)

    queue.remove()
    queue.remove()
    queue.remove()
}

출처 : 큐 위키백과