[자료구조] 큐(Queue)

큐(Queue)의 개념

한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조 (선형 자료 구조)

가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First In First Out) 방식으로 자료를 처리

큐(Queue)의 에러

• 큐 오버플로우 : 큐의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없을 때 발생

• 큐 언더플로우 : 큐에 제거할 자료가 없을 때 발생

큐(Queue)의 연산

시작과 끝을 표시하는 두 개의 포인터가 있는데, 프런트(F, Front)는 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터이며 삭제 작업을 할 때 사용한다. 리어(R, Rear)는 가장 마지막에 삽입된 자료가 위치한 기억공간을 가리키는 포인터이며 삽입 작업을 할 때 사용한다.

• create(size) : 큐의 크기를 size로 지정하고 생성한다.

• push(item) : item을 큐에 삽입한다.

• pop() : 큐에 front에 있는 항목을 제거한다.

• front() : 큐의 가장 앞에 있는 항목을 반환한다.

• size() : 큐에 있는 item의 개수를 반환한다.

큐(Queue)의 예제

상태의 의존관계가 없을 때 A와 B가 서로 관련이 없지만 모두 하긴 해야할 때 

= 병렬화, 스케줄링(Scheduling)

• BFS(너비 우선 탐색)

큐(Queue)의 구현

class Queue {
	int[] data = new int[100];
	int f; // 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터
	int r; // 가장 마지막에 삽입된 자료가 위치한 기억공간을 가리키는 포인터
	int capacity; 
	
	void create(int m){
		capacity = m;
		f = 0;
		r = 0;
	}
	
	void push(int item){
		if(r-f >= capacity){
			System.out.println("Queue Overflow!");
		}
		else{
			data[r++] = item;
		}
	}
	
	void pop(){
		if(r-f <= 0){
			System.out.println("Queue Underflow!");
		}
		else{
			data[f] = 0;
			f++;
		}
	}
	// 큐의 맨 앞에 있는 값을 반환
	// 단, 반환할 값이 없다면 -1 반환
	int front(){            
		if(r-f <= 0){
			return -1;
		}
		else{
			return data[f];
		}	
	}
	
	int size(){
		return r-f;
	}
}

public class DataStructureQueue {
	public static void main(String[] args) {
		Queue q1 = new Queue();
		q1.create(3);
		
		q1.push(1);
		q1.push(2);
		q1.push(3); 
		q1.push(4); //overflow

		System.out.println(q1.front()); //1
		
		q1.pop(); 
		System.out.println(q1.front()); //2
		
		q1.pop();
		q1.pop();
		q1.pop(); // underflow
		System.out.println(q1.size()); // 0
	}
}