[자료구조] 2. Queue(큐)랑 친해지고 구현하기

자료구조 두 번째 시간을 맞이하다니,,👏

오늘은 Queue랑 친해져 보고 구현해 보는 시간 가져보겠습니닷

---

Queue ⛓️

Queue는 사실 굉장히 많이 들어봤눈데

Swift에서는 동시성에서 다루는 DispatchQueue 가 있져

바로 이 DispatchQueue의 Queue가 오늘 배울 자료구조 Queue라고 함

근데 Queue도 많이 사용하기는 했지만 뜻을 정확히 몰라서 찾아보니까

순서대로 줄을 서는 대기열이라고 함!

티켓 같은 거 살 때 줄 서 있는 것을 상상해 보면 가장 먼저 줄 선사람이 가장 먼저 티켓을 사서 줄에서 빠져나가죠잉

그것이 바로 Queue의 특성입니다. FIFO(First In, First Out) 선입선출 구조‼️

 

FIFO, 선입선출 구조! 가장 먼저 들어온것부터 제거된다

 

Stack에 push와 pop이 있다면, Queue에는 Enqueue와 Dequeue가 있다.

Enqueue는 큐에 데이터가 추가되는 것이고 Dequeue는 큐에서 데이터가 제거되는 것을 말함!

그리고 Stack에서와 다른 점은 스택은 가장 마지막에 추가된 데이터가 가장 중요하지만 큐에서는 큐의 맨 앞과 맨 끝 이 두 지점이 중요하다. 

그래서 큐의 가장 앞 인덱스를 front, Head라고 말하고 가장 뒤를 back, tail이라고 말한다. 

그래서 Dequeue가 되는 부분은 head, Enqueue가 되는 부분은 tail 부분임!

 

---

 

Let's implement a stack🚀‼️

Queue도 스택처럼 배열로 구현해 볼 수 있다.

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

 

📍 Queue라는 구조체에 Generic 데이터를 담을 수 있는 queue라는 배열을 생성한다. 

📍 스택과 똑같이 큐에 데이터가 몇 개 있는지 알 수 있는 count와 큐에 데이터가 있는지 없는지 확인하는 isEmpty 속성을 각각 배열의 계산 속성으로 구현해주었댜

 

📍 func enqueue(_ element: Element)는 큐에 데이터를 추가하는 함수이다. 파라미터로 받는 element를 queue 배열에 append 해주었다. 배열 끝에 append 하기 때문에 시간복잡도는 O(1)이다.

📍 func dequeue()는 큐에서 데이터를 제거하는 함수이다. queue 배열에 요소가 없을 수 있기 때문에 옵셔널로 리턴한다. 만약 큐가 비어있으면 nil을 리턴하고 큐에 데이터가 있으면 가장 첫 번째 요소를 제거하기 위해 removeFirst() 함수를 사용한다. 

 

그런데 removaFirst()는 스택과는 다르게 가장 마지막 데이터를 제거하는 것이 아니라 가장 첫번째 요소를 제거한다. 

그렇게 되면 큐의 데이터들이 앞으로 하나씩 옮겨지는 과정이 생긴다.

1번 데이터가 디큐되니까 앞으로 하나씩 옮겨지는 과정 발생!

 

그렇기 때문에 removeFirst 메서드로 dequeue를 하게 되면 시간복잡도가 O(n)이 되어버려여려려~~~

 

‼️그래서 시간 복잡도를 줄인 더 효율적인 Dequeue 방법을 구현할 수 있음‼️

 

removeFirst()로 맨 앞의 데이터를 제거하는 대신에 맨 앞 데이터를 nil로 변경하는 거임!

그리고 head를 추가해 준다!! head는 큐의 가장 앞부분을 가리키게 된다.

이제 dequeue를 하면 데이터가 제거되는 것이 아니라 이 추가된 head가 그다음 인덱스로 옮겨지게 되면서 head가 가리키는 지점의 데이터가 dequeue(데이터가 nil로 변경) 되는 방법이다.

 

dequeue되면서 데이터는 nil로 변경되고 head가 다음 인덱스로 옮겨진다.

 

코드로 구현해 보면

struct Queue2<Element> {
    var queue: [Element?] = []
    var head: Int = 0 // ⭐️추가⭐️
    
    var count: Int {
        return queue.count
    }
    
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    mutating func enqueue(_ element: Element) {
        queue.append(element)
    }
    
    mutating func dequeue() -> Element? {
        guard head <= count, let element = queue[head] else { return nil }
        queue[head] = nil
        head += 1
        return element
    }
}

 

이제 queue에는 nil값도 들어가게 되기 때문에 queue의 타입을 [Element?] 옵셔널 배열로 변경해 준다.

그리고 Int 타입의 head를 추가해 준다. 이제 dequeue 될 때마다 이 head의 값을 1씩 올려줄 것이다.

그리고 다른 것은 똑같고 우리는 dequeue 함수에 주목하면 된닷!!

 

🔎 함수를 보자면, 일단 guard 문을 사용해서 head가 count보다 작은지 즉, head가 현재 유효한 인덱스인지를 확인한다. 그리고 queue[head]가 nil이 아닌 실제 값이 있는 요소인지 확인해서 element에 할당한다. 만약 head가 큐의 데이터 개수보다 더 높은 인덱스를 가지고 queue [head]에 값이 nil이라면 바로 nil을 리턴하고 함수가 종료된다. 

 

🔎 만약 head도 유효한 인덱스이고 element도 유효한 값이라면 queue[head]를 nil로 변경한다. 위의 이미지를 예로 들자면, 현재 head가 0(index 값)이고 queue[0] 이 nil이 아닌 "1" 이니까 queue[0] 에 "1" 을 nil로 할당해 주는 것이다. 그렇게 해서 큐의 가장 맨 앞의 데이터를 제거하지 않고 nil로 만들어 준다. 

 

🔎 그 후에 head의 값을 1 증가시켜 준다. 그래서 head가 가리키는 index의 값은 1이 되는 것이다. 이 상태에서 dequeue를 하게 되면 "2"가 nil이 되고 head는 index 2를 가리켜서 "3" 위치에 갈 것이다. 그리고 nil로 변경된 값을 리턴해준다.

 

소들님 블로그를 참고해 보면 head += 1 작업 후에 nil로 바뀐 dequeue 된 데이터들을 계속 가지고 있을 수가 없으니 설정한 임계점에 도달하면 이 nil 값들을 다 제거하는 코드도 추가되어 있다.

 mutating func dequeue() -> Element? {
        guard head < count, let element = queue[head] else { return nil }
        queue[head] = nil
        head += 1
        
        // 이부분!
        if head > 10 {
            queue.removeFirst(head)
            head = 0
        }
        return element
  }

 

나는 일단 10으로 설정했는데 이건 설정하기 나름인 듯!

그래서 head가 10을 초과하면, 아마 11부터가 되겠죠잉 head가 11이 되면 removeFirst(_ k: Int) 함수를 이용해서 맨 앞에서부터 head 개를 지울 수가 있다.  그리고 head를 다시 0으로 돌려놓는닷!!

 

결론적으로!

이 방법을 사용하면 맨 앞 데이터가 삭제되지 않아서 앞으로 하나씩 옮겨지는 과정이 필요하지 않으니까

시간복잡도는 O(1)이 됩니닷

 

---

큐,, 스택보다 어렵지만 재밌군여 ,,!!!! 큐큐,,

언능 큐 관련된 코테 문제도 풀어보아서 감을 익혀야겠어요 홍홍

다음에는 어떤 자료구조로 돌아올지,, 일단 돌아오는 것이 목표 🔥

---

📖 reference(늘 감사합니당) ♥️

https://jeong9216.tistory.com/350

[자료구조] Queue(큐) with Swift

https://babbab2.tistory.com/84

Swift) 큐(Queue) 구현 해보기