package queue;
/*
enpueue(Object o)
depueue()
peek()
isEmpty()
isFull()
indexOf()
clear()
*/
public interface QueueInterface<T> {
public void enQueue(T item);
public void deQueue();
public void peek();
public boolean isEmpty();
public boolean isFull();
public void indexOf(T key);
public void clear();
}
사용자 예외, 생성자, 인스턴스 변수
private T[] queue;
private int front, rear;
private int count, size;
/**
* 큐 기본 사이즈 10
*/
CircleQueue() {
this(10);
}
/**
* @param size 큐 사이즈 지정 변수
*/
CircleQueue(int size) {
try {
queue = (T[]) new Object[size];
this.size = size;
} catch (OutOfMemoryError oome) {
System.out.println("메모리 부족");
}
}
/**
* 사용자 예외 큐가 빈 상태
*/
private static class UnderFlow extends RuntimeException {
public UnderFlow() throws RuntimeException {
super("큐가 비어있는 상태");
}
}
/**
* 사용자 예외 큐가 가득 찬 상태
*/
private static class OverFlow extends RuntimeException {
public OverFlow() throws RuntimeException {
super("큐가 꽉찬 상태");
}
}
정적할당으로 배열 사이즈는 미리 정한다. 기본 사이즈는 10이다.
사용자 예외 OverFlow와 UnderFlow를 정의한 후 큐의 상태 메시지를 문자열로 넘긴다.
/**
* count기반 isEmpty 체크 count가 0보다 작거나 크면 큐에 아무것도 없는 상태
* front==rear 확인은 count기반이 아닌 큐 1자리 남기고 포화상태 체크할 때 사용하는 조건
*
* @return count<= 0 인 경우 false 반환
*/
@Override
public boolean isEmpty() {
//return front==rear;
return count <= 0;
}
/**
* count기반 isFull 체크 count가 size와 크거나 같으면 큐가 꽉 찬 상태이다.
* count기반 사용하기 싫다면 주석부분 삭제 후 사용
* 큐의 한 자리 남기고 포화상태 체크하는 알고리즘 (rear+1)%size == front인 경우 한자리를 제외한 rear==front이므로 포화
*
* @return count>=size 일 경우 true 반환
*/
@Override
public boolean isFull() {
//return ((rear+1)%size)==front; //마지막 자리 남기고 isFull 확인 가능
return count >= size;
}
주석 부분을 보면 알겠지만 isEmpty와 isFull은 사실 front==rear로 큐의 상태를 확인할 수 있다.
front==rear연산의 문제는 isEmpty와 isFull 둘 다 true가 되므로 큐가 비어있는지 포화상태인지 구별할 수 없다.
따라서 해당 코드에서는 count <=0는 큐 공백상태 확인 연산으로 사용하였고
포화상태 확인은 count변수 기반으로 count값이 큐의 size값과 동일하면 true 반환.
위 코드로 포화, 공백 상태 확인은 enqueue, dequeue 연산할 때 count를 증감 연산을 계속해줘야 한다.
count 변수를 관리하기 싫다면
큐의 한 자리는 계속 남겨 놓은 상태에서 (rear+1)%size==front 일 경우 포화상태라고 볼 수 있다.
return ((rear+1)%size)==front; //마지막 자리 남기고 isFull 확인 가능
return count >= size;
/**
* 순환 구조 시계 방향 (rear+1)%size , count 기반
*
* @param item 큐에 추가할 요소
* @throws OverFlow 큐 가득찬 상태 경우 예외 발생
*/
@Override
public void enQueue(T item) throws OverFlow {
if (isFull()) {
throw new OverFlow();
}
queue[rear] = item;
rear = (rear + 1) % size;
count++;
System.out.println(Arrays.toString(queue));
}
/**
* 순환 구조 시계 방향 (front+1)%front , count 기반
*
* @throws UnderFlow 큐가 빈 상태일 때 예외 발생
*/
@Override
public void deQueue() throws UnderFlow {
if (isEmpty()) {
throw new UnderFlow();
}
System.out.println("꺼낸 값: " + queue[front]);
front = (front + 1) % size;
count--;
System.out.println(Arrays.toString(queue));
}
enqueue: rear의 맨 초기값은 0이다. queue[rear]에 값을 먼저 넣은 후 rear를 증가시킨다.
일반적으로 rear++ 연산하면 선형 큐와 다를 게 없으므로 (rear+1)% SIZE로 rear값을 0~큐의 size-1 사이 값으로 순환하게 한다. ex) rear = 3 SIZE = 4 front = 0일 경우 (3+1)%4는 0이므로 front와 같다 포화상태인 것을 확인할 수 있다.
dequeue
peek(), indexOf()
/**
* 큐 front에 존재하는 값 출력
*
* @throws UnderFlow 큐가 빈 상태일 때 예외 바생
*/
@Override
public void peek() throws UnderFlow {
if (isEmpty()) {
throw new UnderFlow();
}
System.out.println(queue[front]);
}
/**
* 순차 탐색으로 배열안에 값 찾는 메서드
*
* @param key 메서드 호출 시 인수로 넘어올 값을 큐에 존재하는지 순차 탐색한다.
*/
@Override
public void indexOf(T key) {
int copyFront = front;
for (int i = 0; i < count; i++) {
if (key.equals(queue[copyFront])) {
System.out.println("해당 " + key + " 는 index queue[" + copyFront + "]에 있습니다.");
return;
}
copyFront = (copyFront + 1) % size;
}
}
peek(): 큐의 출구 쪽 (front) 쪽에 가장 가까운 요소 출력
indexOf(T key): front값부터 시작하여 for문의 지역변수 i를 계속 더해 순차적으로 탐색한다. 여기서 count변수 대신 size변수를 사용하여 반복문의 횟수를 관리해도 된다. 탐색할 때 front값은 (front+1) % SIZE로 size값을 초과하지 않게 한다.
package queue;
import java.util.Arrays;
public class CircleQueue<T> implements QueueInterface<T> {
private T[] queue;
private int front, rear;
private int count, size;
/**
* 큐 기본 사이즈 10
*/
CircleQueue() {
this(10);
}
/**
* @param size 큐 사이즈 지정 변수
*/
CircleQueue(int size) {
try {
queue = (T[]) new Object[size];
this.size = size;
} catch (OutOfMemoryError oome) {
System.out.println("메모리 부족");
}
}
/**
* 사용자 예외 큐가 빈 상태
*/
private static class UnderFlow extends RuntimeException {
public UnderFlow() throws RuntimeException {
super("큐가 비어있는 상태");
}
}
/**
* 사용자 예외 큐가 가득 찬 상태
*/
private static class OverFlow extends RuntimeException {
public OverFlow() throws RuntimeException {
super("큐가 꽉찬 상태");
}
}
/**
* 순환 구조 시계 방향 (rear+1)%size , count 기반
*
* @param item 큐에 추가할 요소
* @throws OverFlow 큐 가득찬 상태 경우 예외 발생
*/
@Override
public void enQueue(T item) throws OverFlow {
if (isFull()) {
throw new OverFlow();
}
queue[rear] = item;
rear = (rear + 1) % size;
count++;
System.out.println(Arrays.toString(queue));
}
/**
* 순환 구조 시계 방향 (front+1)%front , count 기반
*
* @throws UnderFlow 큐가 빈 상태일 때 예외 발생
*/
@Override
public void deQueue() throws UnderFlow {
if (isEmpty()) {
throw new UnderFlow();
}
System.out.println("꺼낸 값: " + queue[front]);
front = (front + 1) % size;
count--;
System.out.println(Arrays.toString(queue));
}
/**
* 큐 front에 존재하는 값 출력
*
* @throws UnderFlow 큐가 빈 상태일 때 예외 바생
*/
@Override
public void peek() throws UnderFlow {
if (isEmpty()) {
throw new UnderFlow();
}
System.out.println(queue[front]);
}
/**
* count기반 isEmpty 체크 count가 0보다 작거나 크면 큐에 아무것도 없는 상태
* front==rear 확인은 count기반이 아닌 큐 1자리 남기고 포화상태 체크할 때 사용하는 조건
*
* @return count<= 0 인 경우 false 반환
*/
@Override
public boolean isEmpty() {
//return front==rear;
return count <= 0;
}
/**
* count기반 isFull 체크 count가 size와 크거나 같으면 큐가 꽉 찬 상태이다.
* count기반 사용하기 싫다면 주석부분 삭제 후 사용
* 큐의 한 자리 남기고 포화상태 체크하는 알고리즘 (rear+1)%size == front인 경우 한자리를 제외한 rear==front이므로 포화
*
* @return count>=size 일 경우 true 반환
*/
@Override
public boolean isFull() {
return ((rear + 1) % size) == front; //마지막 자리 남기고 isFull 확인 가능
//return count >= size;
}
/**
* 순차 탐색으로 배열안에 값 찾는 메서드
*
* @param key 메서드 호출 시 인수로 넘어올 값을 큐에 존재하는지 순차 탐색한다.
*/
@Override
public void indexOf(T key) {
int copyFront = front;
for (int i = 0; i < count; i++) {
if (key.equals(queue[copyFront])) {
System.out.println("해당 " + key + " 는 index queue[" + copyFront + "]에 있습니다.");
return;
}
copyFront = (copyFront + 1) % size;
}
}
/**
* 큐를 초기화하는 메서드 rear, front, count도 모두 0으로 값을 바꾼다.
*/
@Override
public void clear() {
queue = (T[]) new Object[size];
front = 0;
rear = 0;
count = 0;
}
}
Main 코드
package queue;
public class Main {
public static void main(String[] args) {
CircleQueue<Integer> circleQueue = new CircleQueue<>(7);
for (int i = 0; i < 6; i++) {
circleQueue.enQueue(i);
}
circleQueue.deQueue();
circleQueue.deQueue();
circleQueue.peek();
circleQueue.enQueue(6);
circleQueue.enQueue(7);
circleQueue.indexOf(3);
circleQueue.clear();
}
}
