기초 데이터 구조

스택(Stack)

• LIFO (Last In First Out)구조 나타냄

메서드

• push: 스택의 상단에 요소를 추가
• pop: 스택의 상단에서 요소를 삭제 후 반환
• peek: 스택의 상단에서 요소를 반환
• count: 스택에 포함된 요소의 수를 반환
• isEmpty: 스택에 포함된 요소가 없으면 true를 반환
• isFull: 스택의 요소수가 정해져 있는 경우, 스택이 꽉 찼으면 true를 반환
• capacity: 스택의 용량을 가져오거나 설정하기 위한 프로퍼티

struct Stack<T> {
    private var elements: [T] = []
    mutating func push(_ element: T) {
        self.elements.append(element)
    }
    mutating func pop() -> T? {
        return self.elements.popLast()
    }
    func peek() -> T? {
        return self.elements.last
    }
    var isEmpty: Bool { return self.elements.isEmpty }
    var count: Int { return self.elements.count }
    var capacity: Int {
        get { self.elements.capacity }
        set { self.elements.reserveCapacity(newValue) }
    }
    func isFull() -> Bool {
        return self.capacity == self.count
    }
}

배열 형태로 초기화

extension Stack: ExpressibleByArrayLiteral { // 배열형태로 초기화
    public init(arrayLiteral elements: T...) {
        self.init(elements: elements)
    }
}

반복문 순환 가능

extension Stack: Sequence, IteratorProtocol { // 순환 가능
    mutating func next() -> T? {
        return self.elements.popLast()
    }
}

큐(Queue)

• FIFO (First In First Out)구조 나타냄

메서드

• enqueue: 큐의 맨 뒤에 요소 추가
• dequeue: 큐의 맨 앞의 요소를 삭제 후 반환
• front: 큐의 맨 앞의 요소를 반환
• clear: 큐를 재설정해 빈 상태로 만듦
• count: 큐에 포함된 요소의 수를 반환
• isEmpty: 큐에 포함된 요소가 없으면 true를 반환
• isFull: 큐의 요소수가 정해져 있는 경우, 큐가 꽉 찼으면 true를 반환
• capacity: 큐의 용량을 가져오거나 설정하기 위한 프로퍼티

struct Queue<T> {
    private var elements: [T] = []
    mutating func enqueue(_ element: T) {
        self.elements.append(element)
    }
    mutating func dequeue() -> T? {
        if self.isEmpty() { return nil }
        return self.elements.removeFirst()
    }
    func front() -> T? {
        return self.elements.first
    }
    mutating func clear() {
        self.elements.removeAll()
    }
    var isEmpty: Bool { return self.elements.isEmpty }
    var count: Int { return self.elements.count }
    var capacity: Int {
        get { return self.elements.capacity }
        set { self.elements.reserveCapacity(newValue) }
    }
    func isFull() -> Bool {
        return self.capacity == self.count
    }
}

배열 형태로 초기화

extension Queue: ExpressibleByArrayLiteral { // 배열형태로 초기화
    public init(arrayLiteral elements: T...) {
        self.init(elements: elements)
    }
}

반복문 순환 가능

extension Queue: Sequence,IteratorProtocol { // 순환 가능
    mutating func next() -> T? {
        if self.elements.isEmpty { return nil }
        return self.elements.removeFirst()
    }
}

우선순위 큐(Priority Queue)

• 기본적인 형태는 큐와 비슷하지만 큐에서 빠져나오는 조건인 우선순위 값을 가지고 있다
• 우선순위 큐를 그림으로 표현할때는 이진 탐색 트리를 그리면 된다

메서드

• push: 우선순위를 고려해 큐에 요소를 추가함
• pop: 큐에서 가장 높은 순위의 요소를 삭제 후 반환
• peek: 큐에서 가장 높은 순위의 요소를 반환
• clear: 큐를 재설정해 빈 상태로 만듦
• count: 큐에 포함된 요소의 수를 반환
• isEmpty: 큐에 포함된 요소가 없으면 true를 반환

struct PriorityQueue<T: Comparable> {
    private var heap: [T] = [] // 실제 큐
    private let ordered: (T, T) -> Bool // 어떤 우선 순위로 할지
    init() {
        // 아래 쪽의 초기화 참고
    }
    var count: Int { return self.heap.count }
    var isEmpty: Bool { return self.heap.isEmpty }
    mutating func push(_ element: T) {
        self.heap.append(element)
        swim(heap.count - 1) // 우선순위에 따라 위치를 잡아줌
    }
    mutating func pop() -> T? {
        if self.heap.isEmpty { return nil }
        if self.heap.count == 1 { return self.heap.removeFirst() }
        self.heap.swapAt(0, self.heap.count-1)
        let value = self.heap.removeLast()
        sink(0)
        return value
    }
    func peek() -> T? {
        return self.heap.first
    }
    mutating func clear() {
        self.heap.removeAll()
    }
    mutating func sink() {
        // 아래 쪽 sink 함수 참고
    }
    mutating func swim() {
        // 아래 쪽 swim 함수 참고
    }
}

초기화

• sink를 실행하기 위한 i의 값이 heap.count/2 - 1 인 이유 : 리프 노드를 제외한 마지막 인덱스
• 리프를 제외한 마지막 인덱스 부터 위로 올라가면서 정렬

상세 설명

1. 리프를 제외한 마지막 노드의 인덱스(x), 리프 포함 제일 마지막 노드의 인덱스(count - 1)
2. 리프를 제외한 마지막 노드는 제일 마지막 노드의 부모 노드이다 (부모의 인덱스 = (자식의 인덱스 -1 ) / 2) : Swim 함수에 설명 있음
3. 따라서 x = ((count - 1) - 1) / 2
4. 2x = count - 2 -> 2(x+1) = count -> x+1 = count/2 -> x = count/2-1
5. 즉, 리프 노드를 제외한 마지막 노드의 인덱스 = 전체 개수 / 2 -1

init(ascending: Bool = false, startingValues: [T] = []){
    //우선순위의 종류를 선택
    if ascending { ordered = { $0 > $1 } } // 여기선 값이 큰쪽이 높음
    else { ordered = { $0 < $1 } } // 여기선 값이 낮은쪽이 높음

    heap = startingValues // 초기의 큐를 생성
    var i = heap.count/2 - 1
    while i >= 0 {
        sink(i) // 우선순위에 따라 위치를 잡아줌
        i -= 1
    }
}

Sink 함수

• pop() 함수, init() 에서 실행
• while문의 조건이 2*index+1 인 이유 : 왼쪽 자식이 있으면 자신은 리프 노드가 아니다 (리프 노드가 되면 비교할 이유가 없음)
• 0번 인덱스부터 시작해서 리프 노드가 되거나 자신이 자식이 될 수 없을 때까지 실행
• 실행 하면서 자신과 자식중에 우선순위가 더 작은 값이 자식이 됨
• 자식의 인덱스 = 현재 인덱스 * 2 + 1 (만약 오른쪽 자식이 왼쪽 보다 크면 + 1 한번 더)
• ex. 4번 인덱스의 자식 = 4 * 2 + 1 (+1) = 9(10)
• => 삭제를 진행하면 마지막 값이 젤 위로가니 0번 부터 아래로 이동

mutating func sink(_ index: Int) {
    var index = index
    while 2 * index + 1 < self.heap.count {
        var j = 2 * index + 1
        if j < (self.heap.count - 1) && ordered(heap[j],heap[j+1]) {
            j += 1
        }
        if !ordered(heap[index],heap[j]) { break } // 바꿔야하는지 판단
        self.heap.swapAt(index, j)
        index = j
    }
}

Swim 함수

• push() 함수에서 실행
• 입력을 받은 index 부터 시작해서 0번 인덱스가 되거나 자신이 부모가 될 수 없을 때까지 실행
• 실행하면서 자신과 부모중에 우선순위가 더 높은 값이 부모가 됨
• 부모의 인덱스 = (현재 인덱스 - 1) / 2
• ex. 11, 12 번 인덱스의 부모 = (11,12 - 1 ) / 2 = 5
• => 삽입을 진행하면 마지막에 값이 들어가니 마지막 인덱스 부터 위로 이동

mutating func swim(_ index: Int) {
    var index = index
    while index > 0 && ordered(heap[(index - 1)/2], heap[index]) {
        self.heap.swapAt((index - 1)/2, index)
        index = (index - 1)/2
    }
}