[자료구조] Queue

전체적으로 알고는 있지만 생각보다 정리를 한 기억이 없어서

개념적인 부분 정리와 Swift 코드를 이용해서 예제 만들어보기 또는 나만의 도구들로써 코드를 작성해보려한다.

이렇게 정리를 한뒤 알고리즘 문제에 접근해서 하나씩 완성해보자..

---

자료구조 01 / Queue

---

정의 

컴퓨터 자료구조로 처리할 항목을 순차적으로 대기열에서 처리하는 방법

가장 먼저 대기중인 데이터를 먼저 처리하는 구조 선입선출 FIFO(First-in First-Out)

줄 서는 모습과 유사하다고 볼 수 있음

 

- 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨(OS)

 

주요기능

enqueue() : 큐에 데이터 쌓기

dequeue() : 큐의 맨 앞 데이터 빼기

front() : 큐의 맨 앞 데이터

empty() : 큐가 비어있는 지 확인하는  

 

활용

운영체제에서 멀티태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용.

Priority Queue (우선순위 큐), 데크 (Deque, 양 방향으로 enqueue/dequeue선택 할 수 있는 구조)등 다양하게 변형 할 수 있다.

 

구현 

github

GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제

 

연결리스트를 통한 구현

 - 노드의 할당 및 삭제, 포인터를 타고 들어가는 시간 낭비가 생긴다

 

동적 배열을 이용한 구현

 - HEAD와 TAIL의 사용을 신경쓰지 않으면 공간의 낭비가 발생할 수 있다.

// Swift 5
// raywenderlich.com

struct Queue<T> {
    var queue = [T]()
    
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    var front: T? {
        return queue.first
    }
    
    var count: Int {
        return queue.count
    }
    
    mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    mutating func dequeue() -> T? {
        if isEmpty {
            return nil
        } else {
            return queue.removeFirst()
        }
    }
}

원형 버퍼(Circulr Buffer), 힙(Heap) 등의 방식으로도 구현 가능.

 

추가적으로 생각해볼 내용

1. 배열구조와 차이점 

큐 형태를 구현하지 않고 배열을 이용해서

.insert(0. data) (enqueue) / .pop() (dequeue) 를 구현하는 경우 queue의 기본적인 기능 측면으로만 보면 동일 하게 사용 가능하지만

 

컴퓨터 성능 측면으로 보았을 때 Enqueue(배열 0으로 추가) 또는 Dequeue(배열 0에서 제거) 등등

나머지 데이터를 모두 방문해서 index를 당기거나 밀어주는 동작이 생성되기 때문에 

시간복잡도 O( array.count ) 만큼의 비용이 발생 할 수 있다. 

 

2. 활용

* 우선순위가 같은 작업 예약 (Round Robin 스케쥴링 기법)

* BFS ( Breath First Search : 너비 우선탐색) 알고리즘에 사용, 그래프 탐색

 

Reference : raywenderlich.com github explain