큐와 덱 : 순서대로 처리하기

큐 초기 상태: [A, B, C, D, E, _, _, _]
            ^           ^
          front       rear

dequeue 후:   [_, B, C, D, E, _, _, _]
                 ^         ^
                front     rear

 

 

지난 시간에는 '해시 테이블'에 대해서 알아보았지요.

 

해시 테이블은 해시 함수를 이용해 키를 인덱스로 변환함으로써 O(1)의 시간 복잡도로 빠른 검색이 가능해졌어요.

그리고 서로 다른 키에 대해 같은 인덱스 값이 나오는 '충돌'이 생겼을 때 체이닝이나 개방 주소법등의 기법을 통해 

대용량의 데이터를 효율적으로 관리할 수 있게 되었어요. 

 

해시 테이블 : 빠르게 데이터 검색하기

이제 오늘의 주인공 '큐(Queue)'와 '덱(Deque)'에 대해 알아보도록 합시다. 

레츠 기딧 ~~~

순서대로 해주세요

자원이 무한정하게 많을 때는 각자가 원하는 만큼 가져가면 되지만 

세상이 그렇게 녹록지는 않죠?

 컴퓨터 세계에도 자원은 한정되어 있고 이를 원하는 이들끼리 나눠 써야 해요. 

 

예를 들어 운영체제에서 여러 프로세스가 CPU 시간을 나눠 써야 하거나 

프린터가 여러 문서를 인쇄해야 할때, 또는 웹 서버에 수 많은 요청이 들어올 때 처럼 말이죠.

그렇다면 이러한 경우에는 어떻게 자원을 분배해야 아무도 불만이 없을까요?

 

"누가 먼저 왔는지"에 따라 순서대로 처리하는 것이 공정하지 않겠어요.

먼저 왔으면 먼저하고 나중에 왔으면 기다렸다 나중에 하는 방식을 "선입 선출(First In First Out)이라해요. 

그리고 이를 구현하기 위한 자료구조가 바로 Queue 랍니다. 

 

큐는 두개의 주요 포인터를 가져요. 

front(앞) : 가장 먼저 제거될 요소를 가리켜요. 

rear(뒤) : 가장 최근에 추가된 요소를 가리켜요. 

 

큐의 기본 연산은 다음과 같아요. 

enqueue(item) : rear에 새 항목을 추가해요. 

dequeue( ) : front에서 항목을 제거하고 반환해요. 

peek( ) : front 항목을 제거하지 않고 확인만 해요.

isEmpty( ) : 큐가 비어있는지를 확인해요. 

size( ) : 큐의 현재 크기를 반환해요. 

 

큐는 실제로 어떻게 구현되는지 알아볼까요?

 

배열 기반 구현

일반 배열을 이용해 큐를 만들 수도 있지만 사실 문제가 좀 있어요. 

요소를 dequeue 할 때마다 모든 요소들을 앞으로 이동시켜야 한다면 O(n) 시간이 걸리기 때문에 비효율적이에요. 

 

이 문제를 해결하기 위해 원형 Queue 개념이 등장했어요.
front와 rear 포인터가 배열의 끝에 도달하면 다시 배열의 처음으로 '순환'하는 방식이에요. 

// 원형 큐의 개념
[I, _, _, A, B, C, D, E, F, G, H]
 ^        ^       
rear     front                 ---> ( 다시 배열의 처음으로 돌아감 )

링크드 리스트 구현 

링크드 리스트를 사용하면 동적으로 크기를 조절할 수 있고

enqueue와 dequeue 연산을 모두 O(1) 시간에 수행할 수 있어요. 

front -> [A] -> [B] -> [C] -> [D] -> [E] <- rear

 

좀 더 자유롭게 사용할래요.

큐는 한쪽 끝(rear)에서만 삽입하고 다른 쪽 끝(front)에서만 삭제할 수 있어요.

그런데 양쪽 끝에서 모두 삽입과 삭제가 가능하면 더 유연하게 활용할 수 있지 않을까요?

이러한 필요성에서 덱(Deque: Double-Ended Queue)이 등장했어요.

 

데크는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조로 기본 연산은 아래와 같아요. 

 

addFirst(item): 맨 앞에 항목 추가

addLast(item): 맨 뒤에 항목 추가

removeFirst(): 맨 앞의 항목 제거 및 반환

removeLast(): 맨 뒤의 항목 제거 및 반환

peekFirst(): 맨 앞의 항목 확인

peekLast(): 맨 뒤의 항목 확인

 

큐와 덱을 Swift를 사용하면 아래와 같이 구현해볼 수 있어요. 

// 배열 기반 큐 구현
struct Queue<T> {
    private var elements: [T] = []
    
    mutating func enqueue(_ value: T) {
        elements.append(value)
    }
    
    mutating func dequeue() -> T? {
        guard !elements.isEmpty else {
            return nil
        }
        return elements.removeFirst()
    }
    
    var front: T? {
        return elements.first
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var size: Int {
        return elements.count
    }
}

// 사용 예
var queue = Queue<String>()
queue.enqueue("첫번째")
queue.enqueue("두번째")
print(queue.dequeue() ?? "")  // 출력: 첫번째

// 링크드 리스트 기반 데크 구현
class Node<T> {
    var value: T
    var next: Node<T>?
    var prev: Node<T>?
    
    init(value: T) {
        self.value = value
    }
}

class Deque<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
    private var count: Int = 0
    
    func addFirst(_ value: T) {
        let newNode = Node(value: value)
        if head == nil {
            head = newNode
            tail = newNode
        } else {
            newNode.next = head
            head?.prev = newNode
            head = newNode
        }
        count += 1
    }
    
    func addLast(_ value: T) {
        let newNode = Node(value: value)
        if tail == nil {
            head = newNode
            tail = newNode
        } else {
            newNode.prev = tail
            tail?.next = newNode
            tail = newNode
        }
        count += 1
    }
    
    func removeFirst() -> T? {
        guard let firstNode = head else {
            return nil
        }
        
        let value = firstNode.value
        head = firstNode.next
        head?.prev = nil
        
        if head == nil {
            tail = nil
        }
        
        count -= 1
        return value
    }
    
    func removeLast() -> T? {
        guard let lastNode = tail else {
            return nil
        }
        
        let value = lastNode.value
        tail = lastNode.prev
        tail?.next = nil
        
        if tail == nil {
            head = nil
        }
        
        count -= 1
        return value
    }
    
    var isEmpty: Bool {
        return count == 0
    }
    
    var size: Int {
        return count
    }
}

// 사용 예
let deque = Deque<String>()
deque.addFirst("앞에 추가")
deque.addLast("뒤에 추가")
print(deque.removeFirst() ?? "")  // 출력: 앞에 추가
print(deque.removeLast() ?? "")   // 출력: 뒤에 추가

 

 

큐와 데크는 컴퓨터 과학에서 매우 중요한 자료구조로, 특히 순서가 중요한 데이터 처리에 널리 사용돼요.

큐는 "선입선출(FIFO)" 원칙을 구현하여 프로세스 스케줄링, 네트워크 패킷 관리, BFS 알고리즘 등에 활용됩니다.

 

데크는 양쪽 끝에서 삽입과 삭제가 가능하여 큐와 스택의 기능을 모두 수행할 수 있어,

더 유연한 데이터 처리가 필요한 상황에서 활용됩니다.

모든 자료구조가 그렇듯이, 큐와 데크도 특정 상황에 더 적합해요.

데이터의 특성과 필요한 연산에 따라 적절한 자료구조를 선택하는 것이 중요합니다.