자료구조: 큐(Queue)

1. 개요 (Introduction)

Queue는 데이터를 일렬로 저장하고 처리하는 선형 자료구조로, FIFO(First-In-First-Out) 원칙을 따릅니다. 이는 가장 먼저 추가된 요소가 가장 먼저 제거되는 방식으로, 사람 줄을 서서 차례로 처리하는 것과 유사합니다. Queue는 CPU 스케줄링, 프린터 작업 처리, 네트워크 패킷 처리 등 다양한 분야에서 활용됩니다.

https://www.geeksforgeeks.org/queue-data-structure/

2. Queue의 활용 예시 (Use Cases of Queue)

Queue는 특정 순서를 유지해야 하는 문제에서 유용하게 사용됩니다.

• 작업 스케줄링: 운영체제의 작업 스케줄링에서 프로세스를 처리할 때 Queue가 사용됩니다. 먼저 들어온 작업이 먼저 처리되므로 처리 순서를 제어할 수 있습니다.
• 프린터 작업 관리: 프린터에 여러 작업이 대기 중일 때, Queue를 사용하여 작업을 순서대로 출력할 수 있습니다.
• 네트워크 패킷 처리: 네트워크에서 패킷을 처리할 때 Queue를 사용하여 패킷을 순서대로 처리하고 전송할 수 있습니다.
• 폭 넓은 그래프 탐색: BFS(너비 우선 탐색) 알고리즘에서 Queue를 사용하여 각 정점을 순서대로 탐색합니다.

3. Queue의 동작 (Operations of Queue)

Queue는 다음과 같은 기본 동작을 제공합니다:

• Enqueue: Queue의 맨 뒤에 새로운 요소를 추가합니다.
• Dequeue: Queue의 맨 앞 요소를 제거하고 반환합니다. Queue가 비어 있을 경우 예외가 발생할 수 있습니다.
• Front: Queue의 맨 앞 요소를 제거하지 않고 반환하여 Queue의 현재 상태를 확인할 수 있습니다.
• IsEmpty: Queue가 비어 있는지 확인하는 연산입니다.

4. Golang으로 Queue 구현하기

Golang에서는 Queue 자료구조가 내장되어 있지 않지만, slice를 사용하여 구현할 수 있습니다. slice는 요소를 추가하고 제거할 때 효율적이며, Queue의 Enqueue와 Dequeue 작업을 지원하는데 적합합니다.

type Queue []int

// Enqueue 연산: Queue의 맨 뒤에 요소를 추가합니다.
func (q *Queue) Enqueue(v int) {
    *q = append(*q, v)
}

// Dequeue 연산: Queue의 맨 앞 요소를 제거하고 반환합니다.
func (q *Queue) Dequeue() (int, bool) {
    if len(*q) == 0 {  // Queue가 비어 있는지 확인
        return 0, false
    }
    element := (*q)[0]  // 첫 번째 요소를 저장
    *q = (*q)[1:]       // 첫 번째 요소를 제외하고 slice 재조정
    return element, true
}

// Front 연산: Queue의 맨 앞 요소를 반환합니다.
func (q *Queue) Front() (int, bool) {
    if len(*q) == 0 {
        return 0, false
    }
    return (*q)[0], true
}

// IsEmpty 연산: Queue가 비어 있는지 확인합니다.
func (q *Queue) IsEmpty() bool {
    return len(*q) == 0
}

func main() {
    queue := Queue{}

    queue.Enqueue(10)
    queue.Enqueue(20)
    queue.Enqueue(30)

    fmt.Println(queue.Front())  // Output: 10, true
    fmt.Println(queue.Dequeue()) // Output: 10, true
    fmt.Println(queue.Dequeue()) // Output: 20, true
    fmt.Println(queue.IsEmpty()) // Output: false
    fmt.Println(queue.Dequeue()) // Output: 30, true
    fmt.Println(queue.IsEmpty()) // Output: true
}

 

Golang에서 제네릭을 활용한 Queue 구현

package main

import "fmt"

// 제네릭 Queue 정의
type Queue[T any] struct {
    elements []T
}

// Enqueue 메서드
func (q *Queue[T]) Enqueue(value T) {
    q.elements = append(q.elements, value)
}

// Dequeue 메서드
func (q *Queue[T]) Dequeue() (T, bool) {
    var zero T
    if len(q.elements) == 0 {
        return zero, false
    }
    value := q.elements[0]
    q.elements = q.elements[1:]
    return value, true
}

// Front 메서드
func (q *Queue[T]) Front() (T, bool) {
    var zero T
    if len(q.elements) == 0 {
        return zero, false
    }
    return q.elements[0], true
}

// IsEmpty 메서드
func (q *Queue[T]) IsEmpty() bool {
    return len(q.elements) == 0
}

func main() {
    var queue Queue[int]
    queue.Enqueue(10)
    queue.Enqueue(20)
    fmt.Println(queue.Front())    // Output: 10, true
    fmt.Println(queue.Dequeue())  // Output: 10, true
    fmt.Println(queue.IsEmpty())  // Output: false
}

Queue에서 append와 slicing 사용

Queue는 FIFO(First In, First Out) 구조이므로, 처음 추가된 요소를 가장 먼저 제거해야 합니다. 이를 위해 append로 맨 뒤에 요소를 추가하고, slicing을 통해 맨 앞 요소를 제거합니다.

type Queue[T any] struct {
    elements []T
}

func (q *Queue[T]) Enqueue(value T) {
    q.elements = append(q.elements, value)  // append로 맨 뒤에 요소 추가
}

func (q *Queue[T]) Dequeue() (T, bool) {
    var zero T
    if len(q.elements) == 0 {
        return zero, false
    }
    value := q.elements[0]
    q.elements = q.elements[1:]  // slicing으로 맨 앞 요소 제거
    return value, true
}

 

• Enqueue에서는 append를 사용하여 Queue의 맨 뒤에 요소를 추가합니다.
• Dequeue에서는 slicing을 사용하여 맨 앞 요소를 제거합니다.

 

 

5. Java로 Queue 구현하기

Java에서는 java.util.Queue 인터페이스를 사용하여 Queue를 구현할 수 있습니다. LinkedList나 ArrayDeque 클래스를 활용하면 간단하게 Queue 기능을 사용할 수 있습니다.

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

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

        // Enqueue 연산: Queue의 맨 뒤에 요소 추가
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        // Front 연산: Queue의 맨 앞 요소 확인
        System.out.println("Front element: " + queue.peek());  // Output: 10

        // Dequeue 연산: Queue의 맨 앞 요소 제거
        System.out.println("Removed element: " + queue.poll());  // Output: 10
        System.out.println("Removed element: " + queue.poll());  // Output: 20

        // IsEmpty 연산: Queue가 비어있는지 확인
        System.out.println("Is queue empty? " + queue.isEmpty());  // Output: false
        queue.poll();
        System.out.println("Is queue empty? " + queue.isEmpty());  // Output: true
    }
}

 

6. Queue의 시간 복잡도 (Time Complexity of Queue Operations)

Queue 자료구조의 각 연산은 대부분 O(1) 시간 복잡도를 가지며, 이는 Queue가 FIFO 구조로 동작하여 추가와 제거가 Queue의 양 끝에서만 이루어지기 때문입니다. 주요 연산의 시간 복잡도를 구체적으로 살펴보고 그래프로 표현해보겠습니다.

1. Enqueue (삽입) 연산 - O(1)

• 설명: Enqueue 연산은 Queue의 맨 뒤에 새로운 요소를 추가하는 작업입니다. 이때 기존의 요소를 이동시키지 않고 끝에만 추가하면 되므로 상수 시간에 수행할 수 있습니다.
• 예외 상황: 배열 기반의 고정 크기 Queue의 경우, 배열이 가득 차면 새로운 요소를 추가하기 위해 배열 크기를 늘리거나, 큐의 맨 앞쪽으로 이동시켜야 할 수도 있습니다. 이 경우 배열 재조정이 필요한 경우 O(n) 시간이 걸릴 수 있지만, 대부분의 구현에서는 이를 피하기 위해 동적 크기 배열이나 연결 리스트를 사용합니다.

2. Dequeue (삭제) 연산 - O(1)

• 설명: Dequeue 연산은 Queue의 맨 앞 요소를 제거하고 반환하는 작업입니다. 첫 번째 요소만을 참조하고, Queue의 시작 부분을 다음 요소로 이동하면 되므로 상수 시간에 수행됩니다.
• 주의 사항: Dequeue 연산 시 Queue가 비어 있는 경우 예외 처리가 필요합니다. 이 역시 상수 시간에 처리될 수 있습니다.

3. Front (맨 앞 요소 확인) 연산 - O(1)

• 설명: Front 연산은 Queue의 맨 앞 요소를 제거하지 않고 확인하는 작업입니다. 단순히 첫 번째 요소를 참조하여 반환하므로 상수 시간에 수행됩니다.

4. IsEmpty (비어있는지 확인) 연산 - O(1)

• 설명: Queue가 비어 있는지 확인하는 연산으로, 요소의 개수나 크기 상태를 확인하여 상수 시간에 수행됩니다. 이는 Queue의 상태를 확인하는 데 필수적인 연산입니다.

요약된 시간 복잡도

7. Queue를 활용한 문제 해결 (Problem Solving with Queue)

Queue를 활용하여 해결할 수 있는 문제는 다양합니다.

• CPU 작업 스케줄링: 운영체제에서 작업을 순서대로 처리하여 공평하게 CPU를 분배할 수 있습니다.
• 그래프 탐색: 너비 우선 탐색(BFS)을 이용하여 특정 노드부터 연결된 모든 노드를 탐색할 수 있습니다.
• 데이터 스트림 처리: 실시간으로 들어오는 데이터를 순서대로 처리해야 할 때 Queue를 활용할 수 있습니다.

8. Queue 사용 시 주의점 및 Best Practices

• 메모리 관리: Queue의 크기를 고려하여 동적 메모리를 사용하거나 고정 크기를 설정하는 것이 좋습니다.
• 상황에 따른 선택: 동적 크기가 필요한 경우 LinkedList나 ArrayDeque를 사용하는 것이 좋으며, Thread-safe가 필요한 경우 ConcurrentLinkedQueue를 사용하는 것을 고려할 수 있습니다.

9. 결론 (Conclusion)

Queue는 선입선출 방식의 자료구조로 순서가 중요한 다양한 문제 해결에 필수적입니다. Golang과 Java를 통해 Queue를 직접 구현하고 응용함으로써 자료구조의 개념과 활용법을 깊이 이해할 수 있습니다.