[자료구조] 큐-1

이번에 정리해 볼 것은 Queue!

 

 iOS개발을 하다보면 DispatchQueue... 와 같은 Queue개념을 사용하는 API들이 존재하는데 ,

큐는 선입선출(First In First Out - FIFO) 방식으로 데이터를 순서대로 관리한다. 

 

무슨 말이냐. 데이터를 관리하는 큐 공간에 A-B-C의 데이터를 순서대로 넣었다면, 데이터를 뽑는 순서도 A-B-C가 들어간 순서 그대로를 보장한다는 것이다. 그렇기 때문에 큐는 순서를 보장해야 하는 작업을 해야할 때 주로 사용 하는 자료구조이다. 

 

마치, 마트의 계산대에서 계산하려고 줄을 기다리는 사람들의 모양이랄까. 한 줄로 늘어선 줄은 앞에 선 사람 부터 차례로 계산을 하고 빠져나간다. 큐도 이와 같은 방식으로 동작한다고 생각하면 된다.

 

 

큐의 종류

선형 큐와 원형 큐가 있다. 차례대로 어떤 부분에서 서로 차이가 있는것인지 알아보자.

 

 

선형 큐

우리가 큐를 떠올린다고 하면 보통 선형큐의 모습을 떠올린다.

 

선형큐의 특징으로는 

-크기가 제한 되어 있는 막대 모양의 큐  ( 배열의 모습을 일단 떠올려 보자 ) 

-데이터를 출력하고 비어진 공간만큼을 또 사용하려면 뒤로 추가된 데이터들을 꺼내서 앞으로 당겨와야하는 단점이 있다.

 

한 번 그림으로 큐의 동작방식을 알아보자.

일단 막대모양의 크기가 정해진 큐라고 했으니...  공간이 4개인 막대를 준비했다. 이게 바로 큐다!

 

그림 1

 

 

큐에서는 head,와 rear( 또는 tail 이라고도 한다.) 개념이 있다.

head와 rear는 이전 2021.07.14 - [자료구조] - [자료구조] 연결리스트-3 (양방향 연결 리스트)

포스팅에서 사용했던 head,tail의 성격과 비슷하다고 할 수 있다. 똑같은건가?

 

Head

연결리스트의 Head는 항상 리스트의 첫 노드를 가리키는 녀석이었지만, 여기서는 다음으로 출력될 Data의 공간을 가리키는 녀석이라고 생각하면 쉬울것 같다.

 

Rear

헤드와 반대로 입력될 공간을 가리키는 녀석이다. 한 번의 데이터의 추가가 완료되면 다음 공간으로 이동하여 Data가 들어갈 공간을 알려준다.

 

그림 2

 

큐를 생성하면 rear와 head는 큐의 첫 번째 공간에 위치해 있다. 당연하게도 아무런 데이터가 들어와 있지 않기 때문이다.

 

추가 ( enqueue)

큐에서 데이터를 공간안에 밀어넣는 것을 enqueue라고 하는데 삽입/추가/입력 등등 표현하는 단어는 다양한것 같다.

 

개인적인 생각: 여러 블로그를 봐도 사용하는 한글단어가 다 달라서 혼동이 온다. 개인적으로는 추가라고 생각하는데 이유는,

enqueue의 사전적 의미를 보면 데이터를 큐의 대기행렬에 더한다. 라는 표현을 사용하기 때문이다.

또, 삽입은 보통 어떠한 물체 사이에 끼워 넣는것을 말하고 입력은 기계적인 명령을 전달하는 뜻? 으로 사용하는것 경우가 많기 때문이다.

추가라고 했지만 enqueue라는 표현을 사용해서 본 포스트를 작성하겠다.

 

enqueue는 위에서 rear에 대해서 설명했듯이, rear의 위치에 Data가 추가 되는 것이다.

위 그림에서 첫 번째 공간에 rear가 위치했으니 , "A"라는 Data를 enqueue 하는 동작을 실행하면 아래 그림 처럼 되겠다.

 

첫 번째 공간에 "A"가 정상적으로 추가되었고 rear는 다음으로 추가될 Data가 들어갈 위치로 이동했다.

그림 3

이상태에서 "B"라는 Data를 추가해본다면 그림4 처럼  두번째 공간에 "B"가 들어갈테고 rear는 세번째 공간을 가리키는 모습이 된다.

그림 4

 

방출(dequeue)

제한된 크기의 막대에 데이터가 모두 들어갔다고 가정해보자. 더 이상 데이터를 추가 할 수 없는 Full상태의 큐가 할 수 있는 일이라고는 FIFO의 방식처럼 가장 먼저 입력된 Data를 방출 하는 일 뿐이다. 이를 dequeue라고 한다. 

 

dequeue는 순차적으로 쌓인 데이터를 방출함과 동시에 데이터가 자리하고 있던 위치를 비운다. 

방출은 head가 가리키는 위치부터 순서대로 방출되는데, rear와 마찬가지로 데이터가 방출되면 다음으로 방출될 data의 위치로 head가 이동하게 된다.

 

그림 5

지금 head가 A의 위치를 가리키고 있다. 선입선출에 의해 "A"가 먼저 들어왔으니 "A"가 방출될 차례라는 것을 알려주고 있는 것이다.

"A"를 방출해보자.

그림 6

그림 6과 같이 A는 방출되고 head의 위치가 "B"가 있는 두번째 공간을 가리키게 되었다. 이게 반복되면 head는 다음, 다음... 으로 이동하여 결국 head와 rear가 같은 위치에서 만나게 된다.

그림 7

이렇게 rear와 head가 만나게 되면 선형큐는 비어있는 상태가 된다.

 

Swift로 구현해봤다.

 

Queue클래스

class Queue {
    private var head: Int = 0
    private var rear: Int = 0
    private var queue: [Int?] = [nil, nil, nil, nil, nil]
    
    func enqueue(_ data: Int) {
        defer {
            if rear < queue.count - 1{
                rear += 1
            }
        }
        
        if rear < queue.count {
            if queue[rear] == nil {
                queue[rear] = data
                print("enq \(data)")
            } else {
                print("queue is full")
            }
        }
    }
    
    func dequeue() -> Int? {
        defer {
            if head < queue.count - 1{
                head += 1
            }
        }
        
        if head < queue.count {
            let deq = queue[head]
            queue[head] = nil
            print("deq \(deq)")
            return deq
        } else {
            print("queue is empty")
            return nil
        }
    }
    
    func queueCount() -> Int {
        return queue.filter {
            $0 != nil
        }.count
    }
    
    func printDatas() {
        var str: [String] = []
        queue.map { data in
            if let data = data {
                str.append("\(data)")
            } else {
                str.append("nil")
            }
        }
        print(str.joined(separator: ","))
    }
}

 

사용

let queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
queue.enqueue(5)
queue.enqueue(5)
queue.dequeue()
queue.dequeue()
queue.printDatas()

출력로그

 

이어서 

2021.07.25 - [자료구조] - [자료구조] 큐 - 원형큐