자료구조&기본 알고리즘 입문(자바)- 큐

○큐?
큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조. 하지만 가장 먼저 넣은 데이터를 
가장 먼저 꺼내는 선입선출(FIFO: First In First Out)인 점이 스택과 다르다. 생활에서 볼 수 있는 큐의 예는
은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있다. 

큐에 데이터를 넣는 작업을 인큐(enqueue)라고 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 
또 데이터를 꺼내는 쪽을 프런트(front)라고 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다. 

○배열로 큐 만들기
스택과 마찬가지로 큐도 배열을 사용하여 구현할 수 있다. 배열 프런트(front)부터 4개(19,22,37,53)의 데이터가 
들어간 배열 que가 있다고 가정해보자. 배열 이름을 que라고 할 경우 que[0]부터 que[3]까지의 데이터가 저장된다. 

24를 인큐할 경우
리어(rear)의 데이터가 저장된 que[3]다음 요소인 que[4]에 24를 저장ㅎ나다. 이 처리의 복잡도는 O(1)이고 
적은 비용으로 구현할 수 있다 

19디큐
que[0]에 저장된 19를 꺼낸 다음 두 번쨰 이후의 요소를 모두 맨 앞으로 옮긴다. 이 처리의 복잡도는 O(n)이며 
데이터를 꺼낼 때 마다 이런 처리를 하게 되면 효율이 떨어진다. 

 

○링 버퍼로 큐 만들기
배열 요소를 앞쪽으로 옮기지 않는 큐를 구현하기 위해 사용하는 자료구조가 링 버퍼(ring buffer)이다. 
링 버퍼는 배열의 처음이 끝과 연결되어 있다고 보는 자료구조이다. 여기서 논리적으로 어떤 요소가 첫 번쨰이고
어떤 쇼소가 마지막 요소인지 식별하기 위한 변수가 프런트(front)와 리어(rear)이다. 

프런트(front): 맨 처음 요소의 인덱스
리어(rear): 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)

이 상태에서 인큐와 디큐를 수행하면 프런트와 리어 값은 다음과 같은 과정을 거치게 된다 

1. 7개의 데이터(35,56,24,68,95,73,19)가 차례되로 있는 que가 있다고 가정하면 차례되로 que[7]. qie[8[...que[11],que[0].
que[1]에 저장된다. 프런트 값은 7이고 리어 값은 2이다. 

2. 82를 인큐한 상태에서는 que[2]에 82를 저장한 다음 리어 값을 1만큼 증가한다 

 

3. 35를 디큐한 상태에서는 프런트 요소(que[front], que[7])의 값 35를 뺴고 프런트 값을 1만큼 증가한다 

이렇게 큐를 구현하면 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하기 때문에 
앞에서 발생한 요소 이동 문제를 해결할 수 있다. 처리의 복잡도는 O(1)이다. 

다음은 링 버퍼로 큐를 구현하는 프로그램으로, INT형 데이터를 저장한다고 가정한다. 

// int형 큐

public class IntQueue {
	private int max;			// 큐의 용량
	private int front;			// 첫 번째 요소 커서
	private int rear;			// 마지막 요소 커서
	private int num;			// 현재 데이터 수
	private int[] que;			// 큐 본체

	// 실행 시 예외：큐가 비어 있음
	public class EmptyIntQueueException extends RuntimeException {
		public EmptyIntQueueException() { }
	}

	// 실행 시 예외：큐가 가득 참
	public class OverflowIntQueueException extends RuntimeException {
		public OverflowIntQueueException() { }
	}

	// 생성자
	public IntQueue(int capacity) {
		num = front = rear = 0;
		max = capacity;
		try {
			que = new int[max];				// 큐 본체용 배열을  생성
		} catch (OutOfMemoryError e) {		// 생성할 수 없음
			max = 0;
		}
	}

큐 클래스 intQueue
큐를 관리하는 클래스로 5개의 필드로 구성된다

1. 큐로 사용할 배열(que)
인큐하는 데이터를 저장하기 위한 큐 본체용 배열 
2. 큐의 최대 용량(max)
큐의 최대 용량을 저장하는 필드로, 이 값은 배열 que에 저장할 수 있는 최대 요소의 개수와 같다 
3. 프런트(front)
인큐하는데이터 가운데 첫 번쨰 요소의 인덱스를 저장하는 필드다 

4.리어(rear)
인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 필드다 
5. 현재 데이터 수(num)
큐에 쌓아 놓은 데이터 수를 나타내느 필드다. front와 rear의 값이 같은 경우 큐가 비어있는지, 가득 찼는지 
구별할 수 없는 상황을 피하기 위해 이 변 수가 필요하다. 큐가 비어 있을 때 num은 0이고, 가득 찼을떄는 num과 max의 값이 같다. num과 max가 없다면 front와 rear값만으로는 두 상태ㅡㄹ 구분할 수 없다. 

생성자 IntQueue
생성자는 큐 본체용 배열을 생성하는 등의 준비 작업을 숭핸한다. 생성 시 큐는 비어 있기 때문에 num, front, rear 값을 모두 0으로 한다. 또 매개변수 capacity로 전달받은 '큐의 용량'을 필드 max에 복사하고, 요솟수가 max인 배열 que의 본체를 생성한다. 

 

// 큐에 데이터를 인큐
	public int enque(int x) throws OverflowIntQueueException {
		if (num >= max)
			throw new OverflowIntQueueException();			// 큐가 가득 참
		que[rear++] = x;
		num++;
		if (rear == max)
			rear = 0;
		return x;
	}

인큐 메서드 enque
큐에 데이터를 인큐하는 메서드. 인큐에 성공하면 인큐한 값을 그대로 반환하다. 큐가 가득차서 인큐할 수 없으면 (num>=max가 성립) 예외  OverflowIntQueueException을 던진다. 

 

// 큐에서 데이터를 디큐
	public int deque() throws EmptyIntQueueException {
		if (num <= 0)
			throw new EmptyIntQueueException();				// 큐가 비어 있음
		int x = que[front++];
		num--;
		if (front == max)
			front = 0;
		return x;
	}

디큐 메서드 deque
큐에서 데이터를 디큐하고 그 값을 반환하는 메서드이다. 그러나 큐가 비어 있어 디큐할 수 없으면 (num<=0이 성립)
예외 EmptyIntQueueException을 던진다. 

 

	// 큐에서 데이터를 피크 (프런트 데이터를 들여다봄)
	public int peek() throws EmptyIntQueueException {
		if (num <= 0)
			throw new EmptyIntQueueException();				// 큐가 비어 있음
		return que[front];
	}

	// 큐에서 x를 검색하여 인덱스(찾지 못하면 –1)를 반환
	public int indexOf(int x) {
		for (int i = 0; i < num; i++) {
			int idx = (i + front) % max;
			if (que[idx] == x)								// 검색 성공
				return idx;
		}
		return -1;											// 검색 실패
	}

	// 큐를 비움
	public void clear() {
		num = front = rear = 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.print(que[(i + front) % max] + " ");
			System.out.println();
		}
	}
}

피크 메서드 peek
맨 앞의 데이터(디큐에서 꺼낼 데이터)를 몰래 엿보는 메서드다. que[front]의 값을 조사만 하고 데이터를 꺼내지는 않으므로 front, rear, num의 값이 변화하지 않는다. 큐가 비어 있으면 예외 EmprtIntQueueException을 던진다. 

검색 메서드 indexOf

큐의 배열에서 x와 같은 데이터가 저장되어 있는 위치를 알아내느 메서드이다. 프런트에서 리어 쪽으로 선형 검색을 
수행하며, 스캔의 시작은 배열의 첫 요소가 아니라 큐의 첫 요소인 프런트이다. 그래서 스캔할 떄 주목하는 인덱스 
idx의 계산이 (i+front)%max로 복잡하다. 검색에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다. 

모든 데이터를 삭제하는 메서드 clear
현재 큐의 모든 데이터를 삭제하는 메서드다

최대 용량을 확인하는 메서드 capacity
큐의 최대 용량을 반환하는 메서드다 

데이터 수를 확인하는 메서드 size
현재 큐의 데이터 수를 반환하는 메서드다 

큐가 비어 있는지 판단하는 메서드 isEmpty
큐가 비어 있는지 판단하는 메서드다. 비어 있으면 true,  그렇지 않으면 false를 반환한다 

큐가 가득찼는지 판단하는 메서드 IsFull
큐가 가득 찼는지 판단하는 메서드. 가득 찼으면 true, 그렇지 안흐면 false를 반환한다. 

 

○모든 데이터를 출력하는 메서드 dump
큐에 인큐된 모든(num개)데이터를 프런트에서 리어 순으로 출력하는 메서드다. 큐가 비어 있으면 
'큐가 비어 있습니다'라고 표시한다 

import java.util.Scanner;
// int형 큐의 사용 예

class IntQueueTester {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		IntQueue s = new IntQueue(64);	// 최대 64개를 인큐할 수 있는 큐

		while (true) {
			System.out.println("현재 데이터 수：" + s.size() + " / "
															  + s.capacity());
			System.out.print("(1)인큐　(2)디큐　(3)피크　" +
								  "(4)덤프　(0)종료：");

			int menu = stdIn.nextInt();
			if (menu == 0) break;

			int x;
			switch (menu) {
			 case 1: 							// 인큐
				System.out.print("데이터：");
				x = stdIn.nextInt();
				try {
					s.enque(x);
			 	} catch (IntQueue.OverflowIntQueueException e) {
					System.out.println("큐가 가득 찼습니다.");
				}
				break;

			 case 2: 							// 디큐
				try {
			 		x = s.deque();
					System.out.println("디큐한 데이터는 " + x + "입니다.");
			 	} catch (IntQueue.EmptyIntQueueException e) {
					System.out.println("큐가 비어 있습니다.");
				}
				break;

			 case 3: 							// 피크
				try {
			 		x = s.peek();
					System.out.println("피크한 데이터는 " + x + "입니다.");
			 	} catch (IntQueue.EmptyIntQueueException e) {
					System.out.println("큐가 비어 있습니다.");
				}
				break;

			 case 4: 							// 덤프
				s.dump();
				break;
			}
		}
	}
}

-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893