Chapter 9: Queue Challenges

Challenge 1: Stack vs. Queue

스택(Stack)과 큐(Queue)의 차이점을 설명한다. 각 자료 구조(Data Structure)에  대한 두 가지 실제 예제를 제시한다.

 

Solution

Queue는 선입선출(first-in-first-out) 이다. 먼저 삽입된 것이 반드시 먼저 제거된다. Queue는 후면에서 삽입되고, 전면에서 제거된다. Queue의 실제 예시는 다음과 같다.

1. 영화관에서 줄 서기 : 티켓 구입 시 줄을 서서 순서대로 구매한다.
2. 프린터 : 먼저 작업 queue에 올라간 파일부터 순차적으로 인쇄된다.

Stack은 후입선출(last-in-first-out) 이다. 나중에 삽입된 것이 반드시 먼저 제거된다. Stack은 상단에서 삽입되고, 상단에서 제거된다. Stack의 실제 예시는 다음과 같다.

1. 쌓인 접시 : 접시를 위로 차근차근 쌓으며, 사용할 때는 위에서 부터 순서대로 꺼낸다.
2. 취소 기능 : 컴퓨터의 많은 프로그램에서, Ctrl-Z를 사용하면 가장 최근 작업이 취소된다.

---

Challenge 2: Step-by-step Diagrams

다음과 같은 큐(Queue)가 있다.

다음 코드가 큐(Queue)에 어떤 영향을 미치는지 단계별 다이어그램(diagram)을 그려본다.

enqueue("R")
enqueue("O")
dequeue()
enqueue("C")
dequeue()
dequeue()
enqueue("K")

다음과 같은 큐(Queue)에서 실행한다.

1. Array-based
2. Linked list
3. Ring buffer
4. Stack based

배열(Array)과 링 버퍼(Ring buffer)의 초기 크기는 5라고 가정한다.

 

Solution

Array

배열(Array)이 가득찼을때 새 요소를 추가하려 하면, 기존의 요소가 복사된 두 배 용량의 새 배열을 생성한다.

 

Linked list

 

Ring buffer

 

Double stack

---

Challenge 3: Whose turn is it?

친구들과 Monopoly 게임을 하고 있다. 자신의 차례(turn)를 알려주는 관리자(organizer)를 만든다. 준수해야할 프로토콜(protocol)은 다음과 같다.

public protocol BoardGameManager {
    associatedtype Player
    
    mutating func nextPlayer() -> Player?
}

 

Solution

BoardGameManager는 누구의 차례인가만 신경쓰면 되므로, 큐(Queue) 자료구조(Data Structure)를 사용해 구현하기 적합하다.

extension QueueArray: BoardGameManager { //Queue가 BoardGameManager를 구현하기 적합하다.
    public typealias Player = T //typealias의 매개변수를 T로 설정한다.
    
    public mutating func nextPlayer() -> T? {
        guard let person = dequeue() else { //dequeue로 다음 Player를 가져온다.
            return nil //Queue가 비어 있다면 nil을 반환한다.
        }
        
        enqueue(person) 
        //dequeue한 Player를 Queue에 넣는다. 순서대로 진행되면 다시 차례가 오게 된다.
        
        return person //nextPlayer 반환
    }
}

시간 복잡도는 선택한 Queue의 구현에 따라 달라진다. Array기반 Queue의 경우에는 전체 시간복잡도가 O(n) 이다. dequeue 시, 첫 번째 요소를 제거하면서 다음 요소들을 모두 하나씩 이동시켜야 하므로 O(n) 이 된다. 구현을 확인해 본다.

var queue = QueueArray<String>()
queue.enqueue("Vincent")
queue.enqueue("Remel")
queue.enqueue("Lukiih")
queue.enqueue("Allison")
print(queue) // ["Vincent", "Remel", "Lukiih", "Allison"]

print("===== boardgame =======")
queue.nextPlayer()
print(queue) // ["Remel", "Lukiih", "Allison", "Vincent"]
queue.nextPlayer()
print(queue) // ["Lukiih", "Allison", "Vincent", "Remel"]
queue.nextPlayer()
print(queue) // ["Allison", "Vincent", "Remel", "Lukiih"]
queue.nextPlayer()
print(queue) // ["Vincent", "Remel", "Lukiih", "Allison"]

---

Challenge 4: Reverse Queue

큐(Queue)를 반전(reverse)시키는 메서드를 구현한다.

extension QueueArray {
    func reversed() -> QueueArray {
        var queue = self
        // Solution here.
        
        return queue   
    }
}

 

Solution

Queue는 FIFO(first-in-first-out) 이지만, Stack은 LIFO(last-in-first-out)이다. Stack을 사용하여 Queue를 reverse 할 수 있다. Queue의 모든 요소를 Stack에 삽입하고, 다시 Stack의 모든 요소를 pop하면 reverse가 구현된다. Queue를 어떤 방법으로 구현했는지는 중요하지 않다(Array로 구현하든, LinkedList로 구현하든 등). Queue의 특성으로 일반화할 수 있다.

extension QueueArray {
    func reversed() -> QueueArray {
        var queue = self //Queue를 복사한다.
        var stack = Stack<T>() //Stack을 생성한다.
        
        while let element = queue.dequeue() { 
            //Queue의 모든 요소를 dequeue 해, Stack에 push 한다.
            stack.push(element)
        }
        
        while let element = stack.pop() { 
            //Stack의 모든 요소를 pop 해, Queue에 enqueue 한다.
            queue.enqueue(element)
        }
        
        return queue //reverse 된 Queue를 반환한다.
    }
}

전체적인 시간복잡도(time complexity)는 O(n) 이다. Queue에서 요소를 제거할 때, Stack에서 요소를 제거할 때, 총 2 번 looop를 사용한다. 구현을 확인해 본다.

var queue = QueueArray<String>()
queue.enqueue("1")
queue.enqueue("21")
queue.enqueue("18")
queue.enqueue("42")

print("before: \(queue)")
// before: ["1", "21", "18", "42"]
print("after: \(queue.reversed())")
// after: ["42", "18", "21", "1"]

---

Challenge 5: Double-ended Queue

Double-ended Queue는 이름에서도 알 수 있듯이 요소를 앞(front), 뒤(back)로 추가하거나 제거할 수 있는 Queue이다.

• Queue(FIFO)를 사용해, 후면에서 요소를 추가하고, 전면에서 제거할 수 있다.
• Stack(LIFO)를 사용해, 후면에서 요소를 추가하고, 후면에서 제거할 수 있다.

Deque는 Stack과 Queue에서 동시에 고려할 수 있다. 자료 구조(Data structure) 구축에 도움이 되는 Dequeue 프로토콜(protocol)이 제공된다. 또, deque가 앞 또는 뒤에서 요소를 추가하는지 제거하는지 여부를 설명하기 위한 Direction 열거형(enum)이 제공된다.

 

Note:

DoubleLinkedList에는 속성과 함수가 하나씩 추가 되었다.

• double-linked list에서 tail 요소를 얻기 위해 last 속성이 추가 되었다.
• double-linked list의 전면에 요소를 추가하기 위해 prepend(_:)함수가 추가 되었다.

enum Direction { //전면, 후면에서 요소를 추가, 제거 여부를 표현하기 위한 열거형
    case front
    case back
}

protocol Deque { //Deque protocol
    associatedtype Element
    
    var isEmpty: Bool { get }
    
    func peek(from direction: Direction) -> Element?
    mutating func enqueue(_ element: Element, to direction: Direction) -> Bool
    mutating func dequeue(from direction: Direction) -> Element?
}

 

Solution

Deque에는 Queue와 Stack의 일반적인 연산들이 정의되어 있다. 이를 구현하는 방법은 여러가지 있지만, 여기서는 이중 연결 리스트(doubly linked-list)를 사용한다. 먼저, 이중 연결 리스트(doubly linked-list)에 Deque 프로토콜(protocol)을 채택한다.

class DequeDoubleLinkedList<Element>: Deque {
    private var list = DoublyLinkedList<Element>()
    
    public init() {}
}

Deque 프로토콜(protocol)을 구현해야 한다. 먼저 Linked List가 비어 있는 지 확인하는 isEmpty를 작성한다. 이는 O(1) 작업이다.

extension DequeDoubleLinkedList {
    var isEmpty: Bool { //LinkedList가 비어 있는 지 확인한다.
        list.isEmpty
    }
}

다음으로, Deque의 앞 또는 뒤의 값을 확인할 수 있는 방법이 필요하다.

extension DequeDoubleLinkedList {
    func peek(from direction: Direction) -> Element? { 
        //Deque의 양 방향에서 peek할 수 있어야 한다.
        switch direction {
        case .front:
            return list.first?.value
        case .back:
            return list.last?.value
        }
    }
}

first와 last의 값을 확인하면 된다. 이는 head와 tail만 확인하면 되므로 O(1) 연산이다. 이제, 앞이나 뒤에소 요소를 추가하는 방법이 필요하다.

extension DequeDoubleLinkedList {
    func enqueue(_ element: Element, to direction: Direction) -> Bool { 
        //Deque의 양 방향에서 enqueue할 수 있어야 한다.
        switch direction {
        case .front:
            list.prepend(element) //head
        case .back:
            list.append(element) //tail
        }
        
        return true
    }
}

 

1. Front : list의 전면에 요소를 추가한다. LinkedList는 새 node를 head로 업데이트 한다.
2. Back : list의 후면에 요소를 추가한다. LinkedList는 새 node를 tail로 업데이트 한다.

head, tail 포인터를 업데이트 하기만 하면 되므로 O(1) 작업이다. 요소를 추가했으므로, 제거하는 방법도 있어야 한다.

extension DequeDoubleLinkedList {
    func dequeue(from direction: Direction) -> Element? {
        let element: Element?
        switch direction {
        case .front:
            guard let first = list.first else { return nil } //head
            element = list.remove(first)
        case .back:
            guard let last = list.last else { return nil } //tail
            element = list.remove(last)
        }
        
        return element
    }
}

dequeue 작업은 간단하다. head와 tail에 대한 참조가 있으므로, 해당 노드의 previous 와 next 참조를 해제하면 된다.

1. Front : list에서 head node(첫 노드)를 가져와 제거한다.
2. Back : list에서 tail node(마지막 노드)를 가져와 제거한다.

enqueue(_:)와 유사하게, dequeue는 O(1) 작업이다. 마지막으로 CustomStringConvertible를 구현한다.

extension DequeDoubleLinkedList: CustomStringConvertible {
    public var description: String {
        String(describing: list)
    }
}

테스트를 위한 코드를 작성한다.

let deque = DequeDoubleLinkedList<Int>()
deque.enqueue(1, to: .back)
deque.enqueue(2, to: .back)
deque.enqueue(3, to: .back)
deque.enqueue(4, to: .back)

print(deque)
// 1 -> 2 -> 3 -> 4 -> end

deque.enqueue(5, to: .front)

print(deque)
// 5 -> 1 -> 2 -> 3 -> 4 -> end

deque.dequeue(from: .back)
deque.dequeue(from: .back)
deque.dequeue(from: .back)
deque.dequeue(from: .front)
deque.dequeue(from: .front)
deque.dequeue(from: .front)

print(deque)
// end