[자료구조] 큐 Queue / 선형 큐 Linear Queue

0. 큐 Queue 란?

 

큐란 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 ( 큐 Queue == 선형 큐 Linear Queue )

데이터의 입력과 출력 순서는 선입선출 (FIFO : Fisrt In First Out)

ex ) 은행 창구에서 차례를 기다리는 대기열, 마트에서 계산을 기다리는 대기열 등

 

인큐 (enqueue) : 큐에 데이터를 넣는 작업

디큐 (dequeue) : 큐에서 데이터를 꺼내는 작업

프런트 (front) : 데이터를 꺼내는 쪽

리어 (rear) : 데이터를 넣는 쪽

 

큐의 enque(), deque()

 

 

 

1. 큐 구현

 

int[] que : 큐 본체용 배열

int max : 큐 용량. 큐에 저장할 수 있는 최대 데이터 수

int front : 큐에 저장된 데이터의 가장 처음 위치. 다음 dequeue()를 실행할 위치

int rear : 큐에 저장된 데이터의 가장 마지막 위치+1. 다음 enqueue()를 실행할 위치

int num : 현재 쿠에 저장되어 있는 데이터 수. 큐가 비어있으면 num == 0, 큐가 가득 차 있으면 num == max

 

 

- Queue() : 생성자

public Queue(int capacity) {
	num = front = rear = 0;
	max = capacity;
	try {
		que = new int[max];
	} catch (OutOfMemoryError e) {
		max = 0;
	}
}

• 매개변수 : 생성할 큐의 용량
• 큐를 생성하면 비어있으므로 num, front, rear는 0
• 매개변수로 전달받은 capacity를 큐 용량을 나타내는 max에 복사
• 요소 수가 max인 배열 que 생성
• try-catch문을 사용하여 큐 본체 생성에 실패할 경우, max를 0으로 설정하여 다른 메서드가 존재하지 않는 배열에 잘못 접근하는 것을 막음

 

 

- enque() : 큐에 데이터를 인큐

public int enque(int x) throws OverFlowQueueException {
	if(rear >= max) {
		throw new OverFlowQueueException();
	}
	que[rear++] = x;
	num++;
	return x;
}

• 매개변수 : 인큐할 값
• 큐가 가득 차서 인큐할 수 없는 경우, 미리 작성한 OverFlowQueueException 을 throw
• 큐에 매개변수로 전달받은 데이터를 추가한 후, rear 증가
• 데이터가 추가되었으므로 num++
• 반환값 : 인큐한 값

 

 

- deque() : 큐에서 데이터를 디큐

public int deque() throws EmptyQueueException {
	if(front < 0) {
		throw new EmptyQueueException();
	}
	int x = que[front++];
	num--;
	return x;
}

• 큐에서 데이터를 제거
• 큐가 비어있어 디큐할 수 없는 경우, 미리 작성한 EmptyQueueException 을 throw
• 데이터를 실제로 제거하는 것이 아니라 front를 증가시킴으로써 다음에 같은 인덱스에 enque()시 데이터가 덮어씌워짐
• 데이터가 삭제되었으므로 num--
• 반환값 : 디큐한 값

 

 

- peek() : 큐의 프런트 값, 큐에서 다음에 꺼낼 데이터

public int peek() throws EmptyQueueException {
	if(num <= 0) {
		throw new EmptyQueueException();
	}
	return que[front];
}

• 큐가 비어있으면 미리 작성한 EmptyQueueException 을 throw
• que[front]의 값을 확인만 하고 데이터를 변경하지 않으므로 front, rear, num 값은 변하지 않음
• 반환값 : 큐의 프런트 값

 

 

- indexOf() : 큐 데이터 탐색

public int indexOf(int x) {
	for(int i = front; i < rear; i++) {
		if(que[i] == x) {
			return i;
		}
	}
	return -1;
}

• 매개변수 : 검색할 데이터
• 큐에 x와 같은 값의 데이터가 포함되어있는지 탐색
• 프런트에서 리어 방향으로 선형 탐색 수행 ( 프런트 앞과 리어 뒷부분은 큐 범위에 포함되어 있지 않기 때문에 que[front] ~ que[rear-1] 까지 탐색 )
• 반환값 : 존재하면 찾은 데이터의 idx, 존재하지 않으면 -1

 

 

 

- dump() : 큐 안의 모든 데이터 출력

public void dump() {
	if(num <= 0) {
		System.out.println("큐가 비어있습니다");
	} else {
		for(int i = front; i < rear; i++) {
			System.out.println(que[i] + " ");
		}
		System.out.println();
	}
}

• 큐에 인큐된 num개의 데이터를 프런트에서 리어 순으로 모두 출력
• 큐가 비어있으면 "큐가 비어있습니다" 출력

 

 

- 기타 메소드

public void clear() {
	num = front = rear = 0;
}

public int capacity() {
	return max;
}

public int size() {
	return num;
}

public boolean isEmpty() {
	return front <= 0;
}

public boolean isFull() {
	return rear >= max;
}

• clear() : 현재 큐의 모든 요소를 삭제. 큐의 배열 요소 값을 변경할 필요 없이 num, front, rear 값만 0으로 변경해주면 됨
• capacity() : 큐의 용량 max값 반환
• size() : 큐의 현재 데이터 수 num을 반환
• isEmpty() : 큐가 비어있는지 확인. 비어있다면 true, 아니면 false
• isFull() : 큐가 가득 찼는지 확인. 가득 찼으면 true, 아니면 false

 

 

 

2.  큐 단점

큐는 데이터를 추가(인큐)하면 rear 값이 증가하고 데이터를 삭제(디큐)하면 front 값이 증가한다.

큐의 용량은 한정되어 있는데, front 값과 rear 값이 증가하고 줄어들지 않아서

max 만큼의 데이터가 추가(인큐)되고 나면 데이터를 모두 삭제(디큐)한다고 해도 더이상 공간이 없어 큐를 사용할 수 없다.

 

이러한 문제를 해결하기 위한 방법이 두가지 존재한다.

1. 원형 큐 사용

2. 디큐할 때 마다 모든 요소를 앞으로 한칸씩 이동

 

원형 큐에 대해서는 다음 게시글 에서 확인할 수 있고

디큐할 때 마다 모든 요소를 한칸씩 이동하는 방법은 다음과 같다

 

 

front 와 rear 대신 num값을 이용한다.enque() 메소드에서는 num 위치에 데이터를 추가하고deque() 메소드에서는 무조건 0 위치의 데이터가 삭제되기 때문에 que[1]의 데이터를 que[0]에, que[2]의 데이터를 que[1]에, …, que[num-1]의 데이터를 que[num-2]에 저장하는 방식을 사용한다.

public int deque() throws EmptyQueueException {
	if(num <= 0) {
		throw new EmptyQueueException();
	}
	int x = que[0];
	num--;
	for(int i = 0; i < num; i++) {
		que[i] = que[i+1];
	}
	return x;
}

 

 

디큐할 때 마다 모든 요소를 앞으로 한칸씩 이동하는 Queue 전체 코드

public class Queue {
	private int max;
	private int num;
	private int[] que;
	
	public class EmptyQueueException extends RuntimeException {
		public EmptyQueueException() { }
	}
	
	public class OverFlowQueueException extends RuntimeException {
		public OverFlowQueueException() { }
	}
	
	public Queue(int capacity) {
		num = 0;
		max = capacity;
		try {
			que = new int[max];
		} catch (OutOfMemoryError e) {
			max = 0;
		}
	}
	
	public int enque(int x) throws OverFlowQueueException {
		if(num >= max) {
			throw new OverFlowQueueException();
		}
		que[num++] = x;
		return x;
	}
	
	public int deque() throws EmptyQueueException {
		if(num <= 0) {
			throw new EmptyQueueException();
		}
		int x = que[0];
		num--;
		for(int i = 0; i < num; i++) {
			que[i] = que[i+1];
		}
		return x;
	}
	
	public int peek() throws EmptyQueueException {
		if(num <= 0) {
			throw new EmptyQueueException();
		}
		return que[num-1];
	}
	
	public int indexOf(int x) {
		for(int i = 0; i < num; i++) {
			if(que[i] == x) {
				return i;
			}
		}
		return -1;
	}
	
	public void clear() {
		num = 0;
	}
	
	public int capacity() {
		return max;
	}
	
	public int size() {
		return num;
	}
	
	public boolean isEmpty() {
		return num <= 0;
	}
	
	public boolean isFull() {
		return num >= max;
	}
	
	public void dump() {
		if(num <= 0) {
			System.out.println("큐가 비어있습니다");
		} else {
			for(int i = 0; i < num; i++) {
				System.out.println(que[i] + " ");
			}
			System.out.println();
		}
	}
}