[자료구조] Queue

이전에 올린 스택의 경우 Swift에서는 배열을 스택처럼 사용할 수 있었다. (append(), removeLast() 등의 메서드를 사용해서)

그러나 큐의 경우 Swift에서 따로 지원하지 않기 때문에 만약 알고리즘 문제를 풀면서 큐를 사용할 일이 있다면 따로 만들어서 사용해야 한다.

 

큐는 선입선출 FIFO 구조이다. 

• enqueue : 맨 뒤에 원소 추가
• dequeue : 맨 앞에 원소 삭제
• peek : 첫 번째 위치한 데이터 읽기
• clear : 큐 재설정해 빈 상태되게 하기
• count : 큐에 있는 요소의 수 반환
• isEmpty
• isFull

 

구현

구조체와 배열로 아래와 같이 구현할 수 있다.

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

// 사용을 한다면 아래와 같이 할 수 있다. 
var myQueue = Queue<Int>()
myQueue.enqueue(127)
myQueue.dequeue()

 

enqueue의 경우는 맨 뒤에 원소를 추가하는 것이므로 append()를 통해서 추가할 수 있다.

그러나, dequeue를 removeFirst()로 풀면 시간 초과가 된다. (사용할 수 있으나)

 

앞서 스택의 경우 마지막을 삭제하는 것은 배열의 마지막을 삭제하는 경우였다.

배열에서 가장 마지막을 삭제하는 것은 본인만 제거 되면 끝나는 것이므로 O(1)로 문제가 되지 않는다.

 

그러나 큐의 경우 마지막이 아니라 처음 element를 삭제하게 된다.

배열에서 가장 첫번째의 element가 삭제가 된다면 그 뒤의 element가 하나씩 앞으로 당겨져야 한다. 그래서 O(n)이라는 시간 복잡도가 나온다.

*배열은 연속적으로 데이터가 들어간 구조이기 때문에

= 그러므로 큐의 Head의 element를 삭제하는 dequeue의 작업은 오버헤드가 크다.

 

---

그래서 이를 개선하는 방법으로 포인터 개념을 적용할 수 있다.

(개선이 필요한 부분은 dequeue이다. dequeue를 할 때 배열을 앞당겨주는 작업을 최소하하는 것이다.)

 

🟢 개선 원리

실제 배열의 head를 삭제하는 것이 아니라 현재 head를 가리키고 있는 포인터를 변경시켜서 dequeue가 호출될 때마다 하던 배열의 삭제 작업을 하지 않는 것이다. 

대신에 더이상 필요하지 않는 dequeue된 element는 nil로 만들어주는 것이다.

 

3	4	7	10	8
0	1	2	3	4

위의 데이터 구조에서 3~은 데이터를 의미하고, 0~은 인덱스를 의미한다.

 

이 때, head라는 것을 두고 dequeue시 반환되어야 하는 element의 index를 갖고 있는 것이다.

그러면 dequeue가 불릴 때마다 element를 삭제하고 나머지 element를 당겨오는 과정이 없기 때문에 오버헤드가 발생하지 않는다.

(= 시간 복잡도가 O(1)이 된다.)

 

 

🔵 개선 코드

개선된 코드를 보면 아래와 같다.

(다른 블로그를 보면 구조체 등을 사용해서 구현하는데 ... 그것을 이해하는 것보다 후리가 소개해준 초이의 블로그를 보는 것이 더 쉬워서 .. 그것을 바탕으로 구현할 것이다.)

 

출처 : 초이님 블로그 

 

var queue: [Int] = []

이런 배열을 만들어두고 구현해보자.

 

enqueue

queue.append(1)

enqueue의 경우 그냥 append를 해주면 된다.

배열의 마지막 위치에 원소가 추가되고 O(1)의 시간 복잡도를 가진다.

 

 

dequeue

queue.removeFirst()

가장 앞에 있는 것이 나오므로 removeFirst()를 하면 된다.

하지만 이것이 배열을 다시 재배치해야하므로 시간복잡도에서 문제가 나타난다.

 

위에서 말한 포인터 개념을 바탕으로 해결해보자.

var queue: [Int] = [0, 1, 2, 3, 4]

이렇게 Int형 배열을 만들 수 있고, 포인터 역할을 하는 head 변수(Int형 변수)를 만들어보자.

var head: Int = 0

 

그러면 현재 상황은 아래와 같다.

0

1

2

3

4

⬆️

head (= 0)

 

 

그리고 이제 dequeue를 해준다면 다음과 같다.

nil

1

2

3

4

⬆️ head (= 1)

가장 앞의 원소를 nil로 만들고 head를 옆으로 옮겨주면 된다.

queue[head] = nil // 맨 앞 원소를 nil로 만들기
head += 1 // head 옮겨주기

 

이 때 주의할 것이 있다.

queue가 비어 있을 때를 주의해야 한다. 그래서 앞의 원소를 nil로 하고 head를 옮기기 전에 guard 구문으로 확인해야하는 작업이 있다.

guard let element = queue[head] else { return nil } // 
queue[head] = nil // 맨 앞 원소를 nil로 만들기
head += 1 // head 옮겨주기
return element

값이 존재할 때까지 앞의 원소를 nil로 만들고 head을 옮겨주면서 값이 있는 index를 찾았을 때 그 때의 인덱스를 n이라고 하고, dequeue된 n개의 데이터를 removeFirst(n)하면 된다.