큐 (Queue)

안녕하십니까. 그린입니다🟢

이번 포스팅에서는 스택과 반대되는 큐에 대해 알아보겠습니다🧑🏻‍💻

큐(Queue)

 : FIFO(선입선출) 방식의 자료구조로 쉽게 생각하면 대기열의 순서에 많이 활용됩니다.

 -> 스위프트에서는 큐 자료구조가 따로 없기에 직접 만들어서 구현해야 합니다.

큐를 구현하기 위한 4가지 방법

 1) 배열 1개를 사용한 큐 구현

  : 큐에 데이터를 추가 시 O(1)의 시간복잡도를 가져 편리하지만 대신 큐에서 데이터를 추출 시 이전 데이터들을 전부 위치를 이동시킴으로 O(n) 시간복잡도를 가집니다. 비효율적입니다.

 2) 연결 리스트를 사용한 큐 구현

 3) 배열 2개를 사용한 큐 구현

  : 추가되는 큐와 삭제될 큐(반대 큐)의 배열 2개를 생성하여 기능을 시켜줍니다. 그럴경우 팝과 푸시 모두 O(1)의 시간복잡도를 가집니다.

    현재 큐를 구현하기 위한 4가지 방법 중 가장 시간/공간복잡도 측면에서 효율적입니다.

 4) 링 버퍼를 사용한 큐 구현

 ** 가장 효율적인 배열 2개를 사용한 큐로 구현하는것을 이번 포스팅에서 해보겠습니다!

Swift로 큐 구현하기

import Foundation

struct Queue<T: Equatable> {
    // 큐에 들어올 데이터를 담은 enqueue & 리버스 시켜 데이터를 내보낼 dequeue
    var enqueue: [T] = []
    var dequeue: [T] = []
    
    // 아무값이 주어지지 않은 초기화 시 동작
    init() {}
    
    // 큐 인자로 엔큐 배열을 초기화
    init(_ queue: [T]) {
        enqueue = queue
    }
    
    // 데이터 추가 push 메서드를 통해 엔큐 배열에 추가
    mutating func push(_ element: T) {
        enqueue.append(element)
    }
    
    // 데이터 꺼낼때 엔큐를 거꾸로 하여 디큐로 지정해주고 엔큐를 삭제 후 디큐의 마지막 요소 추출
    mutating func pop() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    
    // 엔큐, 디큐 초기화
    mutating func remove() {
        enqueue.removeAll()
        dequeue.removeAll()
    }
    
    // 비어있는지에 대한 연산프로퍼티 변수
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }
    
    // 첫번째 데이터값에 대한 연산프로퍼티 변수
    var firstIndex: T? {
        if dequeue.isEmpty {
            return enqueue.first
        } else {
            return dequeue.last
        }
    }
    
    // 마지막 데이터값에 대한 연산프로퍼티 변수
    var lastIndex: T? {
        if enqueue.isEmpty {
            return dequeue.first
        } else {
            return enqueue.last
        }
    }
    
    // 전체 큐에 대한 데이터 수 연산프로퍼티 변수
    var count: Int {
        return enqueue.count + dequeue.count
    }
    
    // 데이터가 포함되어 있는지 찾는 메서드
    // Equatable 프로토콜을 채택해주어야지 같은 값인지 판별할 수 있는 contains를 사용할 수 있음
    func contains(_ element: T) -> Bool {
        return enqueue.contains(element) || dequeue.contains(element)
    }
}

var firstQueue: Queue = Queue<Int>()
var secondQueue: Queue = Queue([1,2,3,4])

firstQueue.push(10)
firstQueue.push(20)
secondQueue.pop()

print("\(firstQueue)" + "\n" + "\(secondQueue)")

 코드에 대한 설명과 동작은 위와 같이 주석으로 달았습니다.

 이렇게 큐를 간단히 구현해주고 순서가 필요한 동작들의 자료구조로 구현해볼 수 있습니다.