3. [자료구조] Queue

2018. 6. 26. 23:13자료구조

3. 자료구조 Queue

 

1) Queue?

Queue란 기본적인 자료구조의 한가지로 먼저 넣은 데이터가 먼저 나오는 형태를 가지고 있는 유한 순서 리스트입니다. 이를 FIFO(First In First Out) 또는 선입선출(先入先出) 구조라고 합니다.

 

이러한 큐는 컴퓨터 시스템에 많이 사용됩니다. 특별한 우선순위가 없는 작업 스케줄을 만들 때 사용하는데 이는 제일 먼저 제출되어 큐에 들어간 작업이 제일 먼저 처리되고 제일 나중에 제출되어 작업 큐에 들어간 작업이 제일 나중에 처리되는 작업 스케줄이 만들어지기 때문입니다.

 

아래 그림은 큐의 기본 형태라고 보시면 됩니다. 큐는 RearFront라는 Cursor와 데이터를 저장하는 공간으로 이루어져 있습니다. RearQueue의 뒷부분을 가리키고 FrontQueue의 앞부분을 뜻합니다.

<비워져 있는 Queue>


이러한 형태의 Queue에 데이터를 삽입하면 아래 그림과 같은 형태가 됩니다그림을 보시면 Rear가 움직이면서 Rear가 위치한 칸에 데이터가 들어간 것을 볼 수 있습니다.

 <queue에 A 데이터 삽입>


다시 데이터를 삽입하면 아래와 같은 형태를 합니다.

 <queue에 B 데이터 삽입>

 <queue에 C 데이터 삽입>

 

이번에는 데이터 삭제입니다. 데이터를 삭제하게 되면 Front가 움직이면서 해당 칸에 데이터가 삭제되게 됩니다.

 <queue에 데이터 삭제>

 

다음은 Queue의 데이터를 모두 삭제하고 다시 데이터 D를 삽입 후 삭제하는 과정입니다.

 <queue에 데이터 삭제>

 <queue에 데이터 삭제 공백상태>

<queue에 D 데이터 삽입>

 <queue에 데이터 삭제 공백상태>


 

2) Queue의 구현

자바 소스코드를 사용해서 간단한 큐를 구현하여 설명하겠습니다.

 

  • 큐의 생성입니다. 위에 설명한 것처럼 데이터 공간과 FrontRearCursor가 필요합니다.
class Queue{
	int[] q;
	int rear;
	int front;
	
	public Queue(int n) {
		q = new int[n];
		rear = -1;
		front = -1;
	}
}


  • 큐가 공백인지 검사하는 함수입니다. 아래 그림과 같이 FrontRear가 같아지면 공백이 됩니다.
	public boolean isEmpty() {
		if(front == rear) {return true;} // Queue가 공백인 상태
		else {return false;} // Queue에 Data가 있는 상태
	}


  • 큐에 데이터를 삽입하는 함수입니다. 데이터 삽입시 rear가 증가하여 해당 위치에 데이터를 삽입합니다. 단 삽입전 Queue가 만원 상태인지 확인합니다.
	public void enQueue(int item) {
		if(rear == q.length-1) {
			System.out.println("Queue Full");
			return; // Queue가 full인 상태 데이터 삽입 불가
		}else {
			rear = rear + 1; // rear를 증가
			q[rear] = item; // rear 위치에 item 삽입
		}
	}


  • 큐에 데이터를 삭제하여 반환하는 함수입니다. Queue가 공백인지 검사하며 공백이 아니라면 front를 증가시키고 반환합니다.
	public int deQueue() {
		if(isEmpty()) { // Queue가 공백이면 99를 반환
			System.out.print("Queue Empty");
			return 99; 
		}else { // Queue에 데이터가 있다면 front값을 1증가후 데이터를 반환
			front = front +1;
			return q[front];
		}
	}




3) 원형 Queue

위 와 같은 알고리즘으로 만들어진 큐에는 큰 문제점이 있습니다. 이는 한번 사용한 공간을 다시 사용하지 못한다는 것입니다. 그래서 만들어 진 것이 원형 큐입니다. 이는 큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐입니다.

 

아래 그림과 같이 배열이 원형으로 돌아가면서 채워지면서 다시 공간을 사용할 수 있습니다.

 


 

이러한 원형큐는 FrontRear의 증감식에 Mod연산자를 사용하여 구현하게 됩니다. 이와 같은 방법을 사용하면 rearn-1다음 값이 n이 아닌 0으로 돌아가게 됩니다. 이때 Mod는 나머지 연산자이며 n은 배열의 크기입니다.

rear <- (rear + 1) Mod n
front <- (front +1) Mod n

이때 주위해야할 사항이 있습니다. QueueFull조건이니다.이때 중요한 것은 rear가 한 바퀴 돌아서 front를 앞지르면 안된다는 것입니다. 이는 기존의 Full조건을 원형 Queue Full조건으로 변경해줘야 합니다.

if(rear == n) then Queue Full // 기존 queue full 조건
if((rear + 1) Mod n == front) then Queue Full // 원형 queue full 조건


'자료구조' 카테고리의 다른 글

5-1. [자료구조] 트리(Tree)  (2) 2018.06.27
4. [자료구조] Stack  (0) 2018.06.27
3. [자료구조] Queue  (0) 2018.06.26
2. [자료구조] 연결리스트  (0) 2018.06.24
1. [자료구조] 배열  (0) 2018.06.24
0. 자료구조란?  (0) 2018.06.24