[자료구조] 큐

Queue

먼저 들어온 게 먼저 나가는 구조.
ex) 대기줄, 입장표 순번…

• First in First out

ADT

• IsEmpty: 큐가 비어있으면 True를, 아니면 False를 반환한다.
• Push: 큐에 요소를 추가한다.
• Pop: 가장 먼저 들어왔던 요소를 삭제한다.
• Front: 가장 먼저 들어왔던 요소를 반환한다.
• Rear: 가장 나중에 들어왔던 요소를 반환한다.

Linear Queue

front index가 고정된 큐이다.
front index가 고정되어 있기에 Pop시 정렬을 해줘야 하는데 비효율적이다.

Circular Queue

front index가 유동적인 큐이다.
Pop시 front index도 함께 움직인다.

구현 - C++

// circular queue
template <typename T>
class Queue
{
private:
    T *queue_;
    unsigned int front_; // front index
    unsigned int rear_;  // rear index
    unsigned int size_;  // maximum count of queue
    unsigned int count_; // elements number of queue

public:
    Queue(int size=10) : size_(size), front_(0), rear_(0), count_(0)
    { queue_ = new T[size_]; }

    ~Queue() { delete[] queue_; }

    inline unsigned int count() const { return count_; }
    inline unsigned int size() const { return size_; }
    inline bool IsEmpty() const { return count_ == 0; }

    T &Front() const
    {
        if (IsEmpty())
            throw "Queue is empty.";
        return queue_[(front_ + 1) % size_];
    }

    T &Rear() const
    {
        if (IsEmpty())
            throw "Queue is empty.";
        return queue_[rear_];
    }

    void Push(const T &obj)
    {
        if (count_ == size_) // if queue is full...
        {
            // double size
            T *temp = queue_;
            queue_ = new T[size_ * 2];

            // <첫번째 방법>: 그대로 카피 후 front밀어버리기
            // copy
            for (int i = 0; i < size_; i++)
                queue_[i] = temp[i];

            delete[] temp;

            // sweep from front to end of index
            if (front_ >= rear_)
            {
                int i;
                for (i = 0; i < size_; i++)
                {
                    if (size_ - 1 - i == front_)
                        break;
                    queue_[size_ * 2 - 1 - i] = queue_[size_ - 1 - i];
                }
                front_ = size_ * 2 - 1 - i;
            }
            size_ *= 2;

            // <두번째 방법>: 카피와 동시에 정렬
            // for (int i = 0; i < size_; i++)
            //     queue_[i] = temp[(front_ + 1 + i) % size_];
            //
            // delete[] temp;
            // front_ = size_ * 2 - 1;
            // rear_ = count_ - 1;
            // size_ *= 2;
        }

        rear_ = (rear_ + 1) % size_;
        queue_[rear_] = obj;
        count_++;
    }

    void Pop()
    {
        if (IsEmpty())
            throw "Queue is empty.";

        front_ = (front_ + 1) % size_;
        queue_[front_].~T();
        count_--;
    }
};