[자료 구조] 큐(Queue)

큐(Queue) 란?

데이터를 일시적으로 저장하고 처리하기 위한 추상 자료형(Abstract Data Type) 중 하나

First In First Out (FIFO) 방식으로 동작 → 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조

선형 구조로 이루어져 있으며, 가장 앞쪽은 front, 가장 뒤쪽을 rear라고 함

큐에 데이터를 삽입하는 연산을 enqueue, 큐에서 데이터를 삭제하는 연산을 dequeue라고 함

큐 활용

• 프로세스 스케줄링(Process Scheduling)
• 네트워크 트래픽 제어(Network Traffic Control)
• 메시지 큐(Message Queue)
• 버퍼(Buffer)

큐(Queue)의 주요 장점

1. FIFO(First In First Out) 구조

   데이터의 순서가 중요한 애플리케이션에서 사용하기 적합함

2. 데이터 삽입/삭제 연산이 빠름

   삽입연산은 뒤쪽에서, 삭제 연산은 앞쪽에서 수행함

   삽입/삭제 연산의 시간 복잡도가 O(1)로 매우 빠름

3. 자료구조의 구현이 쉬움

   • 배열로 구현할 경우 : 구현이 쉽고 접근이 용이함
   • 연결 리스트로 구현한 경우 : 동적으로 큐의 크기를 조절할 수 있어 메모리를 효율적으로 사용 가능

큐(Queue)의 단점

1. 크기에 제한이 있음

   자료구조의 크기가 고정되어 있기 때문에 크기를 초과라는 데이터를 삽입 불가

2. 중간에 위치한 데이터에 접근이 어려움

   큐의 중간에 위치한 데이터에 접근하기 위해서는 큐의 모든 데이터를 순서대로 탐색해야함. 이는 시간 복잡도가 O(n)으로 매우 느려질 수 있음

큐의 종류

• 일반적인 큐
• 우선순위 큐(Priority Queue)
  • 각 데이터마다 우선순위 값을 가지고 있어, 우선순위가 높은 데이터가 먼저 처리됨
  • heap이나 binary search tree로 구현 가능
• 원형 큐(Circular Queue)
  • 배열로 구현된 일반적인 큐에서 발생하는 메모리 낭비를 줄이기 위해 사용됨.
  • 데이터를 삽입할 때 rear를 이동하고, 데이터를 삭제할 때 front를 이동
• 블로킹 큐(Blocking Queue)
• 덱(Deque)
  • 양쪽 끝에서 삽입과 삭제가 가능한 큐
  • 택(Stack)과 큐(Queue)를 합친 형태로, stack과 queue를 대체해서 사용 가능
  • Queue와 마찬가지로 FIFO(First-In-First-Out) 구조를 가지고 있음

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        // 덱 생성
        Deque<String> deque = new ArrayDeque<String>();

        // 데이터 추가
        deque.addFirst("apple");
        deque.addLast("banana");
        deque.offerFirst("cherry");

        // 데이터 삭제
        String removedFirst = deque.removeFirst();
        String removedLast = deque.removeLast();
        System.out.println("Removed first element: " + removedFirst);
        System.out.println("Removed last element: " + removedLast);

        // 덱 출력
        System.out.println("Deque: " + deque);

        // 다음에 삭제될 요소 확인
        String peekedFirst = deque.peekFirst();
        String peekedLast = deque.peekLast();
        System.out.println("Next first element: " + peekedFirst);
        System.out.println("Next last element: " + peekedLast);

        // 덱의 크기 확인
        int size = deque.size();
        System.out.println("Size of deque: " + size);
    }
}

큐 코드

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 큐 생성
        Queue<String> queue = new LinkedList<String>();

        // 데이터 추가
        queue.add("apple");
        queue.add("banana");
        queue.add("cherry");

        // 데이터 삭제
        String removed = queue.remove();
        System.out.println("Removed element: " + removed);

        // 큐 출력
        System.out.println("Queue: " + queue);

        // 다음에 삭제될 요소 확인
        String peeked = queue.peek();
        System.out.println("Next element: " + peeked);

        // 큐의 크기 확인
        int size = queue.size();
        System.out.println("Size of queue: " + size);
    }
}

참고
https://leejinseop.tistory.com/36
https://galid1.tistory.com/483