[자료구조] 큐

큐(queue)

- 한쪽 끝에서 삽입이 일어나고 반대쪽 끝에서 삭제가 일어나는 순서 리스트

- 선입선출(FIFO, Firest-In-First-Out) 리스트

• 새로운 원소가 삽입되는 끝 - rear
• 원소가 삭제되는 끝 - front

 

큐의 구현

1차원 배열 이용

1. 큐의 첫 번째 원소를 queue[0]로 표현한 큐

- 삭제: queue[0] 원소를 제거
- 삭제 후 나머지 원소들을 왼쪽으로 이동해야 함 → 시간복잡도 - O(n)

비효율적

 

2. 큐의 첫번째 원소를 queue[front]로 표현한 큐

- 변수 fornt를 사용하여 큐의 첫번째 위치를 항상 유지
- 삭제: 시간복잡도 - Θ(1)
- 큐의 원소: queue[fornt], ..., queue[rear]

- 배열 queue의 크기가 capacity일 경우, rear = capacity-1이고 front > 0일 때 문제 발생

원형 큐

- 큐가 배열의 끝에서 되돌아오게 함
- 변수 fornt는 큐에서 첫 원소의 위치보다 시계반대 방향으로 하나 앞 위치를 가리킴
- 변수 rear는 큐에서 마지막 원소의 위치를 가리킴

- 모든 배열 위치는 직전 위치와 다음 위치를 가짐
→ capacity-1의 다음 위치는 0, 0의 직전 위치는 capacity-1

- 원형 큐의 동작을 위해 front와 rear를 시계 방향으로 이동시킴

if (rear == capacity - 1) rear = 0;
else rear++;

template <class T>
class Queue
{ // 0이상의 원소가 있는 유한 순서 리스트
private:
    T *queue;     // 큐 원소를 위한 배열
    int front,    // 원소가 삽입되는 끝
        rear,     // 원소가 삭제되는 끝
        capacity; // 큐 배열의 크기
public:
    Queue(int queueCapacity = 10);
    // 초기 용량이 queueCapacity인 빈 큐 생성

    bool IsEmpty() const;
    // 큐의 원소 수가 0이면 true를 반환, 그렇지 않으면 false를 반환

    T &Front() const;
    // front 원소 반환

    T &Rear() const;
    // rear 원소 반환

    void Push(const T &item);
    // rear에 원소 삽입

    void Pop();
    // front의 원소 삭제
};

 

큐의 함수 구현

emplate <class T>
inline bool Queue<T>::IsEmpty() { return front == rear; }

template <class T>
inline T &Queue<T>::Front()
{
    if (IsEmpty())
        throw "Queue is empty. No front element";
    return queue[(front + 1) % capacity];
}

template <class T>
inline T &Queue<T>::Rear()
{
    if (IsEmpty())
        throw "Queue is empty. No rear element";
    return queue[rear];
}

template <class T>
void Queue<T>::Push(const T &x)
{ // queue의 rear에 x를 더함
    if ((rear + 1) % capacity == front)
    { // queue가 꽉 찼을 때, capacity(용량)를 2배로 늘림
        T *newQueue = new T[2 * capacity]; 
        // 크기가 2배인 새로운 큐 생성

        // 새로운 큐에 기존 큐를 복사
        int start = (front + 1) % capacity;
        if (start < 2)
            // 큐가 인덱스 0부터 채워져 있을 때
            copy(queue + start, queue + start + capacity - 1, newQueue);
        else
        {   // 큐가 인덱스 0부터 채워져 있지 않을 때
            copy(queue + start, queue + capacity, newQueue);
            copy(queue, queue + rear + 1, newQueue + capacity - start);
        }

        // 새로운 큐로 대체
        front = 2 * capacity - 1;
        rear = capacity - 2;
        capacity *= 2;
        delete[] queue;
        queue = newQueue;
    }
    rear = (rear + 1) % capacity;
    queue[rear] = x;
}

template <class T>
void Queue<T>::Pop()
{ // 큐의 원소를 삭제
  if (IsEmpty()) throw "Queue is empty. Cannot delete.";
  front = (front + 1) % capacity;
  queue[front].~T(); // T의 소멸자
}