[Data Structure] 큐 (Queue)

안녕하세요!

이번에는 Queue에 대해서 포스팅해보려고 합니다!

 

 

1. Queue란?

Queue는 한쪽 끝에서만 원소의 추가가 이루어지고, 다른 한쪽 끝에서만 원소의 제거가 이루어지는 순차화된 리스트입니다.

원소의 추가가 이루어지는 쪽을 rear, 원소의 제거가 이루어지는 쪽을 front라고 합니다.

즉, rear로 원소가 들어오고, front로 원소가 나간다고 생각하시면 됩니다.

 

Queue는 가장 먼저 들어온 원소가 가장 먼저 나오기 때문에 FIFO (First-In-First-Out) 구조입니다.

 

Queue 또한 Stack과 마찬가지로 원소의 추가/제거 시간복잡도는 O(1)입니다.

제일 앞과 뒤에 있는 원소를 확인하는 시간복잡도 또한 O(1)입니다.

그리고 Queue의 제일 앞과 뒤를 제외한 나머지 원소들의 확인 또는 변경은 불가능합니다.

 

 

 

2. Queue 구현하기

 

Queue를 구현하는 코드는 다음과 같습니다.

struct Queue<T> {
    private var queue: [T] = []
    
    // queue가 비어있는지 확인
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    // queue의 front (제일 앞의 원소 확인)
    var front: T? {
        return queue.first
    }
    
    // queue의 rear (제일 뒤의 원소 확인)
    var rear: T? {
        return queue.last
    }
    
    // queue의 원소 갯수
    var count: Int {
        return queue.count
    }
    
    // queue의 rear에 원소 추가
    mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    // queue의 front에서 원소 제거
    mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

 

 

Queue 또한 다양한 자료형으로 사용하기 위해 Generic으로 선언하였고,

queue 라는 배열에 원소를 저장하여 사용하면 된답니다!

 

var myQueue = Queue<Int>()

myQueue.enqueue(0)
myQueue.enqueue(1)
myQueue.enqueue(2)

print("front:", myQueue.front!) // 0
print("rear:", myQueue.rear!) // 2
print("count:", myQueue.count) // 3

myQueue.dequeue() // front인 0을 dequeue
myQueue.dequeue() // front인 1을 dequeue

print("front:", myQueue.front!) // 2
print("rear:", myQueue.rear!) // 2

myQueue.dequeue() // front인 2를 dequeue
myQueue.dequeue() // nil

print("count", myQueue.count) // 0

 

위 코드의 실행 결과는 아래와 같습니다.

추가로,,

Swift로 알고리즘 문제를 풀다보니 시간초과를 굉장히 많이 겪었습니다!

removeFirst()의 시간복잡도가 O(n)이기 때문에, removeFirst()를 사용하면 시간초과가 나는 것 같더라구요.

 

그래서 removeFirst()를 사용하지 않고 Queue를 구현하는 방법도 추가하였습니다!

struct AnotherQueue<T> {
    private var list1: [T] = [] // enqueue를 위한 배열
    private var list2: [T] = [] // dequeue를 위한 배열
    
    var isEmpty: Bool {
        return list1.isEmpty && list2.isEmpty
    }
    
    var count: Int {
        return list1.count + list2.count
    }
    
    var front: T? {
        if list2.isEmpty {
            return list1.first
        } else {
            return list2.last
        }
    }
    
    var rear: T? {
        if list2.isEmpty {
            return list1.last
        } else {
            return list2.first
        }
    }
    
    mutating func enqueue(_ element: T) {
        list1.append(element)
    }
    
    mutating func dequeue() -> T?  {
        // list2가 비어있을 때에만 list1의 요소들을 reversed()로 복사해옴
        if list2.isEmpty {
            list2 = list1.reversed()
            list1.removeAll()
        }
        return list2.popLast()
    }
}

 

여기서는 배열을 2개 사용합니다!

바로 enqueue를 위한 배열 list1과 dequeue를 위한 배열 list2인데요,

 

먼저 enqueue 메소드는 앞에서와 마찬가지로 list1에 원소를 추가하는 역할을 합니다.

dequeue 메소드가 조금 다른데요!

dequeue 메소드에서는 list2가 비어있을 때에만 list1 원소들을 reversed로 복사해옵니다.

그 후에 list1을 빈 상태로 만들어줍니다.

그리고 마지막으로 list2의 원소 갯수와 상관없이 가장 마지막 원소를 pop해주면 dequeue가 이루어집니다.

removeFirst()를 사용하지 않는 방법이죠!

 

그림으로 설명하면 다음과 같습니다.

 

 

그렇기 때문에 front와 rear 속성도 구현 방법이 살짝 다르지만, 사용방법과 원리는 똑같다는거!!!

여기까지 오늘도 Queue에 대해 알아보았는데요, 글 읽어주셔서 감사하고 피드백은 항상 환영입니다😇