c++ queue 큐 구현

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다.

 

1. STL Queue / 큐 인터페이스 구현

STL vector를 기반으로 구현되어 있으며, STL vector와 같이 클래스 큐는 std 네임스페이스에 속하므로, 아래 코드의 두번째 줄처럼 해야 한다. 아래 코드는 한 예로 float의 큐를 선언한 것이다.

#include <queue>
using std::queue;
queue<float> myQueue;

size, empty, push, pop, front, back 인터페이스를 가지고 있다.

 

stl 말고 비공식적인 클래스로서 queue의 인터페이스를 구현해보면 아래와 같다.

template <typename E>
class Queue {
public:
    int size() const;
    bool empty() const;
    const E& front() const throw(QueueEmpty);
    void enqueue(const E& e);
    void dequeue() throw(QueueEmpty);
};

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

2. 배열 이용 시 더 효율적으로 큐를 구현하는 방법?

 순환 배열을 구현하는 방법이다. 이는 배열의 크기가 고정되어 있는데 반해 큐는 데이터의 이동, 삭제가 너무 빈번히 일어난다는 점에서 착안한 것이다. 코드는 후에 필요하면 본문에 추가할 예정

 

3. 환형 링크드 리스트로 큐 구현

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


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


LinkedQueue::LinkedQueue()
    : C(), n(0) { }
int LinkedQueue::size() const
    { return n; }
bool LinkedQueue::empty() const
    { return n==0; }

const Elem& LinkedQueue::front() const throw(QueueEmpty) {
    if(empty())
        throw QueueEmpty("front of empty queue");
    return C.front;
}
void LinkedQueue::enqueue(const Elem& e) {
    C.add(e);
    C.advance();
    n++;
}
void LinkedQueue::dequeue() throw(QueueEmpty) {
    if(empty())
        throw QueueEmpty("dequeue of empty queue");
    C.remove();
    n--;
}

 

4. 양방향 큐(deque)

STL 데크는 다음과 같이 선언하고 사용한다.

#include <deque>
using std::deque;
deque<string> myDeque;

size(), empty(), push_front/back(e), pop_front/back(), front(), back() 연산자를 지원한다.