[Swift] Linked List를 이용한 Queue 구현

Queue는 먼저 입력된 데이터가 먼저 출력되는 자료구조이다. 이러한 특성을 선입선출(FIFO: First-In Frist-Out)이라고 한다. 이러한 개념은 일상생활에서 쉽게 찾아볼 수 있기 때문에 Queue는 많이 사용되는 자료구조 중 하나이다. 

 

Swift에서는 기본적으로 Queue를 제공해 주지는 않아서 별도로 구현해 주어야 한다. 다양한 방법으로 다양한 종류의 Queue를 구현할 수 있는데, Array를 이용한 Queue의 구조를 살펴보자. 

 

먼저 Array를 이용하여 일렬로 쭉 늘어선 모양의 선형 Queue를 구현할 수 있다.

Queue에서 가장 먼저 입력된 데이터를 출력하는 함수를 pop이라고 하겠다. pop을 하는 방법에는 크게 두 가지가 있다. 

배열로 구현된 Queue의 pop 연산1

첫 번째로 pop 연산 시에 Array의 첫 번째 원소를 반환하고 해당 자리를 그다음 원소들이 순서대로 채우는 방법이다. 해당 연산은 낭비되는 메모리는 없지만, 삭제 연산 시에 빈번한 데이터의 이동이 일어나는 단점이 있다. 

배열로 구현된 Queue의 pop 연산2

두 번째로 Array의 양 끝단에 index를 두어, 데이터 입/출력 시에 해당 index를 이동시키는 방법이다. 첫 번째 방법과 달리 삭제 시에 빈번한 데이터 이동이 일어나진 않지만 반환된 원소는 사용이 안 되는 메모리로 남게 되고, 입출력 시에 index를 관리해줘야 하는 번거로움이 있다. 

 

각각 장/단점이 있지만 일반적으로 메모리보다 연산 속도에 관심이 많아 두 번째 방법이 많이 사용된다. 그리고 두 번째 방법의 메모리에 대한 단점 원형 Queue를 이용해 어느 정도 극복이 가능하다. 원형 Queue는 말 그대로 마지막 원소 다음이 첫 번째 원소로 이어지는 Queue를 말한다. 해당 Queue를 이용하여 메모리의 낭비를 어느 정도 극복할 수 있지만, Queue의 크기를 선언 시에 정해야 하고, 해당 크기 이상의 데이터는 저장을 못하는 문제가 있다. 

 

이렇듯 Array로 Queue를 구현하게 되면 다양한 문제들이 존재한다. 이러한 문제들을 해결하기 위해 이번 포스팅에서는 Linked List를 이용하여 Queue를 구현해 보고자 한다. 

 

Linked List를 이용한 Queue의 구조는 다음과 같다. 

Linked List를 이용한 Queue의 구조

배열과 달리 각각의 Node에 데이터가 저장되어 있으며 다음 Node를 가리키고 있으며, 처음과 끝 Node는 각각 fisrt와 last로 표시하였다.

Linked List를 이용한 Queue의 pop 연산

그리고 pop연산 수행 시에는 first를 첫 번째 Node가 가리키는 Node로 옮긴다. 그러면 기존에 첫 번째 Node는 참조되지 않으므로 자동으로 소멸된다. 

 

이러한 구조를 Swift를 통해 구현하면 다음과 같다. 이전 포스팅에서 LinkedList를 구현해 주었기 때문에 해당 클래스를 상속하여 구현해 주었다. (https://taeminator1.tistory.com/36)

class Queue<Element>: LinkedList<Element> {
    @discardableResult func pop() -> Node<Element>? {
        guard !isEmpty() else {               
            return nil
        }
        
        let result: Node? = first
        first = first?.getNext()
        count -= 1
        
        return result
    }
}

Queue가 비어있는 경우 nil을 반환하기 위해 반환 값을 Optional로 선언하였다. 그리고 반환 값을 먼저 임시로 저장한 뒤에 first를 기존의 첫 번째 노드가 가리키는 Node로 변경해 주었다. 

 

해당 클래스를 테스트하기 위해 다음과 같이 작성하여 실행하였다. 

var queue: Queue = Queue<Int>(Node(1))
queue.append(Node(2))
queue.append(Node(3))

print(queue[0]!.data)                                           // 1
print(queue[1]!.data)                                           // 2
print(queue[2]!.data)                                           // 3

print("pop: \(queue.pop()!.data)")                              // Node with 1 has been expired.
                                                                // pop: 1

print(queue[0]!.data)                                           // 2
print(queue[1]!.data)                                           // 3

queue.append(Node(4))

print(queue[0]!.data)                                           // 2
print(queue[1]!.data)                                           // 3
print(queue[2]!.data)                                           // 4

눈여겨볼 곳은 단연 pop연산이 실행되는 부분이다. 연산이 실행되면 기존에 첫 번째 Node는 누구에게서도 참조되지 않으므로 자동으로 소멸되는 것을 확인할 수 있다.