4. 큐 (Queue)

dyeoma.tistory.com/4

자료구조 개념, 종류

 

Queue 선언

Private:
   T *queue;
   int front, rear;
   int capacity;
template <class T>
Queue<T>::Queue (int queueCapacity): capacity (queueCapacity){
   if(capacity < 1) throw "Queue capacity must be > 0";
   queue = new T[capacity];
   front =rear-1;
}

초기 front = rear = -1

queue full 상태 rear == capacity-1

queue empty 상태 front == rear

 

 

일차원 배열로 queue 생성 시 배열의 공간이 많이 남아도 queue full 발생

front	rear	Q[0]	[1]	[2]	[3]	[4]	[5]	[6]	...	설명
-1	-1									초기(empty)
-1	0	J1								J1을 삽입
-1	1	J1	J2							J2를 삽입
-1	2	J1	J2	J3						J3를 삽입
0	2		J2	J3						삭제(J1)
0	3		J2	J3	J4					J4를 삽입
1	3			J3	J4					삭제(J2)

 

 

 

원형 큐 (Circular Queue)

 

 

 

 

 

 

 

 

 

 

 

front와 rear를 시계방향으로 이동

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

rear = (rear+1)%capacity;

위의 두 코드는 같은 의미

 

초기 front=rear=0

empty 상태 front == rear

queue full 상태 front == (rear+1)%capacity

 

 

원형 Queue 삽입 - O(1) 소요

template <class T>
void Queue<T>::Push(const &x){
   if ( (rear+1)%capacity == front ){
      ChangeSizeID(queue, capacity, 2*capacity);
      capacity *=2;
   }
   rear = (rear+1)%capacity;
   queue[rear] = x;
}

 

원형 Queue 삭제 - O(1) 소요

template <class T>
T* Queue<T>::Pop(T& x){
   if (front == rear)	// empty queue
      return 0;
   front = (front+1)%capacity;
   x = queue[front];
   return &x;
}