[Swift] 자료구조 - Queue

Queue

Stack과 상반되는 녀석이라고 생각한 요놈

게임쪽에서 일 할 때 Queue는 좀 많이 사용했던것 같아요
캐릭터의 대화에서 한 글자씩 나오도록 할 때 Queue를 이용하여서
만들었던 기억이 있답니다

 

예전에 큐를 공부하면서 기억남은것들은

선형큐도 있지만 원형큐 등등 있다는걸 배웠던걸로 기억하는데여

우선 원형큐를 구현하기 위해서는 head와 tail을 기억하고 있어야합니다

그렇게 해야 원형을 유지할 수 있기 때문이죠 번호가 부여된 강강 술래 너낌스..

 

근데 Swift에서 Queue를 지원하지 않더라구요

시스템적으로 DispatchQueue는 있으면서.. 왜 없니...?

 

그래서 직접 구조체로 하단의 코드로 만들 수 있답니다 :)

 

 

두 가지 버전으로 만들어 보았습니당

우선 사용해 볼 건 

SimpleQueue로 구현해 보겠습니다

 

 

두번째 버전은

시간 복잡도 개선 버전의

queue를 만들었습니다

 

 

비슷한 예시 두가지를 만들어보았어요

 

이러한 예시로 확인할 수 있는건

enqueue를 하게되면 마지막 인덱스 뒤에 들어가게되고

 

dequeue를 하게되면 제일 앞에있는 인덱스가 사라지게됩니다

 

이걸 우리는 FIFO : First In First Out 먼저 들어간 오브젝트가 제일 먼저 나간다

라고 합니다!

stack과는 다르죠? stack경우는 나중에 들어간 녀석이 제일 빨리 나오는데 ㅎㅎ

 

배열을enqueue / dequeue / front(peek) 시간복잡도로 나타내면 

O(1)이라고 할 수 있다

 

하지만 dequeue의 시간복잡도를 O(1)이라고 했지만

제일 처음 인덱스를 삭제하고 앞당기기 때문에

당겨지는 과정 때문에 O(n)이라고 할 수 있기 때문에

이러한 과정에서 오버헤드가 발생할 수 있답니다

 

그래서 이러한 현상이 발생하지 않도록

큐 구현에서 링크드 리스트를 사용해서 요소를 저장하고

첫번째 요소를 제거하게되면 O(1)만큼의 시간 복잡도가 소요된답니다

 

but

 

큐에서 특정 요소를 찾는다고하면

시간 복잡도가 O(n) 입니다

왜냐?

크기만큼 인덱스를 다 돌아다니며 검색해야하기 때문이죠!

 

추후 배울 링크드리스트에서 배우겠지만

미리 코드만 살짝 보고 간다면

 

// 노드 클래스 정의
public class Node<T> {
    var value: T
    var next: Node<T>?

    init(_ value: T) {
        self.value = value
    }
}

// 큐 구조체 정의
public struct Queue<T> {
    private var front: Node<T>? // 큐의 맨 앞
    private var rear: Node<T>?  // 큐의 맨 뒤

    // 큐가 비어있는지 확인하는 프로퍼티
    public var isEmpty: Bool {
        return front == nil
    }

    // 큐에 있는 요소의 수를 확인하는 프로퍼티
    public var count: Int {
        var current = front
        var count = 0

        // 큐의 맨 앞부터 끝까지 탐색하면서 요소의 수를 셈
        while current != nil {
            count += 1
            current = current?.next
        }

        return count
    }

    // 큐에 요소를 추가하는 메서드
    public mutating func enqueue(_ element: T) {
        let newNode = Node(element)

        // 큐가 비어있으면 맨 앞과 맨 뒤가 새 노드를 가리킴
        if front == nil {
            front = newNode
            rear = newNode
        } else {
            // 큐가 비어있지 않으면 맨 뒤의 다음 노드로 새 노드를 지정하고, 맨 뒤를 새 노드로 업데이트
            rear?.next = newNode
            rear = newNode
        }
    }

    // 큐에서 요소를 제거하고 반환하는 메서드
    public mutating func dequeue() -> T? {
        // 큐의 맨 앞의 노드를 꺼냄
        guard let currentFront = front else {
            return nil
        }

        // 큐의 맨 앞을 다음 노드로 업데이트
        front = currentFront.next

        // 만약 큐가 비어있게 되면 맨 뒤도 nil로 업데이트
        if front == nil {
            rear = nil
        }

        return currentFront.value
    }

    // 큐의 맨 앞에 있는 요소를 확인하는 메서드
    public func peek() -> T? {
        return front?.value
    }
}

// 예제 사용
var myQueue = Queue<Int>()

// 큐에 요소 추가
myQueue.enqueue(1)
myQueue.enqueue(2)
myQueue.enqueue(3)

// 큐의 요소 수 출력
print("Queue Count: \(myQueue.count)") // Output: Queue Count: 3

// 큐의 맨 앞에 있는 요소 확인
if let frontElement = myQueue.peek() {
    print("Front element: \(frontElement)") // Output: Front element: 1
}

// 큐에서 요소를 제거하고 출력
while let dequeuedElement = myQueue.dequeue() {
    print("Dequeued element: \(dequeuedElement)")
}

// 큐의 요소 수 출력
print("Queue Count: \(myQueue.count)") // Output: Queue Count: 0

 

 

 

두 번째 예시를 살펴봅시다

시간 복잡도를 개선하여 작성된 코드입니다

배열의 길이가 50개 넘거나 삭제된 비율이 25%넘어가면 큐를 재 조정한답니다

 

removefirst대신 nil로 초기화 해버리기 때문에 앞당길 작업을 일정 조건 동안은 

작업하지 않아도 됩니다

 

 

 

 

마지막으로 원형큐를 구현해보고자 합니다

public struct CircularQueue<T> {
    private var elements: [T?]
    private var head: Int = 0
    private var tail: Int = 0
    private var capacity: Int

    // 큐의 초기화
    public init(capacity: Int) {
        self.capacity = max(capacity, 1) // 최소 크기는 1로 설정
        self.elements = Array(repeating: nil, count: self.capacity)
    }

    // 큐가 비어있는지 확인하는 프로퍼티
    public var isEmpty: Bool {
        return head == tail && elements[head] == nil
    }

    // 큐가 가득 찼는지 확인하는 프로퍼티
    public var isFull: Bool {
        let nextIndex = (tail + 1) % capacity
        return nextIndex == head
    }

    // 현재 큐에 있는 요소의 수를 계산하는 프로퍼티
    public var count: Int {
        if head <= tail {
            return tail - head
        } else {
            return capacity - head + tail
        }
    }

    // 큐에 요소를 추가하는 메서드
    public mutating func enqueue(_ element: T) {
        guard !isFull else {
            // 큐가 가득 찼을 경우 요소를 추가하지 않음
            return
        }

        elements[tail] = element
        tail = (tail + 1) % capacity
    }

    // 큐에서 요소를 제거하고 반환하는 메서드
    public mutating func dequeue() -> T? {
        guard !isEmpty, let element = elements[head] else {
            // 큐가 비어있을 경우 또는 head에 해당하는 요소가 nil일 경우 nil 반환
            return nil
        }

        elements[head] = nil
        head = (head + 1) % capacity

        return element
    }

    // 큐의 맨 앞에 있는 요소를 확인하는 메서드
    public func peek() -> T? {
        return isEmpty ? nil : elements[head]
    }
}

// 예제 사용
var circularQueue = CircularQueue<Int>(capacity: 5)

circularQueue.enqueue(1)
circularQueue.enqueue(2)
circularQueue.enqueue(3)

print("Queue Count: \(circularQueue.count)") // Output: Queue Count: 3

if let frontElement = circularQueue.peek() {
    print("Front element: \(frontElement)") // Output: Front element: 1
}

while let dequeuedElement = circularQueue.dequeue() {
    print("Dequeued element: \(dequeuedElement)")
}

print("Queue Count: \(circularQueue.count)") // Output: Queue Count: 0

 

 

위에서 말했다시피 번호부여된 강강술래라고 생각하시면 됩니다

선형 큐의 문제점을 보완한 큐 입니당

맨 끝까지 데이터가 차고 맨 앞에 공간이 있담녀 맨 앞에 데이터를 넣는 형식입니다

그래서 맨뒤와 맨 앞의 요소가 연결되어 원형이라고 불러요

 

Swift 언어는 주로 애플의 플랫폼에서 사용되므로, Swift로 작성된 애플리케이션은 macOS, iOS, watchOS, tvOS 등의 운영체제에서 동작합니다. 여러 운영체제에서 활용되는 여러 시나리오에서 Swift Queue를 찾을 수 있습니다. 아래는 몇 가지 예시입니다:
멀티스레드 환경에서의 비동기 프로그래밍:Swift에서의 GCD(Grand Central Dispatch)는 멀티스레딩을 지원하는데, 이 때 큐가 사용됩니다.
백그라운드에서 수행되는 비동기 작업들이나 메인 스레드에서 수행되기를 기다리는 작업 등을 큐를 통해 관리합니다.

애플리케이션 이벤트 처리:애플리케이션에서 발생하는 이벤트나 작업들은 큐를 통해 관리될 수 있습니다.
예를 들어 사용자 입력, 네트워크 응답, 데이터베이스 작업 등은 큐를 활용하여 비동기적으로 처리될 수 있습니다.

애플리케이션의 데이터 처리 및 업데이트:애플리케이션에서 데이터의 큐를 사용하여 처리하거나 업데이트하는 경우가 있습니다.
예를 들어 큐를 활용하여 데이터를 비동기적으로 불러오거나 업데이트하는 작업을 관리할 수 있습니다.

프로듀서-컨슈머 모델:큐는 프로듀서-컨슈머 모델에서 사용될 수 있습니다. 여러 스레드 간에 데이터를 안전하게 전달하고 처리하기 위해 큐를 활용할 수 있습니다.작업 큐 및 비동기 처리:비동기 작업이나 백그라운드 작업을 처리할 때 큐가 사용됩니다.
예를 들어, 이미지 다운로드, 파일 처리, 데이터 동기화 등을 비동기적으로 큐를 통해 수행할 수 있습니다.애플리케이션의 이벤트 처리 및 태스크 스케줄링:애플리케이션에서의 이벤트 처리나 특정 작업을 예약하고 실행하기 위해 큐를 활용할 수 있습니다.

-gpt-

 

 

❤️잘못된 부분은 알려주시면 감사하겠습니다❤️

 

 

⭐️참고 사이트⭐️

https://github.com/kodecocodes/swift-algorithm-club/blob/master/Queue/Queue-Optimized.swift

https://chat.openai.com/