스위프트로 구현하는 자료구조 3: 큐(Queue)

큐 (Queue)

큐는 FIFO(First In First Out)의 특성을 가지는 자료구조입니다. 이름처럼 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 특징을 가지고 있습니다. 스위프트에서는 배열에서 removeFirst를 지원하긴 하지만,

이렇게 시간복잡도는 O(n)이라서, 동작만 FIFO일 뿐, 삭제에 O(1)을 보장하는 큐가 될 수는 없습니다. 그래서 이 포스트에서는 링크드 리스트를 사용해서 큐를 구현하도록 하겠습니다.

 

뼈대 만들기

var list = TwoPointerLinkedList<T>()
    
init(_ elements: [T] = []) {
    for element in elements {
        list.add(node: Node(data: element))
    }
}
    
var count : Int {
    return list.count
}
var isEmpty : Bool {
    return list.head == nil
}
var front: T? {
    return list.front?.data
}
var back: T? {
    return list.back?.data
}

먼저 기본적인 프로퍼티와 생성자는 이렇게 구성했습니다. TwoPointerLinkedList는 head, tail 두 개의 포인터로 링크드 리스트의 가장 앞과 뒤를 가리키게 하는 링크드 리스트 자료구조입니다.

 

생성자에서는 만약에 배열이 한 번에 들어오면 순서대로 링크드 리스트에 추가해주는 로직을 넣어두었고, count 프로퍼티는 노드의 개수를, isEmpty 프로퍼티는 head 포인터가 비어있는지를 통해 값을 반환하도록 구성했습니다.

 

링크드 리스트

큐를 만들기 위해서 만든 링크드 리스트는 이렇습니다! 링크드 리스트의 구현과 동작방식은 https://jeonyeohun.tistory.com/320 여기에 더 자세히 설명되어 있습니다!

import Foundation
 
struct TwoPointerLinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?
    var count: Int = 0
    
    var front: Node<T>? {
        return head
    }
    var back: Node<T>? {
        return tail
    }
    
    mutating func add(node: Node<T>) {
        if self.head == nil {
            self.head = node
            self.tail = node
        } else {
            self.tail?.next = node
            self.tail = node
        }
        self.count += 1
    }
    mutating func removeFirst() -> Node<T>? {
        guard head != nil else {
            self.clear()
            return nil
        }
        let deleted = self.head
        self.head = head?.next
        self.count -= 1
        
        if head == nil {
            self.clear()
        }
        return deleted
    }
    mutating func clear() {
        self.head = nil
        self.tail = nil
    }
}

기존 링크드 리스트와 거의 동일하지만, clear 메서드를 통해 모든 노드를 한번에 해제할 수 있게 하고, 노드의 개수를 탐색없이 확인할 수 있도록 하는 count 프로퍼티와 가장 앞 노드와 가장 뒤 노드를 쉽게 확인할 수 있는 front, back 프로퍼티를 추가했습니다.

삽입(push) - O(1)

삽입 연산은 기존의 링크드 리스트의 추가 연산을 그대로 사용할 수 있습니다.

    mutating func push(_ element: T) {
        list.add(node: Node(data: element))
    }

이번에는 큐를 좀 더 범용적으로 사용할 수 있게, 노드를 외부에서 만들어서 넣는 것이 아니라 큐 자료구조에서 자체적으로 만들어서 링크드 리스트에 주입하는 방식으로 구성해보았습니다.

 

리스트 내부에는,

mutating func add(node: Node<T>) {
    if self.head == nil {
        self.head = node
        self.tail = node
    } else {
        self.tail?.next = node
        self.tail = node
    }
    self.count += 1
}

이렇게 새로운 노드를 tail 뒤에 붙여주거나, 리스트가 비어있는 경우에는 추가해주는 로직과 노드의 개수를 늘려주는 로직이 들어가있습니다. 별도의 탐색과정 없이 tail로 찾아가 뒤에 노드를 추가해주는 방식이기 때문에 O(1)의 시간복잡도가 보장됩니다.

 

삭제(pop) - O(1)

삭제 연산은 링크드 리스트에서 가장 앞 노드를 반환하고 지우는 방식으로 구현되어 있는데요,

이렇게 리스트가 있을 때, 

현재 head 가 가리키는 값을 변수에 임시로 저장해 메모리에서 해제되지 않도록 강한 참조를 해주고,

head 포인터를 한 칸 앞으로 이동시켜서 리스트에서 가장 앞에 있던 노드를 제외시켜줍니다. 그리고 임시로 저장했던 노드를 그대로 반환하면 pop 연산이 완성됩니다. 이렇게 하면 탐색 없이 곧바로 첫번째 노드를 지우고 반환하니 O(1)의 시간복잡도가 보장됩니다.

 

mutating func removeFirst() -> Node<T>? {
    guard head != nil else {
        self.clear()
        return nil
    }
    let deleted = self.head
    self.head = head?.next
    self.count -= 1
    
    if head == nil {
        self.clear()
    }
    return deleted
}

 

전체 코드

	import Foundation
	struct Queue<T> {
	var list = TwoPointerLinkedList<T>()
	init(_ elements: [T] = []) {
	for element in elements {
	list.add(node: Node(data: element))
	}
	}
	var count : Int {
	return list.count
	}
	var isEmpty : Bool {
	return list.head == nil
	}
	var front: T? {
	return list.front?.data
	}
	var back: T? {
	return list.back?.data
	}
	mutating func clear () {
	list.clear()
	}
	mutating func pop() -> T? {
	return list.removeFirst()?.data
	}
	mutating func push(_ element: T) {
	list.add(node: Node(data: element))
	}
	}

view raw Queue.swift hosted with ❤ by GitHub

 

 

GitHub - jeonyeohun/Data-Structures-In-Swift: 👷🏻‍♂️ STL 왜 없어.. 스위프트로 구현하는 자료구조

자료구조 시리즈의 코드들은 이 레포에서 모두 확인할 수 있어요!