Fixed Size Queue ( Circular Queue Buffer )

개요

개발을 진행하면서 큐 자료구조를 써야하는 경우는 종종 발생한다. 아래 그림 처럼 동작하는 자료구조가 바로 큐이다.

대부분의 언어에서 큐 자료구조 정도는 지원 하지만 내가 개발하는 환경이 메모리에 민감하거나 매프레임 동적할당을 할 수 있는 환경이 아닌 경우 제공하는 자료구조를 쓰지 못할 수 도 있다. std::queue 의 경우 동적할당이 매번 발생하니까..

또한 기존의 동작과는 다른 요구사항이 있었다.

"새로운 원소가 들어오면 기존 큐에 가장 오래 남아있던 원소는 삭제하고, 새로운 원소를 큐에 집어넣어주세요" 라는 요구사항이다.

정리하면 아래의 세가지 요구사항을 만족하는 새로운 자료구조가 필요하였다.

큐는 고정된 사이즈여야한다. ( 메모리 한계 )
새로운 원소가 들어오면 기존에 가장 오래된 원소는 제거하고 새로 들어간다.
동적할당을 쓰지 않는다.

이런 이유로 고정된 사이즈의 큐를 개발하게 됐다. 그리 어려운 구현은 아니지만 은근히 고려해야할 부분이 많았다.

나는 세가지 방법으로 구현하였다.

Fixed Size Queue 개념

기본 큐와는 달리 새로운 원소가 들어오면 가장 오래된 원소가 삭제된후 새로운 원소가 큐에 들어간다.

아래 세가지 방법은 Fixed Size Queue 를 구현하는 세가지 방법이다.

1. QueueBufferArray

간단한 배열 연산을 사용하여 개발하였다. 새로운 원소가 들어올때마다 기존의 배열들이 shift 해야 하기 때문에 큐의 사이즈가 클 수록 시간이 많이 걸린다.

template <typename T, int bufferSize>
class QueueBufferArray
{
public:
    QueueBufferArray()
    {
        capacity_ = bufferSize;
        size_=head_ = tail_ = 0;
    }
    ~QueueBufferArray() = default;
    QueueBufferArray(const T& data)
    {
        capacity_ = bufferSize;
        size_=head_ = tail_ = 0;

        for (int i = 0; i < bufferSize; i++)
        {
            enqueue(data);
        }
    }
    void enqueue(const T& data)
    {
        if (size_ == capacity_)
        {
            shiftBuffer();
            tail_--;
            buffer_[tail_++] = data;
            return;
        }

        buffer_[tail_++] = data;
        size_++;
    }
    T operator[](const int idx)const
    {
        return buffer_[idx];
    }
    void printAll()
    {
        for (int i = 0; i < tail_; i++)
        {
            cout << buffer_[i] << " ";
        }cout << endl;
    }
private:
    T buffer_[bufferSize + 1];

    int capacity_;
    int size_;
    int head_;
    int tail_;
    void shiftBuffer()
    {
        for (int i = 0; i < size_ - 1; i++)
        {
            buffer_[i] = buffer_[i + 1]; // 여기에서 원소들을 shift . 시간이 O(n) 걸림
        }
    }
};

2. QueueBuffer LinkedList.

동적할당에 쓸 메모리를 미리 전역변수로 잡아놓는 메모리 풀 기법을 활용하였다. Fixed Size Queue에 사용하는 메모리는 컴파일 타임때 결정된다. 새로운 원소가 들어오게 되면 가장 오래된 원소의 메모리의 내용을 새로원 원소로 채워놓는다. 기존의 head tail 포인터도 그에 맞게 새로 바꾸면 된다.

template <typename T>
struct Node
{

    Node* prev_;
    Node* next_;
    T data_;
    Node()
    {
        prev_ = nullptr;
        next_ = nullptr;
        data_={};
    }
    ~Node() = default;
    void alloc(Node* prev, Node* next, const T&data)
    {
        data_ = data;
        prev_ = prev;
        next_ = next;
        if (prev_)prev_->next_ = this;
        if (next_)next_->prev_ = this;

        return;
    }
    void pop()
    {
        if (prev_)prev_->next_ = next_;

        if (next_)next_->prev_ = prev_;

        return;
    }


};

template <typename T, int N>
class  QueueBufferLinkedList
{

public:
    QueueBufferLinkedList()
    {
        capacity_ = N;
        bcnt_ = 0;
        size_ = 0;
        head_.next_ = &tail_;
        tail_.prev_ = &head_;

    }
    QueueBufferLinkedList(const T& initData)
    {
        capacity_ = N;
        bcnt_ = 0;
        size_ = 0;
        head_.next_ = &tail_;
        tail_.prev_ = &head_;

        for (int i = 0; i < N; i++)
        {
            enqueue(initData);
        }        
    }
    void enqueue(const T& data)
    {

        if (size_ == capacity_)
        {
            Node <T>* ptr = head_.next_;
            ptr->pop();
            ptr->alloc(tail_.prev_, &tail_, data);
            return;
        }
        else
        {
            buf_[bcnt_++].alloc(tail_.prev_, &tail_, data);
            size_++;
        }

        return;
    }
    T operator[](const int idx)const
    {
        if (idx >= 0)
        {
            Node<T>* ptr = head_.next_;
            for (int i = 0; i < idx; i++)
            {
                ptr = ptr->next_;
            }
            return ptr->data_;
        }
        else
        {
            Node<T>* ptr = tail_.prev_;
            for (int i = -1; i >idx; i--)
            {
                ptr = ptr->prev_;
            }
            return ptr->data_;
        }
    }
    void printAll()
    {
        Node<T>* ptr = (&head_)->next_;


        while (ptr != &tail_)
        {
            cout << ptr->data_ << " ";
            ptr = ptr->next_;
        }cout << endl;
    }
private:
    Node<T> buf_[N + 1];// Memory pool.
    int capacity_;
    int size_;
    int bcnt_;
    Node<T>head_;
    Node<T>tail_;
    bool IsEmpty() const
    {
        return head_.next_ == &tail_;
    }
};

3. SimpleBuffer

가장 간단하게 구현하였다. 우리에게는 CircularQueue 라고 하여 고정된 사이즈의 큐를 다루는 좋은 자료구조가 있다. 이를 잘만 활용하면 위의 기능을 구현할 수 있다. 설명은 코드로 대체한다.

template<typename T, int bufferSize>
class SimpleBuffer
{
public:

    SimpleBuffer()
    {
        head_ = -1;
        tail_ = -1;
        size_ = 0;
        bufferSize_ = bufferSize;
    }
    ~SimpleBuffer() = default;
    SimpleBuffer(const T& initdata)
    {
        head_ = -1;
        tail_ = -1;
        size_ = 0;
        bufferSize_ = bufferSize;
        for (int i = 0; i < bufferSize_; i++)
        {
            enqueue(initdata);
        }
    }
    T front() const
    {
        if (isEmpty()) { return T(); }

        return buffer[head_];
    }
    T tail() const
    {
        if (isEmpty()) { return T(); }


        return buffer[tail_];
    }
    void enqueue(const T& data)
    {
        if (IsFull())
        {
            dequeue();
            enqueue(data);
            return;
        }
        else
        {
            if (head_ == -1) { head_ = 0; }

            tail_ = (tail_ + 1) % (bufferSize_);
            buffer[tail_] = data;
            size_++;
        }
    }
    T operator[](const int idx) const // don't want to return l-value. Queue's data only changed by enqueue and dequeue
    {

        if (idx >= 0)
        {
            return buffer[(head_ + idx) % bufferSize_];
        }
        else
        {
            return buffer[(head_ + size_ + idx) % bufferSize_];
        }
    }

    void dequeue()
    {
        if (isEmpty())
        {
            return;
        }
        else
        {
            if (head_ == tail_)
            {
                head_ = -1, tail_ = -1;
            }
            else
            {
                head_ = (head_ + 1) % bufferSize_;
            }
        }

        size_--;

    }
    void printAll()
    {
        int i = head_;
        if (isEmpty())
        {

            return;
        }


        int idx = head_;

        for (idx = head_; idx != tail_; idx = (idx + 1) % bufferSize_)
        {
            cout << buffer[idx] << " ";
        } cout << buffer[idx] << endl;


        return;
    }
private:

    int head_;
    int tail_;
    int size_;
    int bufferSize_;
    T buffer[bufferSize] = {};
    bool IsFull() const
    {

        if (head_ == 0 && tail_ == (bufferSize_ - 1))
        {
            return true;
        }
        if (head_ == tail_ + 1)
        {
            return true;
        }
        return false;

    }
    bool isEmpty() const
    {
        if (head_ == -1) { return true; }

        else { return false; }
    }

};

마치며

큐는 고정된 사이즈여야한다.
새로운 원소가 들어오면 기존에 가장 오래된 원소는 제거하고 새로 들어간다.
동적할당을 쓰지 않는다.

위 세가지 조건을 위하여 개발한 나름 새로운 자료구조이다. 처음에는 구글링으로 위와 같은 자료구조를 명명하는게 있는지 찾아보았지만 딱히 부르는 말은 없는 것 같다. (버퍼(?) 원형 큐 (?) CircularQueue(?))

큐의 기본적인 동작이 꽉 찰 경우에는 아무것도 안하는게 컨셉이라 그런걸 수도 있을 것 같다.

위에 올린 코드가 동작하는 cpp 파일은 이 깃허브링크 에 올려두었다.

저작자표시 (새창열림)

'Study > DataStructure' 카테고리의 다른 글

CircularQueue Buffer (0)	2022.09.13

개요

Fixed Size Queue 개념

1. QueueBufferArray

2. QueueBuffer LinkedList.

3. SimpleBuffer

마치며

'Study > DataStructure' 카테고리의 다른 글

티스토리툴바