[자료구조/Swift] 큐(Queue)

Swift로 직접 자료구조 구현하기 - 큐

✅ 간단하게 알아보는 큐

- 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조로, FIFO(First-In, First-Out), 선입선출 구조 이다.

- 마치 음식점에서 줄섰을 때, 먼저 줄 선 사람부터 식당에 들어가는 것과 같다

- 메소드는 enqueue() : 큐에 데이터를 넣기 / dequeue() : 큐에 데이터를 꺼내기 가 있다.

 

1) 뼈대 잡기

struct Queue<T> {
  var elements:[T] = []

  var isEmpty: Bool {
    return elements.isEmpty
  }

  var size: Int {
    return elements.count
  }
}

 

2) 메소드 추가

- enqueue(), dequeue()

  mutating func enqueue(_ element: T){
    elements.append(element)
  }

  mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    }
    return elements.removeFirst() //선입선출
  }
}

큐 또한 enqueue, dequeue 메소드가 주요 메소드이기에 크게 구현하는 데에 어려움은 없지만, removeFirst() 에서 시간복잡도가 O(n) 이기 때문에 이를 O(1)로 개선할 수 있다. (메모리나 시간이 한정적일 때 제한이 걸릴 수 있음)

 

*시간복잡도가 O(n)인 이유?

- removeFirst() 를 하면, 뒤에 있던 원소들이 맨 앞을 향해 차례대로 이동하는 과정이 있으므로 시간복잡도가 O(n)임

- 그래서 배열의 맨 첫번째를 가리키는 head 원소를 생성하여, removeFirst() 를 실제로 실행하는 것이 아니라 맨 앞의 원소를 nil로 만들고, head 변수의 값을 +1 을 해줌

 

3) dequeue 함수를 더 효율적으로 개선한 메소드

  var head = 0
  
  mutating func dequeue() -> T? {
      guard head <= queue.count, let element = queue[head] else { return nil }
      queue[head] = nil
      head += 1
      return element
  }
 }

- 하지만 이렇게 했을 때, 큐의 마지막 원소를 알아낼 때 조금 까다로운 면이 있기도 하고 (nil인 원소들을 다 거른다음에 맨 마지막 원소를 가져와야함), 스택 2개로 구현한 사례도 있기에 설명을 보고구현해보았다.

 

4) 스택 2개를 이용한 큐

좋은 설명이 있어서 참고해보면 좋을듯 하다.

https://the-brain-of-sic2.tistory.com/entry/%ED%81%90

struct Queue<T> {
  var input = [T]()
  var output = [T]()
  
  var isEmpty : Bool {
      return input.isEmpty && output.isEmpty
  }
  var size: Int {
      return input.count + output.count
  }
  
  mutating func enqueue(element: T) {
      input.append(element)
  }
  
  mutating func dequeue() -> T {
    if output.isEmpty {
        output = input.reversed() //output에 reverse한 배열 넣고 input 비우기
        input.removeAll()
    }
    return output.removeLast()
  }

  var first: T? {
    if isEmpty {
      return nil
    }
    return output.isEmpty ? input.first! : output.last!
  }
  
  var last: T? {
    if isEmpty {
      return nil
    }
    return input.isEmpty ? output.first! : input.last!
  }
}

 

 

 

전체코드 : https://github.com/yurrrri/Swift_DataStructure/blob/main/queue.swift

GitHub - yurrrri/Swift_DataStructure: Swift 알고리즘을 공부하다가 STL이 없어 직접 구현한다,,

https://github.com/yurrrri/Swift_DataStructure/blob/main/queue_doublestack.swift

GitHub - yurrrri/Swift_DataStructure: Swift 알고리즘을 공부하다가 STL이 없어 직접 구현한다,,

 

reference

https://babbab2.tistory.com/84

https://one10004.tistory.com/247

https://the-brain-of-sic2.tistory.com/entry/%ED%81%90