[Algorithms]Queue_큐

Queue 큐

선입선출(FIFO:First In First Out)

스택과 마찬가지로 데이터를 일시적으로 쌓아두기 위한 자료구조로, 예를 들어 은행창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 생각해 볼 수 있다. 

시작 지점이 front, 마지막 지점이 rear이며, insert는 뒤 순서에 enqueue, delete는 앞 순서부터 dequeue된다. dequeue되고 나면 뒷 순서의 요소들을 앞쪽으로 하나씩 옮겨야 한다(shift).

enqueue시에 뒤 rear부터 삽입되므로 rear가 점차 증가하여  rear==n-1 인 경우 큐는  full상태 가 된다. 

 

문제점

 dequeue할 때마다 요소들을 앞으로 shift해주어야하며 이때 많은 비용이 (원소이동에 따른 지연시간)이 발생한다. 

 

 

---

 

<해결책>

원형큐(링버퍼)

 

순차표현 큐에서 데이터를 이동하는 대신 인덱스(front, rear)를 업데이트하여 복잡도를 줄여 효과적
:이동문제가 해결되어 0(n)의 복잡도는 O(1)이 된다. 

 

 max(큐의 최대용량)  저장가능한 최대 요소의 개수
 num(현재 데이터의 수)  front와 rear가 같을 때 큐가 비어 있는지, 가득찼는지 구별하게 해준다. 

 

//enqueue

public int enque(int x) throws OverflowIntQueueException{

	// 큐가 가득찼는지 확인하여 예외처리
    if(num>=max) { 
    	throw new OverflowQueueException();
    }
    que[rear++] = x; // rear + 1
    num ++;			 // num  + 1
    
    if(rear == max) { //rear가 max값을 넘어가는 경우 rear 값을 0으로 초기화
    	rear = 0;
    }
    
    return x;
}

//dequeue

public int deque() throws EmptyIntQueueException{
	
    // 큐가 비어있을 경우 예외 처리
    if(num<=0){
    	throw new EmptyIntQueueException();
    }
    int x = que[front++];
    num--;
    
    if(front == max){ // front를 0으로 초기화 
    	front =;
    }
    return x;
}