Swift 자료구조

배열

- 데이터를 순차적으로 저장하는 구조

- 인덱스를 사용해 특정위치의 요소에 접근할 수 있음

- 특정 인덱스를 통해 접근하는 것은 빠르지만(O(1)), 삽입/삭제 과정은 오래걸린다(O(n))

 

예시

 

 

큐

선입선출의 형식인 데이터구조 (FIFO)

- Enqueue: 큐 맨 뒤에 요소 추가

- Dequeue: 큐 맨 앞의 데이터를 반환

- Peek: Front에 위치한 데이터 값 반환

- Front: 큐의 앞부분 (가장 먼저 들어온 데이터가 위치함)

- Rear: 큐의 뒷부분 ( 가장 최근에 들어온 데이터가 위치함)

 

dequeue하는 과정에서 removeFirst() 메소드를 이용한다면 시간복잡도가 O(n)이 걸리게된다.

이를 해결하기위해 index를 이용해 front부분을 확인하여 데이터를 반환하는 방법도 있지만,

reversed()도 O(1)이 걸리므로 이 방법을 사용했다.

import Foundation

struct Queue<T> {
    var elements: [T] = []
    
    // 큐 갯수
    var count: Int {
        return elements.count
    }
    // 큐의 가장 먼저 나갈 데이터
    var peek: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements[0]
        }
    }
    // 큐의 앞부분
    var front: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements[0]
        }
    }
    // 큐의 뒷부분
    var rear: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements.last!
        }
    }
    // 큐 비어있는지
    var isEmpty: Bool {
        return elements.isEmpty
    }
    // 큐 데이터 삽입
    mutating func enqueue(element: T) {
        elements.append(element)
    }
    // 큐 데이터 삭제(반환)
    mutating func dequeue() -> T? {
        if elements.isEmpty {
            return nil
        } else {
            var arr = Array(elements.reversed())
            let returnValue = arr.popLast()
            elements = Array(arr.reversed())
            return returnValue
        }
    }
}