[Data Structure / Algorithms] Queue

전성훈·2023년 11월 1일
Algorithmsdatastructureswift
0

Data Structure-Algorithm

목록 보기
5/35

주제: FIFO의 구조

Queue는 FIFO(First-in-First-out)를 사용하며, 추가된 첫 번째 요소가 항상 처음으로 제거됩니다.

Queue의 작동구조

  • Queue는 나중에 처리해야 할 요소의 순서를 유지할 때 유용합니다.
  • 또한 Queue는 BFS 탐색을 할 때 유용하게 활용할 수 있습니다.
  1. enqueue
    • 요소를 큐의 뒷부분에 삽입합니다.
  2. dequeue
    • 큐의 맨 앞에서 요소를 제거하고 반환합니다
  3. isEmpty
    • 큐가 비어있는지 확인합니다.
  4. peek
    • 큐의 맨 앞에 있는 요소를 제거하지 않고 반환합니다. 
public protocol Queue { 
	associatedtype Element
	
	mutating func enqueue(_ element: Element) -> Bool
	mutating func dequeue() -> Element? 
	
	var isEmpty: Bool { get }
	var peek: Element? { get }
}

Queue 생성의 여러가지 구조

  • 크게 4가지 구조를 활용하여 Queue를 만들 수 있습니다.
    1. 배열을 활용한 큐
    2. 이중연결리스트를 활용한 큐
    3. 링 버퍼를 활용한 큐
    4. 두개의 스택을 활용한 큐

Array-based Queue

  • 연속적이며 순서대로 정렬된 요소 목록을 저장하는 데이터구조인 Array를 활용한 Queue입니다.
  • Enqueue
    • Enqueue 작동은 평균 O(1) 시간 복잡도를 나타냅니다. 왜냐하면 Array 마지막에 요소를 더하기 때문입니다.
    • 하지만 계속해서 값을 더하다가 배열이 가득차게 될 경우, 추가적인 크기를 확장하게 될 것이며 이 연산은 O(n)의 시간이 필요합니다. 이 때 데이터를 할당하게 되면 O(n)의 시간복잡도를 나타냅니다.
    • 그러나 핵심은 이 연산은 자주 발생하지 않는다는 것입니다.
    • 이는 공간이 부족해질 때마다 2배씩 증가하기 때문입니다. 결과적으로, 연산의 분할 상환 비용(평균 비용)을 계산하면, enqueueing이 평균 O(1)임을 알 수 있습니다. 하지만 최악의 경우 성능은 복사가 수행될 때 O(n)이 됩니다.
  • Dequeue
    • queue가 비어있지 않다면, Array 맨 앞 요소를 제거하게 될 것입니다. 맨 앞 요소를 제거하는 연산은 O(n) 시간 복잡도를 나타냅니다. 
public struct QueueArray<T>: Queue { 
	private var array: [T] = []
	
	public init() { }
	
	public var isEmpty: Bool { 
		array.isEmpty
	}
	
	public var peek: T? { 
		array.first
	}
	
	@DiscardableResult 
    public mutating func enqueue(_ element: T) -> Bool { 
		array.appent(element)
		return true
	}
	
	public mutating func dequeue() -> T? { 
		isEmpty ? nil : array.removeFirst() 
	}
}
OperationsAverage caseWorst case
enqueueO(1)O(n)
dequeueO(n)O(n)
Space ComplexityO(n)O(n)

Doubly Linked List-based Queue

  • QueueArray와 비슷하지만, DoublyLinkedList를 사용합니다.
  • 배열 대신 이중 연결 리스트를 사용하면 특정 노드를 삽입하거나 삭제할 때 O(n) 대신 O(1) 시간 복잡도가 걸립니다.
  • Enqueue
    • 이중 연결 리스트에서 노드를 삽입하면, 새 노드를 추가하기 전의 마지막 노드가 새 노드를 참조하도록 업데이트 하고, 새 노드는 마지막 노드를 이전 노드로 참조합니다.
    • 따라서 이 작업은 O(1) 시간 복잡도를 가집니다.
  • Dequeue
    • 리스트의 맨 앞에서 데이터를 삭제하는 것도 O(1) 시간 복잡도를 가집니다. 배열 구현과 비교해보면, 요소를 하나씩 이동시키지 않아도 됩니다.
    • 대신 연결 리스트의 첫 두 노드 사이의 다음과 이전 포인터를 업데이트하기만 하면 됩니다.
  • QueueArray의 주요 문제 중 하나는 항목을 dequeue하는 데 선형 시간이 걸린다는 것입니다. 그러나 연결 리스트로 구현하면 상수 시간으로 줄일 수 있습니다.
  • 하지만 QueueLinkedList의 주요 문제는 O(1)의 좋은 성능에도 불구하고, 높은 오버헤드를 갖고 있습니다.
  • 각 요소들의 비지역성은 캐시 미스가 더 많이 발생하여 액세스 시간이 증가될 수 있습니다.
  • 각 요소는 앞 뒤 참조를 위한 추가 저장 공간이 필요합니다. 게다가, 새 요소를 만들 때마다 상대적으로 비싼 동적 할당이 필요합니다. 반면, QueuArray는 더 빠른 대량 할당을 수행합니다. 
public class QueueLinkedList<T>: Queue {
    
    private var list = DoublyLinkedList<T>()
    
    public var values: DoublyLinkedList<T> {
        list
    }
    
    public init() { }
    
    public var isEmpty: Bool {
        list.isEmpty
    }
    
    public var peek: T? {
        list.first?.value
    }
    
    public func enqueue(_ element: T) -> Bool {
        list.append(element)
        return true
    }
    
    public func dequeue() -> T? {
        list.removeFirst()
    }
}
OperationsAverage caseWorst case
enqueueO(1)O(1)
dequeueO(1)O(1)
Space ComplexityO(n)O(n)

Ring buffer-based Queue

  • 고정된 크기를 초과하지 않을 것이라는 것만 보장되면, 링 버퍼를 기반으로 한 다른 접근 방식을 사용할 수 있습니다.
  • 예를 들어, 다섯 명의 플레이어가 있는 Monopoly 게임을 할 경우, 다음 차례를 추적하기 위해 링 버퍼를 기반으로 한 큐를 사용할 수 있습니다.
  • Ring Buffer 또는 Circular Buffer는 고정 크기의 배열로, 더 이상 삭제할 아이템이 없을 때 배열이 시작지점으로 되돌아가는 데이터 구조입니다.
  • ex 크기가 4인 고정 크기의 링 버퍼를 생성했을 때
    1. Read 포인터는 큐의 맨 앞을 확인합니다.
    2. Write 포인터는 이미 읽은 기존 요소를 덮어쓸 수 있도록 사용 가능한 슬롯을 확인합니다.
  • Enqueue
    • 큐에 항목을 추가할 때마다, Write 포인터가 1 증가합니다.
    • 만약, Write 포인터가 Read 포인터 보다 더 앞에 있을 때 (index 카운트가 증가되었을 때) 이는 큐가 비어 있지 않다는 것을 의미합니다.
    • 만약, Write 포인터가 끝에 도달했을 때 Write 포인터는 시작 인덱스로 다시 이동합니다.
    • Ring Buffer의 고정된 사이즈 때문에 데이터가 가득 차있을 경우, enqueue가 실패할 수 도 있다.
  • Dequeue
    • 큐에 항목을 Dequene할 때마다, Read 포인터가 1 증가합니다.
    • 만약, Read 포인터가 끝에 도달했을 때 Read 포인터는 시작 인덱스로 다시 이동합니다.
    • Read 포인터와 Write 포인터가 같을 때, 큐는 비어있다는 것을 보장 할 수 있습니다.
public struct RingBuffer<T> {
    
    // 빈 공간의 배열을 만들기 위해서 옵셔녈처리
    private var array: [T?]
    private var readIndex = 0
    private var writeIndex = 0
    
    public init(count: Int) {
        array = Array<T?>(repeating: nil, count: count)
    }
    
    public var first: T? {
        array[readIndex]
    }
	
	private var availableSpaceForReading: Int {
        writeIndex - readIndex
    }
    
    public var isEmpty: Bool {
        availableSpaceForReading == 0
    }
    
    private var availableSpaceForWriting: Int {
        array.count - availableSpaceForReading
    }
    
    public var isFull: Bool {
        availableSpaceForWriting == 0
    }
    
    public mutating func write(_ element: T) -> Bool {
        if !isFull {
            array[writeIndex % array.count] = element
            writeIndex += 1
            return true
        } else {
            return false
        }
    }
    
    public mutating func read() -> T? {
        if !isEmpty {
            let element = array[readIndex % array.count]
            readIndex += 1
            return element
        } else {
            return nil
        }
    }
    
}

extension RingBuffer: CustomStringConvertible {
  public var description: String {
    let values = (0..<availableSpaceForReading).map {
      String(describing: array[($0 + readIndex) % array.count]!)
    }
    return "[" + values.joined(separator: ", ") + "]"
  }
}
public struct QueueRingBuffer<T>: Queue {
    private var ringBuffer: RingBuffer<T>
    
    public init(count: Int) {
        ringBuffer = RingBuffer(count: count)
    }
    
    public var isEmpty: Bool {
        ringBuffer.isEmpty
    }
    
    public var peek: T? {
        ringBuffer.first
    }
    
    public mutating func enqueue(_ element: T) -> Bool {
        ringBuffer.write(element)
    }
    
    public mutating func dequeue() -> T? {
        ringBuffer.read()
    }
}


extension QueueRingBuffer: CustomStringConvertible {
    public var description: String {
        String(describing: ringBuffer)
    }
}
OperationsAverage caseWorst case
enqueueO(1)O(1)
dequeueO(1)O(1)
Space ComplexityO(n)O(n)

Double-Stacks-based Queue

  • Double Stacks의 큐 구현은 비교적 간단합니다.
  • enqueue시 right stack에 append를 실시하고, dequeue시 right stack을 reverse시킨 다음에 reversed된 데이터를 left stack 에 저장하고 마지막 원소를 제거해주면 된다.
  • Enqueue
    • 배열에 추가하기 위해 append를 사용하여 스택에 요소를 push 합니다.
  • Dequeue
    1. left stack이 비었는지 확인합니다.
    2. left stack이 비었다면 뒤집어진 right stack을 left stack에 넣습니다.
    3. right stack의 모든 원소를 제거합니다.
    4. 마지막으로 left stack의 마지막 원소를 제거합니다.
    • left stack이 비어있지 않다면 left stack의 마지막 원소를 제거합니다.
    • 배열을 뒤집는 연산은 O(n)의 시간 복잡도를 가집니다. 하지만 전체 dequeue 비용은 평균 O(1) 입니다.
  • QueueArray와 비교하여 두 개의 스택을 활용함으로 써 dequeue의 시간 복잡도를 O(1)의 작업으로 변환할 수 있습니다.
  • 또한, 이 두 개의 스택 구현은 고정 크기 제한이 없으며 완전히 동적입니다. Right Stack이 뒤집히는 경우나, 용량이 부족해지는 경우에만 최악의 성능인 O(n)이 됩니다.
  • 마지막으로, 공간 지역성 측면에서 Linked List보다 효율성이 좋습니다. 배열 요소는 메모리 블록에서 서로 옆에 있기 때문에 많은 수의 요소가 처음 액세스할 때 캐시에 로드됩니다.
  • 배열은 O(n)의 메모리 복사 작업을 수행하지만, 메모리 대역폭 근처에서 매우 빠르게 실행되는 매우 빠른 O(n) 작업 입니다. 
public struct QueueStack<T>: Queue {
    private var leftStack:[T] = []
    private var rightStack:[T] = []
    public init() { }
    
    public var isEmpty: Bool {
        leftStack.isEmpty && rightStack.isEmpty
    }
    
    public var peek: T? {
        !leftStack.isEmpty ? leftStack.last : rightStack.first
    }
    
    public mutating func enqueue(_ element: T) -> Bool {
        rightStack.append(element)
        return true
    }
    
    public mutating func dequeue() -> T? {
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        return leftStack.popLast()
    }
}
OperationsAverage caseWorst case
enqueueO(1)O(n)
dequeueO(1)O(n)
Space ComplexityO(n)O(n)

출처(참고문헌)

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.

profile
전성훈
이전 포스트

[Data Structure / Algorithms] Doubly Linked List

다음 포스트

[Data Structure / Algorithms] Dequeue

0개의 댓글