[Swift] 큐(Queue)는 선착순.

큐는 이전에 살펴본 스택과 유사한 자료구조로, FIFO 원칙을 따릅니다.

스택은 가장 나중에 추가된 데이터가 먼저 추출되지만, 큐는 가장 먼저 추가된 데이터가 먼저 추출됩니다.

 

(스택에 대해 아직 잘 모르신다면 공부한 후 다시 오시기를 권장합니다. 이전에 설명한 내용은 간략하게 넘어갑니다! 😎)

[Swift] 스택(Stack)은 프링글스.

 

FIFO는 First In First Out 원칙으로,

데이터를 배열에 들어온 순서대로 추가하고(Enqueue), 가장 먼저 추가된 데이터를 먼저 추출하는 것(Dequeue)을 의미합니다.

 

무슨 말이지 잘 모르겠다면…

 

이 글의 제목처럼 큐는 선착순.을생각하면 쉽습니다!

예를 들어, 뭔가를 선착순으로 구매할 때 새벽에 일찍 나가서 줄을 서는 것과 비슷한 원리입니다.

 

왜냐? 먼저 가야지 먼저 들어갈 수 있으니까요!!

 

이러한 개념을 바탕으로 큐는 FIFO 원칙을 따르는 자료구조로 이해하면 됩니다.

정리하자면!

큐는 enqueue 연산으로 값을 차례대로 삽입하고, dequeue 연산으로 가장 먼저 저장된 값을 삭제하는 기본적인 자료구조를 의미합니다.

---

Swift로 Queue 구현

기본적으로 enqueue와 dequeue 연산을 구현해야 하며, 추가적으로 front, isEmpty, count 연산을 구현하겠습니다.

 

오늘은 코드를 먼저 보겠습니다. 

(해당 코드는 비효율적이라는 것을 먼저 말씀드리며..)

struct Queue<T> {
    private var datas: [T] = []
    
    var count: Int {
        return datas.count
    }
    
    var isEmpty: Bool {
        return datas.isEmpty
    }
    
    
    mutating func enqueue(_ element: T) {
            datas.append(element)
        }
    
    mutating func dequeue() -> T? {
        return isEmpty ? nil : datas.removeFirst()
        }
    
}

 

배열 생성, count, isEmpty, enqueue 메서드는 이전에 소개된 스택에서 사용한 내용과 상당히 유사합니다.

또한, 시간 복잡도 또한 O(1)로 상수 시간에 동작합니다.

 

그러나, dequeue 메서드에서는 새로운 removeFirst() 메서드를 사용하고 있습니다.

이 메서드는 배열의 맨 처음 요소를 삭제하고 해당 요소를 반환합니다.

(리턴 타입도 Self.Element여서, 빈 배열일 경우를 고려해줘야 합니다!)

 

그러나 주의할 점은 이 메서드는 배열의 메모리 앞 부분을 비워버리고, 뒤에 있는 데이터들은 앞으로 이동해야 한다는 점입니다.

따라서, 해당 메서드는 O(n)의 시간 복잡도를 갖기 때문에 효율적이지 않을 수 있습니다.

(이런 과정을 오버헤드라고 부릅니다.)

removeFirst() | Apple Developer Documentation

---

위에서 구현한 큐보다 더 효율적인 코드를 작성해보겠습니다.

이는 dequeue시 배열의 나머지 요소이 이동하는 것을 최소화하면 됩니다.

 

따라서 첫 번째 요소를 삭제하는 방식이 아닌, Head를 도입하여 첫 번째 요소의 인덱스를 관리해주는 방식으로 구현을 해보겠습니다.

물론, 배열은 그대로 유지를 시키겠습니다.

 

그럼 이제 조금 더 효율적인 큐를 확인해보겠습니다.

배열과 head 생성

// 큐의 요소들을 담을 배열, head 인덱스를 유지
private var datas: [T?] = []
private var head: Int = 0

 

제네릭으로 구현된 빈 배열을 생성합니다. 하지만 이번에는 옵셔널 타입으로 생성합니다.

dequeue할 요소들을 실제로 삭제시키는 것이 아닌, nil값으로 교체하여 관리를 할 것이기 때문입니다.

 

또한, head 프로퍼티를 생성하여 첫 번째 요소의 인덱스를 계속해서 관리해줍니다.

삽입 (enqueue) - O(1)

// 큐에 요소를 추가하는 메서드
mutating func enqueue(_ element: T) {
    datas.append(element)
}

 

배열의 삽입(enqueue) 메서드는 스택과 마찬가지로 append(_ newElement: Element) 메서드를 사용하여 데이터를 추가합니다.

이는 배열의 끝에 데이터를 덧붙이는 것으로, 대부분의 경우에는 O(1)의 시간 복잡도를 갖습니다.

(배열의 용량(capacity)가 부족할 때는 O(n)의 시간 복잡도가 발생할 수 있는데, 이것은 스택 글에서 설명 했습니다!)

 

간단하게 설명하면, 현재 배열의 용량이 부족하니까 새로운 배열로 이사를 가야하기 때문입니다.

append(_:) | Apple Developer Documentation

삭제 (dequeue) - O(1)

// 큐에서 요소를 제거하고 반환하는 메서드
mutating func dequeue() -> T? {
    // 큐가 비어있거나 head가 범위를 벗어나면 nil 반환
    guard head < datas.count, let element = datas[head] else { return nil }
    
    datas[head] = nil // head에 해당하는 요소를 nil로 설정
    head += 1 // head를 증가시켜 다음 요소로 이동
    
    let percentage = Double(head) / Double(datas.count)
    
    // head가 배열의 앞부분에 요소가 많이 남아있으면 배열을 정리
    if percentage > 0.25 && head > 50 {
        datas.removeFirst(head) // head 개수만큼 요소를 배열에서 제거
        head = 0
    }
    
    return element
}

 

dequeue 메서드는 삭제할 데이터가 없는데 삭제를 시도하면 동작을 막아야 합니다.

따라서, 큐가 비어있거나 head가 데이터 배열의 범위를 벗어나면 nil을 반환합니다.

 

head가 배열의 count와 같거나 큰 경우는 큐가 모든 데이터를 삭제한 상태를 나타냅니다.

예를 들어, 다음과 같은 큐 상태에서 head가 큐의 count와 같거나 큰 경우에는 해당 큐가 데이터가 없는 상태입니다.

(아래는 count와 head가 4로 같은 상황입니다.)

[nil, nil, nil, nil]
		   head

 

배열의 범위 내에서 dequeue를 수행하면, head 인덱스의 데이터를 nil로 변경하고 head를 다음 인덱스를 가리키도록 +1을 해주면 됩니다. 

 

그러나 이러한 동작만 계속하면 배열은 계속해서 nil로 설정된 데이터를 가지게 되는데, 이는 메모리 낭비로 이어질 수 있습니다. 이를 방지하기 위해 적절한 시점에 dequeue된 자료들을 정리하는 작업을 추가합니다.

 

작업은 환경에 맞추어 적절한 때에 수행되도록 설정되어야 합니다.

 

여기서는 배열에 최소 50개의 요소가 있어야 하며(배열 크기가 작을 경우에는 공간 낭비가 큰 문제가 아니므로 무시할 수 있습니다), 그 중 25% 이상이 사용되지 않는 경우에 해당 부분을 nil로 설정된 데이터들을 제거하는 작업을 수행하도록 구현할 것입니다.

 

마지막으로, 삭제된 데이터를 리턴해주며 메서드를 종료합니다.

---

⭐️⭐️ 주의 ⭐️⭐️

많은 블로그 글에서 head와 count의 값이 같을 때도 메서드를 실행시키는 경우가 많은데 주의하세요!

인덱스는 0부터 시작하고, count는 1부터 시작해서 헷갈릴수 있는데..

(모든 데이터를 dequeue하고 한 번 더 메서드를 실행하면 배열에서 벗어난 인덱스를 입력하여 에러가 발생합니다.)

// 잘못된 코드 예시
guard head <= datas.count, let element = datas[head] else { return nil }

 

조회 (count, isEmpty, front) - O(1)

// 현재 큐에 있는 요소의 개수
var count: Int {
    return datas.count - head
}

// 큐가 비어있는지 여부를 반환
var isEmpty: Bool {
    return count == 0
}

// 현재 큐의 맨 앞에 있는 요소를 반환하는 메서드
func front() -> T? {
    if isEmpty {
        return nil
    } else {
        return datas[head]
    }
}

 

여기도 중요하게 봐주세요! ⭐️⭐️⭐️

(여러 블로그들이 여기를 꽤 틀리신 거 같은데.. 제가 맞겠죠..?ㅎ)

 

많은 분들이 아래 주의 코드를 보시는 것처럼 그냥 큐 배열의 count와 isEmpty 프로퍼티를 이용하시더라고요 ?! 

그러나, 이 경우에는 조금 더 주의가 필요합니다!

 

우리는 현재 큐의 dequeue 메서드를 더 효율적으로 사용하기 위해

데이터를 실제로 배열에서 삭제하는 것이 아니라, nil로 바꾸고 head로 첫 번째 데이터 인덱스를 관리하고 있습니다.

 

그렇기 때문에 datas 배열에는 nil인 데이터들이 존재한다고 생각해야 합니다!

 

배열의 count와 isEmpty 프로퍼티는 nil을 제외하고 생각하지 않기 때문에, 우리는 이 nil로 바뀐 데이터들도 신경 써줘야 합니다.

 

따라서 위의 코드처럼 count를 계산할 때 head를 고려하여 반영해주어야 합니다.

 

아래와 달리 제대로 나오는 것 같죠 ?!

---

⭐️⭐️ 주의 ⭐️⭐️

// 잘못된 코드
public var count: Int {
    return datas.count
}

public var isEmpty: Bool {
    return datas.isEmpty
}

 

이대로 코드를 동작해보면, 값이 제대로 나오지 않습니다!

---

다른 방식으로 Queue 만들기

위에 코드가 아닌, 다른 방식으로도 많이 만드시던데..

저는 일단 참고만 할게요.😅

 

- 두 개의 스택을 이용하여 Queue 구현하기

[자료구조] Swift 로 Queue 구현하기;

 

- 링크드 리스트를 이용해서 구현하기

스위프트로 구현하는 자료구조 3: 큐(Queue)

---

Swift 전체 코드

struct Queue<T> {
    // 큐의 요소들을 담을 배열, head 인덱스를 유지
    private var datas: [T?] = []
    private var head: Int = 0
    
    // 현재 큐에 있는 요소의 개수
    var count: Int {
        return datas.count - head
    }
    
    // 큐가 비어있는지 여부를 반환
    var isEmpty: Bool {
        return count == 0
    }
    
    // 큐에 요소를 추가하는 메서드
    mutating func enqueue(_ element: T) {
        datas.append(element)
    }
    
    // 큐에서 요소를 제거하고 반환하는 메서드
    mutating func dequeue() -> T? {
        // 큐가 비어있거나 head가 범위를 벗어나면 nil 반환
        guard head < datas.count, let element = datas[head] else { return nil }
        
        datas[head] = nil // head에 해당하는 요소를 nil로 설정
        head += 1 // head를 증가시켜 다음 요소로 이동
        
        let percentage = Double(head) / Double(datas.count)
        
        // head가 배열의 앞부분에 요소가 많이 남아있으면 배열을 정리
        if percentage > 0.25 && head > 50 {
            datas.removeFirst(head) // head 개수만큼 요소를 배열에서 제거
            head = 0
        }
        
        return element
    }
    
    // 현재 큐의 맨 앞에 있는 요소를 반환하는 메서드
    func front() -> T? {
        if isEmpty {
            return nil
        } else {
            return datas[head]
        }
    }
}

 

---

마무리

간단히 마무리할 수 있었지만, 코드 작성과 실험을 거쳐보니 예상치 못한 문제가 발생했습니다.

덕분에 다른 블로그에서도 잘못된 내용을 발견할 수 있었습니다!

 

앞으로는 블로그 글을 무조건 믿지 말고 도구로 활용하되, 반드시 정확한 정보인지 확인하는 습관을 갖는 것이 중요해보입니다.

 

우리는 공식 문서를 더 신뢰하고, 정보를 검증하는 과정을 소홀히하지 않아야 합니다. 💡

---

잘못된 내용이나 궁금하신 점이 있다면 댓글 남겨주세요. 🤓

읽어주셔서 감사합니다.

---

📝 참고 자료

한국외대 신찬수 교수님의 Data Structures with Python 강의

[자료구조] Swift로 구현하는 Queue (큐)

Swift) 큐(Queue) 구현 해보기

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