[Swift] Queue Struct(구조체)와 Class(클래스) 구현하기!

❗️ 백준 알고리즘 문제를 풀다보니 Swift에는 Queue와 Deque 자료구조가 구현이 안되어있다는 슬픈 소식이..

그래서 공부한 내용을 바탕으로 간단하게 사용하기 위해 Queue에 대해 공부한 내용을 정리해보자!

 

Queue 구조체 구현

// Queue 구조체 구현
struct Queue <T: Equatable> {
    var enqueue:[T] = []
    var dequeue:[T] = []
    
    var count : Int {
        enqueue.count + dequeue.count
    }
    
    var isEmpty : Bool {
        enqueue.isEmpty && dequeue.isEmpty
    }
    
    var first : T?{
        dequeue.isEmpty ? enqueue.first : dequeue.last
    }
    
    var last : T?{
        enqueue.isEmpty ? dequeue.first : enqueue.last
    }
    
    mutating func push(_ value: T){
        enqueue.append(value)
    }
    
    mutating func pop() -> T?{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    
    mutating func removeAll() {
        enqueue.removeAll()
        dequeue.removeAll()
    }
    
    func contains(_ value: T) -> Bool {
        return enqueue.contains(value) || dequeue.contains(value)
    }
}

✅ 위의 Queue는 제네릭 타입으로 어떤 타입이든 정의할 수 있다. 생성할 때 타입을 명시해주면 된다!

Queue 클래스 구현

// Queue 클래스 구현
class Queue <T> {
    var enqueue:[T]
    var dequeue:[T] = []
    
    var count : Int {
        enqueue.count + dequeue.count
    }
    
    var isEmpty : Bool {
        enqueue.isEmpty && dequeue.isEmpty
    }
    
    init(_ queue: [T]) {
        enqueue = queue
    }
    var first : T?{
        dequeue.isEmpty ? enqueue.first : dequeue.last
    }
    
    var last : T?{
        enqueue.isEmpty ? dequeue.first : enqueue.last
    }
    
    func push(_ value: T){
        enqueue.append(value)
    }
    
    func pop() -> T{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()!
    }
    
    func removeAll() {
        enqueue.removeAll()
        dequeue.removeAll()
    }
}

✅ 백준 문제들을 해결하다보니 실제로는 입력받은 배열을 Queue로 바로 생성이 가능할 수 있도록 하는게 편리해 Class 구현까지 했다.

용도에 맞게 Struct와 Class를 사용하면 좋을 듯!

Int형 Queue 생성 방법

구조체

var q = Queue<Int>()
// Int형 Queue 생성

✅ 위의 코드블럭과 같이 [ 구조체이름<자료형>() ] 으로 원하는 자료형 Queue를 구현할 수 있다.

 

클래스

let N = [4,2,3,5]
var queue = Queue(N) // Int형 Queue 생성
print(queue.pop()) // 4

✅ 위의 코드블럭과 같이 Queue(Queue로 만들고 싶은 배열[타입은 제너럴이라 아무 타입도 상관없다!])로 원하는 자료형 Queue를 구현할 수 있다.

🧑‍💻 Queue의 구조 설명

해당 queue는 두 개의 stack으로 구현되어 있다.

1️⃣ enqueue : push를 했을 때 들어오는 stack

2️⃣ dequeue : pop을 할 때 빼내는 stack

두 개의 stack으로 구현하는 이유는 간단하다. removeFirst() 함수를 통해 간단하게 배열로 구현할 수 없기 때문에! (시간복잡도가 O(N)이라 비효율적이다.)

그래서 먼저 push를 했을 땐 enqueue 배열에 집어넣고, pop을 할 때는 enqueue.reversed()를 통해 dequeue에 집어넣는다.

 

그렇게 되면 dequeue.popLast()를 했을 때 뒤집어진 enqueue의 첫번째를 pop하게 되므로 queue의 자료구조에 맞게 선입선출 구조로 구현 할 수 있다!

위의 구조를 똑같이 Class로 만들 수 있지만 Class로 만들게 되면 init() 생성자 함수를 필수로 만들어줘야 하므로 귀찮아서..? 구조체로 만들었다. Class로 만들기 위해서는 enqueue 배열을 초기화하지않고 var enqueue : [T] 로 변수를 생성해준 다음 생성자 함수(init)에서 enqueue = (받은 매개변수 배열) 를 통해 초기화해주면 똑같이 구현할 수 있다!

 

🔥 함수 설명

1️⃣ 연산 프로퍼티 사용(count, isEmpty, first, last)

 var count : Int {
        enqueue.count + dequeue.count
    }

✅ Queue의 count 값을 알려준다. 하나의 Queue에는 두 개의 배열로 구현되어 있으므로, 각 배열의 count를 모두 더해 돌려준다.

var isEmpty : Bool {
        enqueue.isEmpty && dequeue.isEmpty
    }

✅ Queue가 비어있는지 안비어있는지 알려준다. 똑같이 두 개의 배열 모두 비어있는지 확인 후, 둘 다 비어있을 때 true를 돌려준다.

var first : T?{
        dequeue.isEmpty ? enqueue.first : dequeue.last
    }

✅ Queue의 Top(head)이 가리키는 값을 돌려준다. dequeue의 값이 가장 먼저 들어온 값이므로 dequeue가 비어있는지를 확인 후 삼항연산자로 비어있다면 enqueue의 첫 번째 값을, 비어있지 않다면 dequeue의 마지막 값을 돌려준다.

또한 first와 last의 return값이 옵셔널이므로 사용할 때 ! 키워드를 통해 옵셔널을 벗겨주면 된다.

var last : T?{
        enqueue.isEmpty ? dequeue.first : enqueue.last
    }

✅ Queue의 마지막 값을 돌려준다. enqueue에 마지막 값이 가장 마지막에 들어온 값이므로 enqueue가 비어있는지를 확인 후 삼항연산자로 비어있다면 dequeue의 첫번째 값을, 비어있지 않다면 enqueue의 마지막 값을 돌려준다.

first와 마찬가지로 옵셔널 값을 return하므로 ! 키워드를 통해 옵셔널을 벗겨줘야 한다!

 

2️⃣ func(함수) 사용(push, pop, removeAll, contains)

mutating func push(_ value: T){
        enqueue.append(value)
    }

✅ 받은 매개변수 value를 enqueue에 append 함수를 통해 집어넣으면 끝! 단, 구조체 내부에서 데이터를 수정하기 위해서는 mutating 키워드를 사용해야만 한다!

mutating func pop() -> T?{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }

✅ 배열을 두 개 선언해 Queue를 구현한 만큼, pop은 이해를 확실하게 하고 넘어가야 한다고 생각한다!

먼저 pop을 이해하기 위해서는 두 개의 배열의 존재 의미를 이해하고 있어야 한다.

enqueue는 값이 들어오는 배열, dequeue는 값을 빼내는 배열, Queue는 선입선출구조로 먼저 들어온 값이 먼저 나가야 한다는 점만 알고 있다면 이해하기 쉽다!

먼저 dequeue, 즉 값을 빼내는 배열이 비어있는지 확인한다. 만약 값이 있다면 먼저 들어온 값이 존재한다는 뜻이니까 바로 popLast를 통해 dequeue의 마지막 값을 빼내면 된다.

하지만 값이 없다면, enqueue에 있는 값을 dequeue로 옮겨줘야 한다는 뜻이 된다! 따라서 시간복잡도 O(1)에 수렴하는 reversed() 함수를 통해 enqueue의 값을 뒤집어서 dequeue에 넣은 이후, 기존의 값들은 dequeue 배열에 넣었으므로 removeAll()을 통해 비워주면 끝이다.(쓰레기통을 비우는것과 비슷한 개념..?)

그리고 똑같이 dequeue의 마지막 값을 빼내면 된다. 이러나 저러나 dequeue의 값을 빼내니까 코드 마지막엔 늘 dequeue.popLast를 해주면 된다!

mutating func removeAll() {
        enqueue.removeAll()
        dequeue.removeAll()
    }

✅ 두 개의 배열을 모두 비워줘야 removeAll의 정의에 부합하므로 각각 enqueue와 dequeue 모두 removeAll 해주면 된다!

func contains(_ value: T) -> Bool {
        return enqueue.contains(value) || dequeue.contains(value)
    }

✅ 받은 value값이 Queue에 포함이 되어있는지를 알려주는 함수다. 마찬가지로 두개의 배열 모두 하나의 Queue 이므로 두 개의 배열 모두에 value값이 있는지 확인하고 하나의 배열에라도 값이 있다면 Queue에 value값이 있다는 뜻이므로 or 연산자인 || 를 통해 작성해주면 된다!

 

이렇게 Queue의 모든 걸 씹고뜯고맛보고즐겨봤다. 내가 공부하고 이해한 내용을 언제 확인해도 바로 이해할 수 있게 정리했다.

미래에 들어오는 나 또는 모르는 사람들에게 도움이 되기를!