[Swift] 자료구조 - Queue
Queue
Stack과 상반되는 녀석이라고 생각한 요놈
게임쪽에서 일 할 때 Queue는 좀 많이 사용했던것 같아요
캐릭터의 대화에서 한 글자씩 나오도록 할 때 Queue를 이용하여서
만들었던 기억이 있답니다
예전에 큐를 공부하면서 기억남은것들은
선형큐도 있지만 원형큐 등등 있다는걸 배웠던걸로 기억하는데여
우선 원형큐를 구현하기 위해서는 head와 tail을 기억하고 있어야합니다
그렇게 해야 원형을 유지할 수 있기 때문이죠 번호가 부여된 강강 술래 너낌스..
근데 Swift에서 Queue를 지원하지 않더라구요
시스템적으로 DispatchQueue는 있으면서.. 왜 없니...?
그래서 직접 구조체로 하단의 코드로 만들 수 있답니다 :)
두 가지 버전으로 만들어 보았습니당
우선 사용해 볼 건
SimpleQueue로 구현해 보겠습니다
두번째 버전은
시간 복잡도 개선 버전의
queue를 만들었습니다
비슷한 예시 두가지를 만들어보았어요
이러한 예시로 확인할 수 있는건
enqueue를 하게되면 마지막 인덱스 뒤에 들어가게되고
dequeue를 하게되면 제일 앞에있는 인덱스가 사라지게됩니다
이걸 우리는 FIFO : First In First Out 먼저 들어간 오브젝트가 제일 먼저 나간다
라고 합니다!
stack과는 다르죠? stack경우는 나중에 들어간 녀석이 제일 빨리 나오는데 ㅎㅎ
배열을enqueue / dequeue / front(peek) 시간복잡도로 나타내면
O(1)이라고 할 수 있다
하지만 dequeue의 시간복잡도를 O(1)이라고 했지만
제일 처음 인덱스를 삭제하고 앞당기기 때문에
당겨지는 과정 때문에 O(n)이라고 할 수 있기 때문에
이러한 과정에서 오버헤드가 발생할 수 있답니다
그래서 이러한 현상이 발생하지 않도록
큐 구현에서 링크드 리스트를 사용해서 요소를 저장하고
첫번째 요소를 제거하게되면 O(1)만큼의 시간 복잡도가 소요된답니다
but
큐에서 특정 요소를 찾는다고하면
시간 복잡도가 O(n) 입니다
왜냐?
크기만큼 인덱스를 다 돌아다니며 검색해야하기 때문이죠!
추후 배울 링크드리스트에서 배우겠지만
미리 코드만 살짝 보고 간다면
// 노드 클래스 정의
public class Node<T> {
var value: T
var next: Node<T>?
init(_ value: T) {
self.value = value
}
}
// 큐 구조체 정의
public struct Queue<T> {
private var front: Node<T>? // 큐의 맨 앞
private var rear: Node<T>? // 큐의 맨 뒤
// 큐가 비어있는지 확인하는 프로퍼티
public var isEmpty: Bool {
return front == nil
}
// 큐에 있는 요소의 수를 확인하는 프로퍼티
public var count: Int {
var current = front
var count = 0
// 큐의 맨 앞부터 끝까지 탐색하면서 요소의 수를 셈
while current != nil {
count += 1
current = current?.next
}
return count
}
// 큐에 요소를 추가하는 메서드
public mutating func enqueue(_ element: T) {
let newNode = Node(element)
// 큐가 비어있으면 맨 앞과 맨 뒤가 새 노드를 가리킴
if front == nil {
front = newNode
rear = newNode
} else {
// 큐가 비어있지 않으면 맨 뒤의 다음 노드로 새 노드를 지정하고, 맨 뒤를 새 노드로 업데이트
rear?.next = newNode
rear = newNode
}
}
// 큐에서 요소를 제거하고 반환하는 메서드
public mutating func dequeue() -> T? {
// 큐의 맨 앞의 노드를 꺼냄
guard let currentFront = front else {
return nil
}
// 큐의 맨 앞을 다음 노드로 업데이트
front = currentFront.next
// 만약 큐가 비어있게 되면 맨 뒤도 nil로 업데이트
if front == nil {
rear = nil
}
return currentFront.value
}
// 큐의 맨 앞에 있는 요소를 확인하는 메서드
public func peek() -> T? {
return front?.value
}
}
// 예제 사용
var myQueue = Queue<Int>()
// 큐에 요소 추가
myQueue.enqueue(1)
myQueue.enqueue(2)
myQueue.enqueue(3)
// 큐의 요소 수 출력
print("Queue Count: \(myQueue.count)") // Output: Queue Count: 3
// 큐의 맨 앞에 있는 요소 확인
if let frontElement = myQueue.peek() {
print("Front element: \(frontElement)") // Output: Front element: 1
}
// 큐에서 요소를 제거하고 출력
while let dequeuedElement = myQueue.dequeue() {
print("Dequeued element: \(dequeuedElement)")
}
// 큐의 요소 수 출력
print("Queue Count: \(myQueue.count)") // Output: Queue Count: 0
두 번째 예시를 살펴봅시다
시간 복잡도를 개선하여 작성된 코드입니다
배열의 길이가 50개 넘거나 삭제된 비율이 25%넘어가면 큐를 재 조정한답니다
removefirst대신 nil로 초기화 해버리기 때문에 앞당길 작업을 일정 조건 동안은
작업하지 않아도 됩니다
마지막으로 원형큐를 구현해보고자 합니다
public struct CircularQueue<T> {
private var elements: [T?]
private var head: Int = 0
private var tail: Int = 0
private var capacity: Int
// 큐의 초기화
public init(capacity: Int) {
self.capacity = max(capacity, 1) // 최소 크기는 1로 설정
self.elements = Array(repeating: nil, count: self.capacity)
}
// 큐가 비어있는지 확인하는 프로퍼티
public var isEmpty: Bool {
return head == tail && elements[head] == nil
}
// 큐가 가득 찼는지 확인하는 프로퍼티
public var isFull: Bool {
let nextIndex = (tail + 1) % capacity
return nextIndex == head
}
// 현재 큐에 있는 요소의 수를 계산하는 프로퍼티
public var count: Int {
if head <= tail {
return tail - head
} else {
return capacity - head + tail
}
}
// 큐에 요소를 추가하는 메서드
public mutating func enqueue(_ element: T) {
guard !isFull else {
// 큐가 가득 찼을 경우 요소를 추가하지 않음
return
}
elements[tail] = element
tail = (tail + 1) % capacity
}
// 큐에서 요소를 제거하고 반환하는 메서드
public mutating func dequeue() -> T? {
guard !isEmpty, let element = elements[head] else {
// 큐가 비어있을 경우 또는 head에 해당하는 요소가 nil일 경우 nil 반환
return nil
}
elements[head] = nil
head = (head + 1) % capacity
return element
}
// 큐의 맨 앞에 있는 요소를 확인하는 메서드
public func peek() -> T? {
return isEmpty ? nil : elements[head]
}
}
// 예제 사용
var circularQueue = CircularQueue<Int>(capacity: 5)
circularQueue.enqueue(1)
circularQueue.enqueue(2)
circularQueue.enqueue(3)
print("Queue Count: \(circularQueue.count)") // Output: Queue Count: 3
if let frontElement = circularQueue.peek() {
print("Front element: \(frontElement)") // Output: Front element: 1
}
while let dequeuedElement = circularQueue.dequeue() {
print("Dequeued element: \(dequeuedElement)")
}
print("Queue Count: \(circularQueue.count)") // Output: Queue Count: 0
위에서 말했다시피 번호부여된 강강술래라고 생각하시면 됩니다
선형 큐의 문제점을 보완한 큐 입니당
맨 끝까지 데이터가 차고 맨 앞에 공간이 있담녀 맨 앞에 데이터를 넣는 형식입니다
그래서 맨뒤와 맨 앞의 요소가 연결되어 원형이라고 불러요
Swift 언어는 주로 애플의 플랫폼에서 사용되므로, Swift로 작성된 애플리케이션은 macOS, iOS, watchOS, tvOS 등의 운영체제에서 동작합니다. 여러 운영체제에서 활용되는 여러 시나리오에서 Swift Queue를 찾을 수 있습니다. 아래는 몇 가지 예시입니다:
멀티스레드 환경에서의 비동기 프로그래밍:Swift에서의 GCD(Grand Central Dispatch)는 멀티스레딩을 지원하는데, 이 때 큐가 사용됩니다.
백그라운드에서 수행되는 비동기 작업들이나 메인 스레드에서 수행되기를 기다리는 작업 등을 큐를 통해 관리합니다.
애플리케이션 이벤트 처리:애플리케이션에서 발생하는 이벤트나 작업들은 큐를 통해 관리될 수 있습니다.
예를 들어 사용자 입력, 네트워크 응답, 데이터베이스 작업 등은 큐를 활용하여 비동기적으로 처리될 수 있습니다.
애플리케이션의 데이터 처리 및 업데이트:애플리케이션에서 데이터의 큐를 사용하여 처리하거나 업데이트하는 경우가 있습니다.
예를 들어 큐를 활용하여 데이터를 비동기적으로 불러오거나 업데이트하는 작업을 관리할 수 있습니다.
프로듀서-컨슈머 모델:큐는 프로듀서-컨슈머 모델에서 사용될 수 있습니다. 여러 스레드 간에 데이터를 안전하게 전달하고 처리하기 위해 큐를 활용할 수 있습니다.작업 큐 및 비동기 처리:비동기 작업이나 백그라운드 작업을 처리할 때 큐가 사용됩니다.
예를 들어, 이미지 다운로드, 파일 처리, 데이터 동기화 등을 비동기적으로 큐를 통해 수행할 수 있습니다.애플리케이션의 이벤트 처리 및 태스크 스케줄링:애플리케이션에서의 이벤트 처리나 특정 작업을 예약하고 실행하기 위해 큐를 활용할 수 있습니다.
-gpt-
❤️잘못된 부분은 알려주시면 감사하겠습니다❤️
⭐️참고 사이트⭐️
https://github.com/kodecocodes/swift-algorithm-club/blob/master/Queue/Queue-Optimized.swift