Queue

Queue

Queue는 Stack과 다르게 First - In - First - Out (FIFO)입니다. 먼저 들어간 순서대로 작업해줍니다. James, Tom, Peter, May 순서대로 서있다고 가정했을 때  가장 먼저 서있는 James부터 처리하고 가장 나중에 합류한 TIM은 맨 마지막에 서게 됩니다. 

 

 

 

Queue Protocol, QueueArray 구조체

protocol Queue {
    associatedtype Element
    mutating func enQueue(_ element : Element) -> Bool
    mutating func deQueue() -> Element?
    
    var isEmpty : Bool { get }
    var peek : Element? { get }
}

 

associatedtype 키워드는 Generic타입처럼 일반화 시킨 타입을 지정할 때 사용합니다. 

protocol을 채택한 것의 타입이 Int라면 element를 쓴 메소드들은 모두 Int, String이라면 Stirng이런식으로 변화됩니다. 

Element는 프로토콜을 채택하는 객체가 자신이 원하는 타입의 Queue를 작성할 수 있도록 해주는 것입니다.

enQueue는 새로운 Queue를 추가하고 성공 여부를 반환합니다. 구조체가 Queue프로토콜을 채택할 수 있기 때문에 mutating을 붙여줍니다.

deQueue 가장 앞에있는 Queue를 제거하고 제거한 Queue를 반환합니다. 

isEmpty 프로퍼티는 Queue가 비어있는지 확인하는 읽기전용 프로퍼티 입니다.

peek  프로퍼티는 가장 앞에 있는 Queue가 무엇인지 알려주는 읽기전용 잔용 프로퍼티입니다.

 

struct QueueArray<T> : Queue {
    var array = Array<T>()
    init() {}
    
    var isEmpty : Bool {
        return array.isEmpty
    }
    var peek : T? {
        return array.first
    }
    
    mutating func enQueue(_ element: T) -> Bool {
        array.append(element)
        return true
    }
    
    mutating func deQueue() -> T? {
        return isEmpty ? nil : array.removeFirst()
    }

}

 

Queue프로토콜을 채택하고 array 변수를 만듭니다. 빈 배열을 만들고 제네릭 타입 T로 선언합니다. 프로토콜에서 associatedtype는 프로토콜을 채택한 것의 타입에 따라 변화 하기 떄문에 T 는 Elemnet 타입이 추론됩니다.

프로토콜에서 정의한 메소드와 프로퍼티들을 실행시킵니다. 

array.append의 연산수행속도는  O(1)입니다 표준라이브러리의 Array의 append 는 O(1)로 수행됩니다.이는 Array의 특징을 알아야합니다.

 

 

 

 

배열은 본인이 담고 있는 배열의 공간이 꽉차면 2배의 공간을 만듭니다. 예를들어 TOM, MAY, LISA의 배열을 가진 배열에 JAMES를 넣고자한다면 3개의 2배인 6개로 공간을 확장합니다. 만약 6개가 꽉차면 다시 12개로 늘립니다.

이렇게 append는 O(1) 연산 수행속도를 실행하지만 공간이 꽉찰경우 공간을 늘려야 할때 수행속도는 O(n)이 됩니다.

메소도 deQueue는 만약 비어있다면 nil을 실행하고 값이 있다면 배열의 맨 처음 요소를 제거합니다. 제거 연산 수행속도는 O(n)이 됩니다.

 

 

만약 TOM, MAY, LISA, JAMES라는 배열이 있을 때 TOM을 제거 시키면 MAY, LISA, JAMES는 한칸 씩 앞으로 떙겨야합니다. 이렇게 되면서 수행시간은 O(n)이 됩니다. 

 

extension QueueArray : CustomStringConvertible {
    var description: String {
        return String(describing: array)
    }
}

var queueArray = QueueArray<String>()
queueArray.enQueue("TIM")
queueArray.enQueue("MAY")
queueArray.enQueue("LEE")
print(queueArray) // ["TIM", "MAY", "LEE"]
queueArray.deQueue() // "TIM"
print(queueArray)  // ["MAY", "LEE"]   

 

결과를 확인하기 위해 CustomStringConvertible프로토콜을 통해 원하는 출력내용을 지정해줍니다. array를 출력하게 합니다.

QueueArray를 문자열 타입으로 지정한 뒤 인스턴스를 생성하고 enqueue를 통해 원하는 문자열을 추가시키고 dequeue를 통해 배열의 가장 앞의 문자열을 리턴하고 삭제시킵니다. 

 

Operations	Best case	Woree case
enqueue(_:)	O(1)	O(1)
dequeue(_:)	O(n)	O(n)
Space Complexity	O(n)	O(n)

Doubly LinkedList를 이용한 Queue

기존 Linked List는 자신의 노드 값과 다음 노드의 참조정보만으로 구성되어있었다면 Doubly LinkedList는 이전 노드의 참조정보까지 자기고 있는 형태입니다. 

 

class QueueLinkedList<T> : Queue {
    var list = DoublyLinkedList<T>()
    init () {}

    func enQueue(_ element: T) -> Bool {
        list.append(element)
        return true
    }
    
    func deQueue() -> T? {
        guard !list.isEmpty, let element = list.first else {
            return nil
        }
        return list.remove(element)
    }
    
    var peek: T? {
        return list.first?.value
    }
    
    var isEmpty: Bool {
        return list.isEmpty
    }
}

extension QueueLinkedList : CustomStringConvertible {
    var description: String {
        return String(describing: list)
    }
}

 

QueueLinkedLIst라는 클래스를 만들고 프로토콜 Queue를 채용합니다.

list라는 변수에 Linked List를 연결할 DoublyLinkedList를 넣습니다. 

프로토콜 Queue에서 기본적으로 사용해야할 enQueue, deQueue를 넣습니다. deQueue는 DoublyLinkedList가 비어있지 않을 때 first프로퍼티에 옵셔널로 선언되었던 것을 바인딩으로 해제시키고 DoublyLinkedList의 remove메소드를 통해 값을 제거합니다.

변수 peek 는 가장 앞의 값을 반환하고, 변수 isEmpty는 DoublyLinkedList가 비었는지 확인합니다.

CustomStringConvertible 프로토콜을 통해 각 Node들의 값이 보여질 수 있도록 설정합니다.

 

class Node<T> {
    var value : T
    var next : Node<T>?
    var previous : Node<T>?
    
    init(value : T) {
        self.value = value
    }
}

    extension Node : CustomStringConvertible {
        var description : String {
            return String(describing: value)
        }
}

class DoublyLinkedList<T> {
    var head : Node<T>?
    var tail : Node<T>?
    init () {}
    
    var isEmpty : Bool {
        return head == nil
    }
    
    var first : Node<T>? {
        return head
    }
    
    func append(_ value : T) {
        let newNode = Node(value : value)
        
        guard let tailNode = tail else {
            head = newNode
            tail = newNode
            return
        }
        
        newNode.previous = tailNode
        tailNode.next = newNode
        tail = newNode
    }

    func remove(_ node : Node<T>) -> T {
        let prev = node.previous
        let next = node.next
        
        if let prev = prev {
            prev.next = next
        }else{
            head = next
        }
        next?.previous = prev
        
        if next == nil {
            tail = prev
        }
        node.previous = nil
        node.next = nil
        
        return node.value
            
    }
}

extension DoublyLinkedList : CustomStringConvertible {
    var description : String {
        var string = ""
        var current = head
        while let node = current {
            string.append("\(node.value) -> ")
            current = node.next
        }
        return string + "end"
    }
}

 

DoublyLinkedList 라는 클래스를 만들고 변수 head에는 헤드노드, 변수 tail에는 테일 노드를 넣을 수 있는 변수를 만듭니다. 

isEmpty 변수를 통해 head가 비어있다면 nil을 리턴 시킵니다. (head가 없다면 빈 LinkedList)

변수 first는 head는 항상 첫번째이기 떄문에 head를 리턴시킵니다.

메소드 append를 호출시키고 새로운 Node는 newNode에 넣습니다. guard문을 통해 tailNode가 있다면 tail에 넣고 tailNode가 없다면 head에 새로운 노드인 newNode를 넣고 tail에도 newNode를 넣고 return 합니다. 

newNode.previous = tailNode는 새로 들어온 Node의 previous는 tailNode가 되고 tailNode의 다음은 새로들어온 노드가 되고 tail은 새로들어온 노드로 변경됩니다.

remove메소드는 변수 prev = node.previous로 제거할 노드의 이전 참조 정보가 들어가고 변수 next에는 제거할  노드의 다음 참조정보가 들어갑니다.

만약 prev = prev가 있다면 (제거할 노드의 이전 참조정보가 있다는 것은 첫번째 노드가 아니라는 것) prev.next = next 이고 그게 아니라면 head = next (제거할 노드는 첫번째이기 때문에 head는 첫번째에서 다음 으로 넘어감)

next?.previous = prev는 next는 제거할 노드의 다음을 지칭하고 그 전 노드의 참조정보를 제거합니다

만약 next == nil 이라면 제거할 노드의 다음 노드가 없다면 tail은 nil로 설정해주고 node.previous, node.next 를 nil로 만들고 제거되는 node 값을 리턴합니다.

 

Operations	Best case	Worse case
enqueue(_:)	O(1)	O(1)
dequeue(_:)	O(1)	O(1)
Space Complexity	O(n)	O(n)

Double Stack

Stack 개념을 사용하여 구현하는 방법

Right stack(enqueue) 에 추가할 아이템을 넣고 Left stack(dequeue)에서 Right stack 요소들을 거꾸로 정렬한 뒤  Left stack 에 넣고 순서대로 마지막 값을 제거합니다. 

 

 

protocol Queue {
    associatedtype Element
    mutating func enQueue(_ element : Element) -> Bool
    mutating func deQueue() -> Element?

    var isEmpty : Bool { get }
    var peek : Element? { get }
}

struct QueueDoubleStack<T> : Queue {
    var leftStack = Array<T>()
    var rightStack = Array<T>()
    
    init () {}
    
    mutating func enQueue(_ element : T) -> Bool {
        rightStack.append(element)
        return true
        
    }
    
    mutating func deQueue() -> T? {
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        return leftStack.popLast()
    }
    
    var isEmpty : Bool {
        return leftStack.isEmpty && rightStack.isEmpty
    }
    
    var peek : T? {
        return !leftStack.isEmpty ? leftStack.last : rightStack.first
    }
  
}

extension QueueDoubleStack : CustomStringConvertible {
    var description: String {
        let printList = leftStack.reversed() + rightStack
        return String(describing: printList)
    }
}


var queueStack = QueueDoubleStack<String>()
queueStack.enQueue("TOM")
queueStack.enQueue("MAY")
queueStack.enQueue("JIN")
print(queueStack) // ["TOM", "MAY", "JIN"]
queueStack.deQueue()
print(queueStack) // ["MAY", "JIN"]

 

QueueDoubleStack 구조체를 만들고 leftStack, rightStack 이 될 배열을 만듭니다. enQueue 메소드를 만들고 rightStack에 append를 통해 배열에 들어갈 값을 추가합니다. 

deQueue 라는 메소드를 만들고 만약 leftStack이 비어있다면(비어있을 때만 스택의 값들을 옮기는 과정을 수행함) rightStack에 먼저 들어온 값들을 거꾸로 정렬하여 leftStack으로옮기고 rightStack을 비웁니다. leftStack이 비어있지 않다면 마지막에 마지막 값을 제거합니다. 

isEmpty를 통해  leftStack, rightStack이 모두 비어있는지 확인합니다. 

peek은 가장 먼저 들어온 값을 찾기 위해 leftStack이 비어있는지 확인합니다. 비어있지 않다면 찾기 전 rightStack에서 leftStack으로 이동된 값이 있다는 뜻이기 때문에 leftStack.last(rightStack의 역순이기 때문입니다)를 리턴하고 leftStack이 비어있다면 rightStack.first를 리턴합니다.

 

Operations	Best case	Worse case
enqueue(_:)	O(1)	O(1)
dequeue(_:)	O(1)	O(1)
Space Complexity	O(n)	O(n)

Ring Buffer

 

고정된 크기에 배열을 생성하고 read는 값을 제거, write는 값을 입력합니다. 값을 입력할 때 마다 write는 1개씩 움직입니다. 만약 값을 제거할 경우 read는 1개씩 움직입니다. 배열이 꽉찰경우 다시 배열의 처음으로 돌아와 값을 넣습니다. 

 

struct RingBuffer<T> {
    var array : [T?]
    var readIndex = 0
    var writeIndex = 0
    
    init(count : Int) {
        array = Array<T?>(repeating: nil, count: count)
    }
    
    var first : T? {
    return array[readIndex]
    }
    
    var availableSpaceForReading : Int {
        return writeIndex - readIndex
    }
    
    var isEmpty : Bool {
        return availableSpaceForReading == 0
    }
        
    var availableSpaceForWriting : Int {
        return array.count - availableSpaceForReading
    }
    
    var isFull : Bool {
        return availableSpaceForWriting == 0
    }
    
    mutating func write(_ element : T) -> Bool {
        if !isFull {
            array[writeIndex % array.count] = element
            writeIndex += 1
            return true
        }else {
            return false
        }
    }
    
    mutating func read() -> T? {
        if !isEmpty {
            let element = array[readIndex % array.count]
            readIndex += 1
            return element
        }else{
            return nil
        }
    }
}

 

RingBuffer라는 구조체를 만들고 고정된 크기의 배열을 만들수 있는 변수를 만들고 read, write의 index가 될 프로퍼티를 만듭니다. 

생성자를 만들고 고정된 배열의 크기를 정할 count를 만듭니다. 

first 프로퍼티를 만들고 RingBuffer의 Read인 readIndex를 읽어옵니다(Read는 항상 배열의 맨 처음에 위치)

프로퍼티  availableSpaceForReading 는 제거할 수 있는 갯수를 표현합니다. 

프로퍼티 isEmpty는 writeIndex와 readIndex가 같은 위치면 비어있는 queue입니다. 만약 모든 빈 배열을 다 소모하고 다시 처음으로 돌아온다면 배열을 차있지만 availableSpaceForReading는 0일 수 있지만 뒤에 isfull프로퍼티가 오류를 막습니다. 

availableSpaceForWriting 프로퍼티는 고정된 배열의 크기에 제거 가능한 제거가능한 갯수를 빼면 추가할 수 있는 공간의 개수가 나옵니다.

isFull 프로퍼티는 만약 고정된 배열을 모두 채우면 writeIndex는 맨 처음인 0으로 다시 돌아오게 되고 readIndex와 같이 0이 됩니다.

write라는 메소드를 만들고 만약 isFull이 true이면 false를 리턴하고 isfull이 false이면 값을 넣을 array배열안에 writeIndex 와 고정된 배열크기를 비교한 후 writeIndex를 넣어주고 writeIndex를 1 증가 시킵니다.

read 메소드를 만들고 만약 isEmpty가 true이면 nil을 리턴하고 isEmpty가 false 면 array 배열안에 readIndex와 고정된 배열의 크기를 비교한 후 readIndex를 넣어주고 readIndex 를 1 증가 시킵니다.

 

extension RingBuffer : CustomStringConvertible {
    var description : String {
        let values = (0..<availableSpaceForReading).map {
            String(describing : array[($0 + readIndex) % array.count]!)
        }
        return String(describing: values)
    }
}

 

 

(0..<availableSpaceForReading).map은 0에서 배열에 들어있는 개수까지를 포함한 범위입니다 예를 들어 고정된 배열의 개수가 5개이고 들어있는 배열의 요소의 수가 4개라 했을 때 0..<4(writeIndex - readIndex)이고 $0에 매개변수를 넣을 때 0+0, 0+1, 0+2, 0+3 을 5로 나눈 나머지를 사용합니다. 

인덱스는 0, 1, 2, 3, 이 되고 값은 0, 1, 2, 3, 이 되고 문자열로 변환됩니다. 

 

struct QueueRingBuffer<T> : Queue {
    var ringBuffer : RingBuffer<T>
    init(count : Int) {
        ringBuffer = RingBuffer<T>(count: count)
    }
    
    var isEmpty: Bool {
        return ringBuffer.isEmpty
    }
    
    var peek : T? {
        return ringBuffer.first
    }
    
    mutating func enQueue(_ element: T) -> Bool {
        return ringBuffer.write(element)
    }
    mutating func deQueue() -> T? {
        return isEmpty ? nil : ringBuffer.read()
    }
}

extension QueueRingBuffer : CustomStringConvertible {
    var description: String {
        return String(describing: ringBuffer)
    }
}

 

QueueRingBuffer 구조체를 만들고 RingBuffer인스턴스를 만듭니다. 고정된 배열의 크기를 받아오기 위해 생성자를 통해 만듭니다. 

isEmpty 프로퍼티를 ringBuffer 메소드의 isEmpty를 가져오고 peek 프로퍼티는 ringBuffer메소드의first를 가져옵니다.

메소드 enQueue 안에 ringBuffer 메소드 write를 가져오고 메소드 deQueue 안에 isEmpty가 비었을 경우 nil을 리턴하고 있을경우 ringBuffer 메소드 read를 가져옵니다.

 

var queueBuffer = QueueRingBuffer<Int>(count: 10)

for i in 1...7 {
    queueBuffer.enQueue(i)
}
print(queueBuffer) // ["1", "2", "3", "4", "5", "6", "7"]

for _ in 0..<3 {
    queueBuffer.deQueue()
}
print(queueBuffer) // ["4", "5", "6", "7"]
queueBuffer.enQueue(8)
print(queueBuffer) // ["4", "5", "6", "7", "8"]

 

QueueRingBuffer의 인스턴스를 만들고 고정된 배열 10을 만듭니다. 

for 구문을 통해 1...7을 넣고 0...2 -> 총 3번의 deQueue를 실행시킵니다. 

 

Operations	Best case	Worse case
enqueue(_:)	O(1)	O(1)
dequeue(_:)	O(1)	O(1)
Space Complexity	O(n)	O(n)