[ 자료구조 ] 큐(Queue)

큐(Queue)

큐는 선입선출(FIFO: First-In First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조다. 데이터 삽입을 enqueue라 하고, 데이터 삭제를 dequeue라고 한다. 그런데 흔히 삽입 및 삭제를 push, pop으로 부른다. 

스택과 비교해서 보기를 바란다. 스택은 가장 먼저 들어온 데이터가 가장 마지막에 나가지만, 큐는 가장 먼저 들어온 데이터가 가장 먼저 나간다. 이러한 자료구조가 왜 필요할까? 어떻게 활용할 수 있을까? 

 

가장 대표적인 예시는 '스케줄링'이라고 생각한다. 스케줄링은 쉽게 말해서 '줄 서기' 규칙이다. 마트에서 줄을 서는 경우를 예로 들어 보자. 줄에 가장 먼저 선 사람이 계산을 가장 먼저 하는 것은 당연하다. 티켓팅도 마찬가지다. 가장 먼저 들어온 사람에게 우선권을 주는 모든 경우에 큐를 사용할 수 있다. 

 

그런데 스케줄링에 스택을 사용할 수는 없을까? 가능하지만 비효율적이다! 스택에서 가장 먼저 들어온 데이터를 pop하려면 스택의 size가 1이 될때까지 모든 데이터를 pop하고 이를 따로 저장해둬야 한다. 여기서 마지막으로 남게 되는 하나의 원소가 가장 먼저 들어온 데이터다. 이를 pop하고 나면? 임시로 저장해둔 나머지 데이터를 스택에 다시 push 해줘야 한다. 

 

반대의 경우도 마찬가지다. 스택이 사용된 예시에서 큐를 사용하면 굉장히 비효율적이다. 인터넷 브라우저의 '뒤로가기' 버튼을 큐로 구현하면 어떻게 될지 스스로 생각해보기를 바란다. 이렇게 문제 해결에 있어 어떤 자료구조를 선택하냐에 따라 효율 차이 많이 난다. 

큐 구현

이제 큐를 구현해보자. 큐의 기본적인 연산은 아래와 같다. 

enqueue(e) : 큐의 rear에 객체 e를 삽입한다.
dequeue() : 큐의 front 객체를 삭제한다. 큐가 비었으면 에러 발생.
front() : front 객체의 레퍼런스를 반환한다. 큐가 비었으면 에러 발생.
size() : 큐 안의 객체의 개수를 반환한다.
empty() : 큐가 비었으면 true, 그렇지 않으면 false를 반환한다. 

 

우리의 목표는 위 기능들을 구현하는 것이다. 큐를 구현하는 방법으로 크게 배열을 사용하는 방법과 원형 연결 리스트를 사용하는 방법이 있다. 두 가지 방법으로 위 기능들을 구현해보자. 이번에도 역시 예외처리까지 고려한다. 

 

큐 구현 : 배열 기반

1. 구조

배열로 후입선출을 구현하려면 어떻게 해야 할까? 인덱스를 사용하면 크게 어렵지 않다. 위 그림을 보면 큐에는 입구와 출구가 따로 있다. 따라서 입구와 출구 인덱스를 저장하는 두 개의 변수가 필요하다. 입구 역할을 하는 인덱스를 rear, 출구 역할을 하는 인덱스를 front로 부른다. 좀 더 엄밀하게 말하면 front는 가장 먼저 들어온 데이터의 인덱스를 저장하는 변수고, rear는 새로운 데이터가 들어올 인덱스를 저장하는 변수다. 

enqueue(7)를 하면 rear 자리에 7이 들어가고 rear는 1 더해주면 된다. dequeue()는 단순히 front에 1을 더해주면 된다. 여기서 front와 rear가 배열의 크기보다 커질 때를 유의해야 한다. 이는 front와 rear 값을 갱신할때 배열의 크기로 모듈러 연산을 해주면 해결된다. 아래 구현 코드를 보면 어렵지 않게 이해할 수 있다. 

2. 클래스 정의

예외처리 클래스

class RuntimeException{
private:
    string errorMsg;
public:
    RuntimeException(const string & err) : errorMsg(err) {}
    virtual string what() const { return errorMsg; }
};

class QueueEmpty: public RuntimeException{
public:
    QueueEmpty(const string& err) : RuntimeException(err) {}
};

class QueueFull: public RuntimeException{
public:
    QueueFull(const string& err) : RuntimeException(err) {}
};

 

ArrayQueue 클래스

template <typename E>
class ArrayQueue{
public:
    ArrayQueue(int cap = 100);
    ~ArrayQueue();
    int size() const;
    bool empty() const;
    const E& front() const;
    void enqueue(const E& e);
    void dequeue();
private:
    E* Q;
    int capacity; // 용량
    int n; // 현재 데이터 개수(=size)
    int f; // front (출구)
    int r; // rear (입구)
};

3. 구현

// 생성자
template <typename E> ArrayQueue<E>::ArrayQueue(int cap)
    : Q(new E[cap]), capacity(cap), n(0), f(0), r(0) {}

// 소멸자
template <typename E> ArrayQueue<E>::~ArrayQueue(){
    delete[] Q;
}

// 큐에 저장된 데이터 개수
template <typename E> int ArrayQueue<E>::size() const{
    return n;
}

// 큐가 비었는지?
template <typename E> bool ArrayQueue<E>::empty() const{
    return (n == 0);
}

// 큐의 front 원소
template <typename E>
const E& ArrayQueue<E>::front() const{
    if(empty()) throw QueueEmpty("Queue is empty");
    return Q[f];
}

// e를 큐에 push
template <typename E>
void ArrayQueue<E>::enqueue(const E& e){
    if(size() == capacity) throw QueueFull("Queue is full");
    Q[r] = e;
    r = (r + 1) % capacity;
    n++;
}

// pop
template <typename E>
void ArrayQueue<E>::dequeue(){
    if(empty()) throw QueueEmpty("Queue is empty");
    f = (f + 1) % capacity;
    n--;
}

 

크게 어려운 부분은 없으므로 설명은 생략한다. 각 멤버 함수를 읽어보면 어렵지 않게 이해할 수 있을 것이다. 구현을 완료했으므로 메인 함수에서 테스트를 해보자! try, catch문으로 감싸주면 오류 발생시 적절한 문구가 출력될 것이다. 아래는 테스트 코드 예제다. 

 

int main(){
    try{
        ArrayQueue<string> Q(3);
        Q.dequeue(); // 오류: 빈 큐에 dequeue
        cout << Q.front() << endl;
    } catch(QueueFull& e){
        cout << e.what() << endl;
    } catch(QueueEmpty& e){
        cout << e.what() << endl;
    }
    
    cout << "Done" << endl;
    
    return 0;
}

 

큐 구현 : 원형 연결 리스트 기반

1. 구조

원형 연결 리스트를 사용하면 큐를 굉장히 쉽게 구현할 수 있다. 원형 리스트의 기준점은 cursor다. 원형 리스트에서 데이터가 추가될 때 새로운 노드는 cursor의 next 위치로 연결되기 때문에 cursor->next 노드를 front로, cursor 노드를 rear로 설정하면 된다. Enqueue 과정은 원형 연결 리스트에 노드 하나를 추가해주고, cursor의 위치만 한칸 옮기면 된다. cursor가 다음 노드로 이동하는 함수는 원현 연결 리스트에서 advance() 함수로 이미 구현되어 있다. Dequeue 과정은 원형 연결 리스트의 삭제 과정과 완전히 동일하다. 아래 그림을 참고하면서 이해해보자. 

데이터 추가 (enqueue)

데이터 삭제 (dequeue)

2. 클래스 정의

(예외처리 클래스는 배열 기반과 동일하므로 생략)

LinkedQueue 클래스

class LinkedQueue{
 public:
     LinkedQueue();
     int size() const;
     bool empty() const;
     const string& front() const;
     void enqueue(const string& e);
     void dequeue();
 private:
     CircleList C;
     int n;
 };

CircleList에 대한 코드는 여기를 참고하길 바란다. 멤버 변수로 n을 따로 둔 이유는 CircleList에 크기를 반환하는 함수가 없기 때문이다. 또한 소멸자는 CircleList의 소멸자를 사용하므로 LinkedQueue 클래스에서 따로 정의해줄 필요가 없다. 할당 해제가 되는지 확인하고 싶으면 CircleList의 소멸자에 "Destructed..."와 같은 문자열을 출력하도록 한 뒤에 메인 함수에서 테스트를 해보면 된다. 

3. 구현

// 생성자
LinkedQueue::LinkedQueue() : C(), n(0) {}

// 데이터 개수
int LinkedQueue::size() const{
    return n;
}

// 큐가 비었는지?
bool LinkedQueue::empty() const{
    return n == 0;
}

// front 원소 반환
const string& LinkedQueue::front() const{
    return C.front();
}

// enqueue
void LinkedQueue::enqueue(const string& e){
    C.add(e);
    C.advance();
    n++;
}

// dequeue
void LinkedQueue::dequeue(){
    C.remove();
    n--;
}

크게 어려운 부분은 없으므로 설명은 생략한다. 테스트 코드는 배열 기반 큐와 동일하게 사용하면 된다. 

 

 

여기까지 큐를 마무리한다!