[Algorithm의 모든것] Swift_큐(Queue)

안녕하세요 ~!
지난번에 스택에 대해 알아봤다면 이번엔 그 단짝 친구인 큐에 관해 알아보려고 합니다.

---

큐(Queue)란 ?

큐(Queue)는 먼저 입력된 데이터가 먼저 출력되는 FIFO(First In First Out) 데이터 구조를 나타냅니다.
스택의 예시로는 마트의 계산대가 있습니다. 먼저 계산하러 온 손님이 계산을 끝내고 먼저 나가게 되죠 !
큐도 이와 마찬가지입니다. 먼저 들어온 데이터가 먼저 나가게 되는 구조입니다.

큐의 주된 메소드는 다음과 같습니다.

1. enqueue() : 큐의 맨 뒤에 새로운 요소를 추가
2. dequeue() : 큐의 맨 첫 번째 요소를 제거한 뒤 반환
3. peak() : 큐의 첫 번째 요소를 반환하되, 제거하지는 않음
4. clear() : 큐를 재설정해 빈 상태가 되게 함
5. count : 큐에 있는 요소의 수를 반환
6. isEmpty() : 큐가 비어있으면 true 반환 / 그렇지 않으면 false 반환
7. isFull() : 큐가 꽉 차있으면 true 반환 / 그렇지 않으면 false 반환

서브 메소드는 다음과 같습니다.

1. capacity : 큐 용량을 가져오거나 설정하기 위한 read/write 프로퍼티
2. insert(_: atIndex:) : 큐의 특정 인덱스 위치에 요소를 삽입
3. removeAtIndex(atIndex:) : 큐의 특정 인덱스 위치에 있는 요소를 제거

---

큐(Queue) 구현

public struct Queue<T> {
    private var data = [T]()
    public init() {}
    
    public mutating func enqueue(_ element: T) {
        data.append(element)
    }
    public mutating func dequeue() -> T? {
        return data.removeFirst()
    }
    public func peak() -> T? {
        return data.first
    }
    public mutating func clear() {
        data.removeAll()
    }
    public var count: Int {
        return data.count
    }
    public func isEmpty() -> Bool {
        return data.isEmpty
    }
    public func isFull() -> Bool {
        return count == data.capacity
    }
    
    public var capacity: Int {
        get {
            return data.capacity
        }
        set {
            data.reserveCapacity(newValue)
        }
    }
    public mutating func insert(_ element: T, atIndex: Int) {
        data.insert(element, at: atIndex)
    }
    public mutating func removeAtIndex(atIndex: Int) {
        data.remove(at: atIndex)
    }
}

var myQueue = Queue<Int>()
myQueue.enqueue(1) // myQueue : [1]
myQueue.enqueue(2) // myQueue : [1, 2]
myQueue.enqueue(3) // myQueue : [1, 2, 3]
myQueue.enqueue(4) // myQueue : [1, 2, 3, 4]

let x = myQueue.dequeue() // 1, myQueue : [2, 3, 4]
let y = myQueue.peak() // 2, myQueue : [2, 3, 4]
myQueue.insert(1, atIndex: 0) // 1, myQueue : [1, 2, 3, 4]
myQueue.removeAtIndex(atIndex: 0) // 1, myQueue : [2, 3, 4]

Playground에서 구현해본 Queue입니다.
큐 또한 스택과 마찬가지로 스위프트 표준 라이브러리에서 제공해주는 Array Method 덕분에 쉽게 구현 가능한 것 같습니다 ㅎㅎㅎ !

---

스택과 거의 비슷한 방식이지만, LIFO 구조이냐 FIFO 구조이냐의 차이만 잘 구분하면 스택과 큐도 쉽게 구분될 것 같습니다.
(동전 케이스와 계산대를 잘 기억해주세요 ㅎㅎㅎ)
읽어주셔서 감사합니다 ~ 😊

참고 서적 : 스위프트 데이터 구조와 알고리즘 - 에릭 아자르, 마리오 에귈루즈 알레빅토