[자료구조] Linear Data - Queue (FIFO)

Kyung Jae, Cheong·2024년 10월 14일
Javapython자료구조
0

자료구조-DataStructure

목록 보기
5/19
post-thumbnail

본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.

  • 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
    • IDE : IntelliJ IDEA (Ultimate Edition)
    • Java : JDK 21 (corretto-21)
    • Python : 3.9 (conda env)

자료구조 - Queue

0. 서론: Queue란?

큐(Queue)는 FIFO(First In, First Out) 구조로 동작하는 선형 자료구조입니다.

  • 즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조입니다.
  • 큐를 생각할 때 흔히 떠올릴 수 있는 예시로는 은행의 대기줄이나 버스 승차 대기열을 들 수 있습니다.
    • 대기열의 맨 앞에 있는 사람은 가장 먼저 서비스를 받고, 새로운 사람은 맨 뒤에 추가됩니다.
    • 이처럼 큐는 데이터 삽입과 삭제가 서로 다른 위치에서 이루어집니다.

큐에서 데이터를 삽입하는 연산은 enqueue(삽입), 데이터를 제거하는 연산은 dequeue(삭제)라고 부릅니다.

  • 데이터를 삽입할 때는 맨 뒤에 데이터를 추가하고, 제거할 때는 맨 앞에 있는 데이터를 삭제합니다.
  • 이 때문에 스택과는 반대로 가장 먼저 들어간 데이터가 가장 먼저 나오는 구조가 됩니다.
    • 이러한 방향은 python과 java 모두 공통적으로 적용됩니다.

0.1 Queue의 주요 연산

큐에서 주로 사용하는 연산들은 다음과 같습니다:

  • enqueue(item): 큐의 맨 뒤에 데이터를 삽입하는 연산.
  • dequeue(): 큐의 맨 앞에 있는 데이터를 제거하는 연산.
  • peek(): 큐의 맨 앞에 있는 데이터를 제거하지 않고 확인하는 연산.
  • isEmpty(): 큐가 비어 있는지 확인하는 연산.

0.2 Queue의 활용사례

큐는 순서대로 처리해야 하는 작업을 관리하는데 유용한 자료구조입니다.

대표적인 활용 사례는 다음과 같습니다:

  • CPU 작업 스케줄링: 작업들이 도착한 순서대로 실행되는 라운드 로빈 스케줄링 같은 알고리즘에서 큐가 사용됩니다.
  • 프린터 작업 관리: 여러 사용자가 프린터에 요청한 작업은 요청 순서대로 처리되며, 이때 작업 요청들을 큐에 저장하여 처리합니다.
  • BFS(너비 우선 탐색): 그래프 탐색 알고리즘 중 하나인 BFS는 큐를 사용하여 탐색 순서를 관리합니다.
  • 메시지 큐: 네트워크 패킷 처리나 이벤트 처리에서 큐는 메시지를 순서대로 처리하는 데 사용됩니다.

Queue는 스택과는 반대로, 먼저 들어간 데이터가 먼저 나오는 구조를 가지므로, 대기열이나 작업 처리의 순서를 보장해야 하는 상황에서 필수적으로 사용됩니다.

1. Queue 개념 및 구현

1.1 Java에서의 Queue

  • Java에서는 Queue 인터페이스가 제공되며, 이를 구현하는 다양한 클래스들이 있습니다.
    • 대표적으로 ArrayDeque, LinkedList, PriorityQueue가 있으며, 각각의 구현 방식에 따라 특성이 다릅니다.
    • 다만, PriorityQueue는 추후에 다룰 Heap 자료구조에 기반한 자료구조로 FIFO가 적용되지 않습니다. 추후에 Heap 자료구조를 다룰때 자세히 다루겠습니다.

Queue 인터페이스

  • Queue는 인터페이스로 제공되며, 가장 기본적인 FIFO(First In, First Out) 구조를 따릅니다.
  • Queue 인터페이스는 데이터를 추가하는 offer() 메서드와 데이터를 제거하는 poll() 메서드, 맨 앞 데이터를 확인하는 peek() 메서드 등을 제공합니다.
  • 여기서 중요한 점은 Queue 인터페이스에서 offer(), poll(), peek() 메서드와 같은 큐의 주요 연산을 정의하고, 구체적인 동작은 각 클래스(ArrayDeque, LinkedList)에서 구현됩니다.

주요 Queue 구현체

  1. LinkedList
    LinkedList는 Queue 인터페이스를 구현하여 기본적인 큐 연산을 지원합니다.
  • 데이터 삽입과 삭제가 빈번한 경우 적합한 자료구조로, 큐의 삽입 연산과 삭제 연산이 O(1)입니다.
  • 배열 기반이 아닌 연결 리스트로 구현되어 있으며, 큐의 크기가 동적으로 변할 수 있습니다.
  • 하지만 각 요소가 노드로 연결되어 있기 때문에 추가적인 메모리 오버헤드(포인터 관리)가 발생합니다.
  1. ArrayDeque
    ArrayDeque는 배열을 기반으로 한 큐의 구현체로, Deque 인터페이스도 함께 구현하고 있습니다.
  • Deque는 양방향 큐를 지원하지만, ArrayDeque를 큐로 사용하는 경우에는 단방향으로만 사용하게 됩니다.
  • 원형 배열 기반 자료구조로, 큐의 크기가 동적으로 확장됩니다.
    • 참고: 원형 배열이란 배열의 처음과 끝이 연결되어 있는 것처럼 동작하는 구조로, 배열이 가득 찼을 때 새로운 공간을 만들기 위해 데이터를 이동하지 않고 효율적으로 앞뒤로 데이터를 추가하거나 제거할 수 있습니다.
  • 큐의 주요 연산들이 O(1)로 매우 빠르게 수행되며, 큐의 크기가 커질 때 재할당 비용이 발생할 수 있습니다.
  • ArrayDeque는 연결 리스트 기반의 LinkedList보다 메모리 사용 효율이 뛰어나고, 속도도 더 빠르기 때문에 Queue 구현으로 더 많이 사용됩니다.

Java에서의 ArrayDeque와 LinkedList 비교

  • ArrayDeque와 LinkedList는 모두 Queue를 구현할 수 있지만, 성능 면에서는 ArrayDeque가 더 효율적입니다.
  • ArrayDeque는 연속된 배열 메모리를 사용해 삽입 및 삭제를 처리하며, LinkedList는 각 요소에 대한 포인터를 사용하여 노드를 연결하기 때문에 메모리 오버헤드가 발생할 수 있습니다.
  • 또한 ArrayDeque는 추가적인 동기화 비용 없이 멀티스레드 환경에서 사용될 수 있는 반면, LinkedList는 멀티스레드 환경에서 별도의 동기화가 필요할 수 있습니다.

Java Queue 코드 예시

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

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

        // 데이터 삽입 (offer)
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        // 데이터 제거 (poll)
        System.out.println(queue.poll());  // 10 출력

        // 맨 앞 데이터 확인 (peek)
        System.out.println(queue.peek());  // 20 출력

        // Queue 상태 출력
        System.out.println(queue);  // [20, 30] 출력
    }
}

위 코드에서 Queue 인터페이스를 사용하여 데이터를 삽입할 때는 offer()를, 데이터를 제거할 때는 poll()을 사용하며, 현재 가장 앞에 있는 데이터를 확인하려면 peek()을 사용합니다.

Deque로 Queue 구현

  • Java에서 큐를 구현할 때, Deque 인터페이스를 사용해도 됩니다.
  • Deque는 양방향 큐를 제공하며, ArrayDeque나 LinkedList를 사용하여 큐를 구현할 수 있습니다.
  • 다만, Queue 인터페이스만으로도 기본적인 큐 연산이 충분히 가능하기 때문에, 양방향 큐의 기능이 필요하지 않다면 Queue 인터페이스를 사용하는 것이 권장됩니다.

1.2 Python에서의 Queue

Python에서는 기본적으로 Queue 자료구조를 위한 표준 라이브러리를 제공합니다.

주요한 구현 방식으로는 다음과 같은 두 가지가 있습니다:
1. collections.deque: 빠르고 효율적인 양방향 큐를 제공하는 deque 객체.
2. queue.Queue: 멀티스레드 환경에서 안전한 FIFO Queue를 구현하기 위한 클래스.

1.2.1 collections.deque를 이용한 Queue

Python의 collections.deque는 양방향 큐를 지원하는 매우 효율적인 자료구조입니다.

  • 리스트(list)와 달리 양쪽에서 데이터를 빠르게 추가하거나 제거할 수 있으며, 큐 연산을 할 때 O(1) 시간 복잡도를 보장합니다.
  • 스레드 안전성이나 잠금(lock)이 필요하지 않은 경우, 가장 빠르고 가벼운 큐 구현체로 deque가 많이 사용됩니다.
from collections import deque

# deque를 이용한 Queue 구현
queue = deque()

# 데이터 삽입 (append)
queue.append(10)
queue.append(20)
queue.append(30)

# 데이터 제거 (popleft)
print(queue.popleft())  # 10 출력

# 맨 앞 데이터 확인 (peek)
print(queue[0])  # 20 출력

# Queue 상태 출력
print(queue)  # deque([20, 30]) 출력

위 코드에서 deque 객체를 사용하여 큐처럼 동작하도록 구현했습니다.

  • 데이터 삽입은 append()로, 데이터 제거는 popleft()로 이루어지며, 맨 앞의 데이터를 확인할 때는 인덱싱을 사용할 수 있습니다.

1.2.2 queue.Queue를 이용한 멀티스레드 안전 Queue

Python의 queue.Queue는 멀티스레드 환경에서 스레드 안전성을 보장하는 큐이고, FIFO(First In, First Out) 큐로 구현되어 있습니다.

  • 이 클래스는 스레드 간의 데이터 전달을 관리할 때 유용하게 사용되며, 내부적으로 잠금 메커니즘을 사용하여 데이터 경쟁을 방지합니다.
  • 기본적으로 큐에 최대 크기를 지정할 수 있으며, 큐가 가득 찬 상태에서 삽입이 시도되면 대기하게 됩니다.
import queue

# 멀티스레드 환경에서 안전한 Queue 생성
q = queue.Queue()

# 데이터 삽입 (put)
q.put(10)
q.put(20)
q.put(30)

# 데이터 제거 (get)
print(q.get())  # 10 출력

# 맨 앞 데이터 확인 (peek) - 큐에 peek 메서드는 없지만, 큐를 먼저 비우지 않고 처리 가능
print(q.queue[0])  # 20 출력

# Queue 상태 출력
print(list(q.queue))  # [20, 30] 출력

위 코드는 스레드 안전한 Queue를 사용하여 데이터를 삽입(put())하고 제거(get())하는 기본적인 큐 연산을 보여줍니다. queue.Queue는 내장된 잠금 메커니즘을 사용하여 멀티스레드 환경에서 안전하게 동작합니다.

Python Queue 구현 방식 비교

Python에서 큐를 구현할 때는 용도에 따라 다음과 같은 기준을 사용할 수 있습니다:

구현 방식장점단점사용 사례
collections.deque- 양방향 큐 지원
- 빠른 삽입/삭제 (O(1))
- 스레드 안전성이 필요 없을 때 적합		- 크기 제한이 없음
- 멀티스레드 환경에서는 사용 주의		단일 스레드 환경에서
빠르고 효율적인 큐가 필요할 때
queue.Queue- 멀티스레드 환경에서
스레드 안전성을 보장
- 큐의 최대 크기 지정 가능		- 스레드 간의 데이터 통신을
위한 구조라 성능이 조금 느림		멀티스레드 환경에서의
데이터 전송 및 동기화
  • 멀티스레드 안전성이 필요 없고, 빠르고 간단한 큐 구현이 필요하다면 collections.deque를 사용하는 것이 적합합니다.
  • 반면, 멀티스레드 환경에서 데이터 동기화가 중요한 경우 queue.Queue를 사용하여 스레드 안전성을 확보할 수 있습니다.

2. Queue 활용 사례

큐는 순서대로 작업을 처리하는 많은 문제에서 매우 유용하게 사용됩니다. 대표적인 큐의 활용 사례는 다음과 같습니다.

2.1 CPU 작업 스케줄링

  • 운영 체제에서 프로세스 스케줄러는 작업들을 FCFS(First-Come, First-Served) 방식으로 처리하며, 이를 구현할 때 큐를 사용합니다.
  • 작업이 도착한 순서대로 큐에 저장하고, 각 작업을 차례대로 처리합니다.
  • 또한 라운드 로빈(Round Robin) 스케줄링에서도 시간 할당량만큼 프로세스를 실행한 후 큐의 맨 뒤로 다시 배치하는 방식으로 동작합니다.

2.2 프린터 작업 관리

  • 여러 사용자가 프린터에 인쇄 작업을 요청할 때, 작업들은 요청된 순서대로 처리됩니다.
  • 이때 인쇄 작업을 대기열에 저장하여 처리하는 방식에 큐를 사용할 수 있습니다.
    • 작업이 요청되면 큐에 추가(enqueue)하고, 프린터가 준비되면 큐에서 작업을 제거(dequeue)하여 인쇄 작업을 시작합니다.

2.3 BFS(너비 우선 탐색)

  • 그래프 탐색 알고리즘 중 하나인 너비 우선 탐색(BFS)는 큐를 사용하여 탐색 순서를 관리합니다.
  • BFS는 시작 정점에서 가까운 노드부터 차례대로 탐색하는 방식으로, 큐에 탐색할 노드를 넣고, 먼저 들어간 노드부터 탐색을 진행합니다.
from collections import deque

# BFS를 이용한 그래프 탐색
def bfs(graph, start):
    visited = []
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])  # 현재 노드와 연결된 노드들을 큐에 추가
    return visited

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

2.4 메시지 큐

  • 메시지 큐는 네트워크 패킷 처리나 이벤트 처리에서 큐를 사용하여 메시지를 순서대로 처리합니다.
  • 메시지 큐는 시스템 간에 데이터를 비동기적으로 전송하거나 프로듀서-컨슈머 패턴에서 자주 사용되며, 큐에 데이터를 저장해 두었다가 순서대로 처리합니다.

2.5 캐시 구현

  • 캐시 메모리는 LRU(Least Recently Used) 알고리즘을 사용하여 큐의 형태로 구현될 수 있습니다.
    • 큐에 가장 최근에 사용된 데이터를 넣고, 오래된 데이터는 큐에서 제거하는 방식으로 캐시를 관리합니다.

3. Queue의 시간 및 공간 복잡도

큐에서 이루어지는 연산들은 대부분 상수 시간으로 이루어지기 때문에 매우 효율적입니다.

3.1 주요 연산의 시간 복잡도

  • enqueue(item): 큐의 맨 뒤에 데이터를 추가하는 연산으로, O(1) 시간 복잡도를 가집니다.
  • dequeue(): 큐의 맨 앞에서 데이터를 제거하는 연산으로, O(1) 시간 복잡도를 가집니다.
  • peek(): 큐의 맨 앞 데이터를 확인하는 연산으로, O(1) 시간 복잡도를 가집니다.
  • isEmpty(): 큐가 비어 있는지 확인하는 연산으로, O(1) 시간 복잡도를 가집니다.

큐의 모든 기본 연산들은 큐의 크기와 무관하게 O(1)로 동작하기 때문에 매우 빠릅니다.

3.2 큐 전체 탐색의 시간 복잡도

큐에서의 전체 탐색은 큐의 모든 요소를 순차적으로 살펴보는 작업이므로, 큐의 크기에 비례하여 시간이 소요됩니다.

  • 전체 탐색의 시간 복잡도는 O(n)입니다. 여기서 n은 큐에 들어 있는 데이터의 개수입니다.

3.3 공간 복잡도

큐는 데이터를 저장하는 자료구조이기 때문에, 큐의 크기가 커질수록 메모리 사용량도 증가합니다.

  • 큐에 저장된 데이터의 개수에 비례하여 공간이 필요하므로, 공간 복잡도는 O(n)입니다.

또한, 배열 기반 큐의 경우 크기가 고정되어 있을 수 있으며, 크기 초과 시 재할당이 발생할 수 있지만, 동적 배열을 사용하는 구현체에서는 자동으로 배열의 크기를 확장하여 데이터를 추가합니다.

마무리

이번 포스팅에서는 큐(Queue) 자료구조의 개념과 구현 방법을 Java와 Python에서 각각 살펴보았습니다.

  • 큐는 FIFO(First In, First Out) 구조를 따르며, 순서대로 처리해야 하는 작업을 관리하는 데 매우 유용합니다.
  • Java에서는 Queue 인터페이스를 구현한 다양한 자료구조들이 있으며, 성능 면에서는 ArrayDeque가 가장 효율적이므로 일반적으로 가장 많이 사용됩니다.
  • Python에서는 deque를 사용하면 빠르고 간단하게 큐를 구현할 수 있으며, 멀티스레드 환경에서는 queue.Queue를 사용하여 스레드 안전한 큐를 구현할 수 있습니다. 각 상황에 맞는 구현체를 선택하는 것이 중요합니다.

다음 포스팅에서는 Deque 자료구조를 다룰 예정입니다.

  • Deque(Double-Ended Queue)는 큐와 스택의 특성을 모두 가지며, 양방향에서 데이터를 추가하거나 제거할 수 있는 자료구조입니다. Queue와의 차이점과 Deque의 다양한 활용을 함께 살펴보겠습니다.
profile
Kyung Jae, Cheong
일 때문에 포스팅은 잠시 쉬어요 ㅠ 바쁘다 바빠 모두들 화이팅! // Machine Learning (AI) Engineer & BackEnd Engineer (Entry)
이전 포스트

[자료구조] Linear Data - Stack (LIFO)

다음 포스트

[자료구조] Linear Data - Deque (양방향 큐)

0개의 댓글