DataStructure - 큐(Queue)란?

본 글은 『얄코의 가장 쉬운 자료구조와 알고리즘』을 참고하여 개인 학습 목적으로 이해한 내용을 정리한 것입니다.

FIFO(First In, First Out) 구조로 이루어진 자료구조로, 먼저 들어온 데이터가 먼저 나가는 형태를 띔.

• enqueue: Queue 값을 삽입
• dequeue: 먼저 들어온 값 추출

Queue는 Stack과 마찬가지로 배열, 연결 리스트를 사용하여 구현 가능함.

배열로 구현하는 경우 선형과 원형 구조로 구현을 할 수 있는데, 선형 구조로 구현할 경우 첫 번째 인덱스와 마지막 인덱스가 고정되기 때문에 값이 모두 들어가 있는 상태에서 dequeue를 한 후에 새로운 데이터를 enqueue할 수 없음.

따라서 대부분의 경우 직접 Queue를 구현해야한다면 원형 구조로 구현함.

원형 구조로 구현할 경우 enqueue와 dequeue 모두 O(1)의 시간복잡도를 가짐

배열을 통한 Queue 구현 예시

class CircularQueue{
    private var queue: [Int]
    private var front: Int = 0
    private var rear: Int = 0
    private var size: Int = 0
    private let capacity: Int
    
    init(capacity: Int) {
        self.capacity = capacity
        self.queue = Array(repeating: 0, count: capacity)
    }
    
    var isEmpty: Bool{
        get{
            return self.size == 0
        }
    }
    
    var isFull: Bool{
        get{
            return self.size == self.capacity
        }
    }
    
    public func enqueue(data: Int){
        if isFull{
            print("Queue is full")
            return
        }
        
        queue[rear] = data
        rear = (rear + 1) % capacity
        size += 1
    }
    
    public func dequeue() -> Int?{
        if isEmpty{
            print("Queue is empty")
            return nil
        }
        
        let item = queue[front]
        front = (front + 1) % capacity
        size -= 1
        
        return item
    }
    
    public func display(){
        var index = front
        for _ in 0..<size{
            print("\(queue[index]) ", terminator: "")
            index = (index + 1) % capacity
        }
        print()
    }
}

let queue = CircularQueue(capacity: 5)

queue.enqueue(data: 1)
queue.enqueue(data: 2)
queue.enqueue(data: 3)
queue.enqueue(data: 4)
queue.enqueue(data: 5)

queue.display()

print("dequeue : \(queue.dequeue()!)")

queue.display()

결과

1 2 3 4 5 
dequeue : 1
2 3 4 5 

연결 리스트를 통한 Queue 구현

class Node{
    var data: Int
    var next: Node?
    
    init(data: Int){
        self.data = data
    }
}

class LinkedListQueue{
    var front: Node?
    var rear: Node?
    
    var isEmpty: Bool{
        front == nil
    }
    
    public func enqueue(data: Int){
        var newNode = Node(data: data)
        if isEmpty{
            front = newNode
            rear = newNode
            return
        }
        
        rear?.next = newNode
        rear = newNode
    }
    
    public func dequeue() -> Int?{
        if isEmpty{
            print("Queue is empty")
            return nil
        }
        
        let data = front?.data
        front = front?.next
        if front == nil{
            rear = nil
        }
        
        return data
    }
    
    public func display(){
        var current = front
        while current != nil{
            print("\(current!.data) ", terminator: "")
            current = current?.next
        }
        print()
    }
}

let queue = LinkedListQueue()
queue.enqueue(data: 1)
queue.enqueue(data: 2)
queue.enqueue(data: 3)
queue.enqueue(data: 4)

queue.display()

print("dequeue : \(queue.dequeue()!)")

queue.display()

결과

1 2 3 4 
dequeue : 1
2 3 4