[알고리즘 독학] 큐(Queue)

큐

 

스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조

but 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출인 점이 스택과 다름

 

인큐 : 데이터를 넣는 작업

디큐 : 데이터를 꺼내는 작업

 

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

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

 

링 버퍼 사용 - 배열 요소를 앞쪽으로 옮기지 않는 큐

프런트(front) : 맨 처음 요소의 인덱스

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

 

1. 큐로 사용할 배열(que) : 인큐하는 데이터를 저장하기 위한 큐 본체용 배열

 

2. 큐의 최대 용량(max) : 큐의 최대 용량을 저장하는 필드

 

3. 프런트(front) : 인큐하는 데이터 가운데 첫 번째 요소의 인덱스를 저장하는 필드

 

4. 리어(rear) : 인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 필드

 

5. 현재 데이터 수(num) : 큐에 쌓아 놓은 데이터 수를 나타내는 필드

 

생성자 IntQueue

 

인큐 메서드 enque

 

package search;

public class IntAryQueue {
		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 IntAryQueue(int capacity) {
			num = front = rear = 0;
			max = capacity;
			
			try {
				que = new int[max];
			} catch (OutOfMemoryError e) {
				max = 0;
			}
		}
		
		//큐에 데이테를 인큐
		public int enque(int x) throws OverflowIntQueueException{
			if(num >= max)
				throw new OverflowIntQueueException();
			que[rear++] = x;
			num++;
			if(rear == max)
				rear = 0;
			return x;
		}
		
		
		//큐에서 데이터를 디큐
		public int deque() throws EmptyIntQueueException {
			if(num <= 0)
				throw new EmptyIntQueueException();
			int x = que[front++];
			num--;
			if(front == max)
				front = 0;
			return x;
		}
		
		//큐를 비움
		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 >= num;
		}
		
		//큐 안의 모든 데이터를 프런트 -> 리어 순으로 출력
		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();
			}
		}
}