[자료구조] 큐(queue)

큐란?

가장 먼저 저장한 자료가 가장 먼저 호출되고, 가장 나중에 저장한 자료가 가장 나중에 호출되는 구조.

한 쪽에서 들어와서 다른 쪽에서 나오는 빨대와 같다

 

큐 구조

 

 

사용 예시

- 컴퓨터 운영체제의 작업 스케줄링(Task Scheduling) 중 빠른 시작시간 우선 스케줄링

- 너비 우선 탐색(BFS)

 

 

큐 구현

첫번째 방법 : 기본 배열로 구현하는 방법

원소 삽입하는 법 : 마지막 위치 뒤에 원소를 삽입한다.

원소 삭제하는 법 :  queue[0]에 있는 원소를 삭제한다.

 

 

하지만 이 방법은 원소를 삭제할 때마다 뒤의 나머지 원소들을 왼쪽으로 한칸씩 이동해야 한다.

(삭제할 때의 시간복잡도는 O(n))

 

 

 

 

 

 

두번째 개선된 방법 : 첫번째 원소의 위치를 옮기는 방법

원소 삽입하는 법 : 마지막 위치 뒤에 원소를 삽입한다.

원소 삭제하는 법 : 첫번째 원소의 위치를 queue[front]로 하여 원소 삭제 후 front++ 를 연산한다.

                         이로써 삭제할 때 나머지 원소들을 왼쪽으로 이동하지 않아도 된다.

                         즉 삭제할 때의 시간복잡도는 O(1)이 되어 첫번째 방법보다 짧은 시간으로 해결할 수 있다.

 

하지만 이 방법도 문제가 발생한다. front가 옮겨질 때 front 앞부분은 더이상 사용되지 않는 메모리가 되기 때문이다.

따라서 front가 계속해서 옮겨질수록 메모리 낭비가 크다.

 

 

 

 

 

 

세번째 개선된 방법 : 원형 큐

배열의 끝이 처음으로 되돌아오게 되어 끝없이 빙빙 도는 구조다.

이로써 front가 옮겨져도 낭비되는 메모리가 없게 된다.

 

 

 

 

 

원형 큐 구현

특징 : 

- 원형 구조로 인해 배열 마지막 원소의 다음 위치는 queue[0]가 된다.

- 원형 큐에서 처음 원소를 가리키는 변수 front와 마지막 원소를 가리키는 변수 rear는 시계방향으로 이동한다.

- front는 처음 원소의 위치보다 시계 방향 기준으로 하나 전 위치를 가진다. 

이때 front가 하나 전 위치를 가리키지 않으면 요소로 꽉찬 상태일때 문제가 발생한다. 위 그림처럼 요소로 꽉차게 되면 front와 rear 모두 queue[0]를 가리킬 수 있다. 문제는 공백 상태인 경우에도 front와 rear 모두 queue[0]를 가리키도록 설정했다는것이다.  결국 front와 rear가 모두 queue[0]을 가리킬 때 공백 상태인지 꽉찬 상태인지 구분되지 않아 오류가 발생한다.

따라서 위 그림처럼 front는 처음 원소의 위치보다 시계 방향 기준으로 하나 전 위치를 가진다. 

 

 

 

 

 

 

구현에 필요한 요소:

template <class T>
class Queue {
 private:
    T *queue;			//큐 배열
    int front;			//처음 원소의 위치보다 시계 방향 기준으로 하나 전인 위치
    int rear;			//마지막 원소의 위치
    int capacity;		//큐 배열의 크기

 public:
    Queue(int queueCapacity);			//큐 배열의 크기를 매개변수로 가지는 생성자
    
    bool IsEmpty() const;			//큐가 공백인지 검사하는 함수
    
    T& Front() const;				//처음 원소를 리턴하는 함수
    
    T& Rear() const;				//마지막 원소를 리턴하는 함수
    
    void Push (const T& item);			//새로운 원소를 삽입하는 함수
    
    void Pop();					//처음 원소를 삭제하는 함수
    
}

 

 

 

생성자 세부정보 :

template <class T>
Queue<T>::Queue(int queueCapacity): capacity (queueCapacity)
{
   if (capacity < 1) throw "Queue capacity must be > 0";	//큐 배열의 크기 < 1 이면 예외 발생시킴
   queue = new T[capacity];					// 동적 배열 생성
   front = rear = 0;
}

 

 

 

 

함수 세부정보:

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


template <class T>
inline T& Queue<T> :: Front()
{
   if (IsEmpty()) throw "Queue is empty. No front element";	//배열이 공백인 경우 예외 발생시킴
   front = (front+1)%capacity;
   return queue[front];
}


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>::Pop()
{
   if (isEmpty()) throw "Queue is empty. Cannot delete.";
   front = (front+1)%capacity;
   queue[front].~T();	//해당 메모리 소멸
}

코드 부연설명:  " rear = (rear+1) % capacity; " ,  " front = (front+1) % capacity; " 의 의미

rear, front값이 1씩 더해지다가 capacity값(배열공간)을 넘어선 순간 원형구조로 인해 queue[0]에 위치하게 되므로 rear = 0으로 리셋한다.

ex) queue[9] == queue[1]

 

또한 아래 코드를 한줄로 압축한 것이다.

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

 

   

 

 

 

 

push() 함수 세부정보:

template <class T>
void Queue<T> :: Push(const T& x)
{
   if ((rear+1) % capacity == front)		//배열이 다 찬 경우 true, 아니면 false
   {
   
   		//배열 확장 코드
   
   }
   
   rear = (rear+1) % capacity;

   queue[rear] = x;
}

 

 

 

- 배열 확장 코드

메모리가 다 찬 경우 메모리를 확장시켜야 한다. (현 메모리 용량의 2배로 확장)

또한 배열 확장 후 큐 구조 유지를 위해 요소를 재정렬해주어야 한다.

 

 

 

- 요소 재정렬 첫번째 방법 : 배열 확장 후 front값 뒤의 요소들을 모두 뒤로 이동시킨다. 

     

     - 시간 복잡도 : 최악의 경우 (capacity - 1) * 2 

     요소의 총 갯수는 (capacity - 1)이다.

     이전 배열에 있는 요소를 모두 복사해 새로운 배열에 넣기.  -> (capacity - 1) 만큼 복사

     아래 그림처럼 모든 요소가 front값 뒤에 있는 경우. -> (capacity -1)만큼 뒤로 이동

     즉, 시간복잡도는 최악의 경우 (capacity - 1) * 2

최악인 경우

 

 

 

- 요소 재정렬 두번째 개선된 방법 : 

   1) 새로운 배열 newQueue 생성

 

 

 

   2) 뒤 부분(queue[front+1]과 queue[capacity-1] 사이에 있는 원소들)을 newQueue의 0에서부터 복사해 넣는다.

 

 

   3) 앞 부분(queue[0]와 queue[rear]사이에 있는 원소들)을 newQueue의 capacity-front-1에서부터 복사해 넣는다.

 

 

     - 시간복잡도 : 요소 복사 후 새로운 배열에 넣기 -> (capacity - 1)

 

 

 

 

 

- 두번째 방법으로 Push()함수 코드 구현

template <class T>
void Queue<T> :: Push(const T& x)
{
   if ((rear+1) % capacity == front)			//배열이 다 찬 경우 true, 아니면 false
   {
   
   	//배열 확장 코드
        T* newQueue = new T[2 * capacity];	//새 배열 생성
        
        int start = (front + 1) % capacity;
        if (start < 2)		// 이전 배열의 요소가 앞 뒤로 안쪼개진 경우 true, 쪼개진 경우 false
           copy(queue+start, queue+start+capacity-1, newQueue);
        else
        {
           copy(queue+start, queue+start+capacity, newQueue);	//이전 배열의 뒤 부분 복사
           copy(queue, queue+rear+1, newQueue+capacity-start);	//이전 배열의 앞 부분 복사
        }
        
        front = 2 * capacity - 1;	//배열의 가장 마지막인 위치로 지정
        rear = (capacity - 1) - 1;	//마지막 요소의 위치로 지정
        capacity *= 2;
        delete [] queue;
        queue = newQueue;	//이름 물려주기
   }
   rear = (rear+1) % capacity;
   
   queue[rear] = x;
}

 

- 코드 부연설명:

두 배열의 요소가 앞 뒤로 쪼개지지 않은 경우 if (start < 2) 에서 true 다.

 

start = 0 인 경우

start = (front + 1) % capacity 에 의해 start = 0

 

 

 

start = 1 인 경우

start = (front + 1) % capacity 에 의해 start = 1

 

 

 

 

 

참고 자료:

C++ 자료구조론/이석호 역/인피니티북스/2007/2판