Queue

Queue는 FIFO(First In First Out) 형태의 자료구조이다.

 

대부분의 서비스업은 이런 Queue 구조로 동작한다.

(대기열이 대표적인 예시)

다른 간단한 예시로 Queue와 Stack을 사용해

앞으로 읽든 뒤로 읽든 똑같은 단어인지 검사하는 프로그램을 만들 수 있다.

기러기 토마토 스위스 인도인 별똥별 우영우 역삼역(?!)

#include <queue>
#include <stack>
#include <cctype>
#include <iostream>

int main() {
    queue<char> q;
    stack<char> s;
    char letter;
    int mismatches = 0;
    
    while (cin.peek() != ‘\n’) {
        cin >> letter ;
        if (isalpha(letter)) {
            q.push(toupper(letter));
            s.push(toupper(letter));
        }
    }
    
    while ((!q.empty( )) && (!s.empty())) {
        if (q.front() != s.top())
            mismatches++;
        q.pop(); 
        s.pop();
    }
}

Queue는 꺼낼 때 먼저 들어간 데이터부터 꺼낸다는 점과

Stack은 나중에 들어간 데이터부터 꺼낸다는 차이를 이용하여 검사한다.

 

Queue를 구현하는 방법은 static array, linked list로 구현할 수 있는데, 우선 static array의 경우부터 살펴보자.

100개의 길이의 정적 배열로 구현한다고 가정해보자.

이 때, head, tail 두 개의 포인터로 queue의 처음과 끝을 가리키게 될 텐데,

만약, 98(head), 99 인덱스를 사용하고 있는 상황에서 queue에 push를 하게되는 경우를 처리하는 좋은 방법은 무엇일까?

98, 99의 데이터를 한 칸씩 앞으로 당기는 작업은 많은 자원을 소비하는 비효율적인 방법이다.

따라서 %(모듈러)연산자를 활용해 0번째 인덱스를 사용하는 것이다. (100%100 = 0, 101%100 = 1 ...)

size_t next_index(size_t i) const {
    return (i+1)%CAPACITY;
}

 

이 경우에는 head=tail인 경우에는 queue에 데이터가 1개 있다는 뜻이 될거고,

head=next_index(tail)인 경우에는 queue에 데이터가 없거나 100개 꽉 차있다는 뜻으로 해석이 된다.

(따라서 초기화시에는 first=0, last = CAPACITY-1로 초기화 해야한다.)

 

linked list로 구현하는 방법도 살펴보자.

template<class Item>
class queue { 
    public:
        typedef std::size_t size_type;
        queue();
        queue(const queue<Item> &source);
        ~queue();
        void pop();
        void push(const Item &entry);
        queue<Item> &operator=(const queue<Item> &source);
        bool empty() const { return (count == 0); }
        Item front() const;
        size_type size() const { return count; }
    private:
        node<Item> *front_ptr;
        node<Item> *rear_ptr;
        size_type count;
}

 

 

template<class Item>
queue<Item>::queue() {
    count = 0;
    front_ptr = NULL;
}

template<class Item>
queue<Item>::queue(const queue<Item> &source) {
    count = source.count;
    list_copy(source.front_ptr, front_ptr, rear_ptr);
}

template<class Item>
queue<Item>::~queue() {
    list_clear(front_ptr);
}

template<class Item>
queue<Item> &queue<Item>::operator=(const queue<Item> &source) {
    if (this == &source) 
        return *this;
        
    list_clear(front_ptr);
    list_copy(source.front_ptr, front_ptr, rear_ptr);
    count = source.count;
    return *this;
}

생성자, 파괴자 함수, 대입 연산자 operator overloading는 위와 같이 간단히 처리해준다.

 

template<class Item>
Item queue<Item>::front() const {
    assert(!empty());
    return front_ptr->data();
}

queue의 head를 보는 방법은 단순히 front_ptr의 data를 리턴하면 된다.

 

template<class Item>
void queue<Item>::pop() {
    assert(!empty());
    list_head_remove(front_ptr);
    --count;
}

queue에서 데이터를 제거하는 방법은 단순히 linked list의 head를 삭제하는 함수를 사용하면 된다.

 

template<class Item>
void queue<Item>::push(const Item &entry) {
    if (empty()) {
        list_head_insert(front_ptr, entry);
        rear_ptr = front_ptr;
    } else {
        list_insert(rear_ptr, entry);
        rear_ptr = rear_ptr->link();
    }
    ++count;
}

queue에 데이터를 추가하는 방법은 간단히 새로운 node를 만든 후,

기존 rear_ptr가 가리키는 node의 link를 새로만든 node로 연결한 뒤,

rear_ptr을 rear_ptr이 가리키는 node, 즉 새로운 node로 바꿔주면 된다.

 

 

c++ queue STL에는 queue 말고도 priority queue, double ended queue가 구현되어 있는데,

priority queue 사용시 주의점이 있다.

priority_queue<Item>은 "less then" operator를 구현해야한다.

그래야 Item 타입의 데이터의 크기 비교하여 데이터를 pop할 수 있기 때문이다.