Swift로 구현한 Queue

안녕하세요. Swift언어를 이용해서 큐(Queue)를 구현해 보겠습니다.

Queue 개념

---

큐는 선입선출, FIFO(Fast In First Out)의 특징을 가진 자료구조로 처음에 넣은 데이터를 처음에 꺼낸다는 특징을 가지고 있습니다.

Queue 연산

---

• front: 큐의 가장 첫 번째 데이터를 확인합니다. 큐가 비어있을 경우 nil을 반환합니다.
• deququ(): 큐의 가장 첫 번째 데이터를 반환합니다.
• enququ(): 큐에 데이터를 집어넣습니다.
• isEmpty: 큐가 비어있는지 여부를 Boolean으로 반환합니다.

Queue 구현

---

큐의 종류에는 선형과 환형이 있다고 하는데요. 각각 장단점이 있는 방식으로 이번 시간에는 간단하게 배열을 이용한 선형 큐를 소개하려고 합니다.
배열을 이용한 선형 큐의 경우 데이터 삽입의 경우 append를 사용하므로 O(1)의 시간복잡도를 가집니다.
그런데 데이터를 꺼낼 때 removeFirst를 많이 사용하는데 시간복잡도가 O(n)으로 효율이 떨어집니다.
이 시간복잡도를 줄이기 위해 커서를 많이 사용하는데요.
deququ 데이터를 꺼낼 때 배열의 첫 번째를 삭제하고 위치를 재조정하는 게 아닌 현재 큐의 첫 번째 데이터를 가리키는 index 값을 가지고 있는 변수(커서)를 이용해 데이터를 삭제할 때 현재 커서가 가리키는 요소를 nil 처리 한 후 커서 값을 증가시켜 다음 데이터를 가리키게 합니다. 이렇게 할 경우 O(1)의 시간복잡도를 가지게 됩니다.

시간복잡도가 줄어들었으니 좋아 보이지만 단점으로는 배열의 크기가 계속 증가하기 때문에 메모리 사용량이 많아진다는 단점이 있습니다.
그래서 배열의 크기가 일정 크기 이상 증가하면 removeFirst를 통해 크기를 줄여주는 로직을 추가하여 구현해 봤습니다.

우선 기본 형태를 보시면

struct Queue<T> {
  var array: [T?] = []
  var head = 0

  var count: Int {
    return array.count - head
  }

  var isEmpty: Bool {
    return count == 0
  }

  var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

Queue 구조체를 생성하고 어떤 타입도 지원할 수 있도록 제네릭 형태로 선언해 주었습니다.

• array: 데이터를 담아둘 배열
• head: 현재 큐의 첫 번째 데이터를 가르키는 index
• count: 현재 Queue에 담긴 데이터의 갯수를 반환합니다.
• isEmpty: Queue가 비어있는지 여부를 Bool타입으로 반환합니다.
• front: Queue의 첫 번째 데이터를 옵셔널 형태로 반환합니다.
  

삽입(enququ) 함수로 O(1)의 시간 복잡도를 가지고 있습니다.

mutating func enququ(_ element: T) {
  array.append(element)
}

• 배열 마지막에 요소를 추가해 줍니다.
  
  

front(커서가 가리키는 데이터 반환) 함수로 O(1)의 시간 복잡도를 가지고 있습니다.

var front: T? {
  if isEmpty {
    return nil
  } else {
      return array[head]
  }
}

• 리턴 타입을 옵셔널로 구현하여 array배열이 비어있을 경우 nil을 반환 합니다.
  
  

deququ(처음에 삽입한 데이터 삭제) 함수로 O(1)의 시간 복잡도를 가지고 있습니다.

mutating func deququ() -> T? {
  guard head < array.count, let element = array[head] else { return nil }
        
  array[head] = nil
  head += 1
        
  // head의 위치가 queue 길이의 25% 이상일 경우
  let percentage = Double(head) / Double(array.count)
  if array.count > 50 && percentage > 0.25 {
    array.removeFirst(head)
    head = 0
  }
        
  return element
}

• head의 값이 array의 범위를 벗어나거나, head가 가리키는 데이터가 nil일 경우 nil을 반환합니다.
  • 아닐 경우 element 반환
• 현재 head가 가리키는 데이터를 nil로 변환하고 head를 1 증가시킵니다.
• 큐의 길이에 대한 head의 위치를 계산하여 지정한 범위를 넘으면 removeFirst 를 이용해 요소가 nil인 부분을 제거합니다.

전체 소스 코드

---

struct Queue<T> {
  var array: [T?] = []
  var head = 0
    
  var count: Int {
    return array.count - head
  }
    
  var isEmpty: Bool {
    return count == 0
  }
    
  mutating func enququ(_ element: T) {
    array.append(element)
  }
    
  mutating func deququ() -> T? {
    guard head < array.count, let element = array[head] else { return nil }
        
    array[head] = nil
    head += 1
        
    // head의 위치가 queue 길이의 25% 이상일 경우
    let percentage = Double(head) / Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }
        
    return element
  }
    
  var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

배열로 선형 큐를 구현해 보면서 이것저것 자료를 찾아봤었는데 이렇게 커서를 이용하여 평소 삭제할 때 O(1)를 유지하고 일정 길이를 넘어갈 때 removeFirst를 해준다는 부분이 합리적이란 생각이 들어서 이렇게 구현해 봤습니다.
그리고 생각보다 큐를 구현하는 방식이 많다는걸 알게 되어 다음엔 다른 방식으로 큐를 소개해 보겠습니다.