자바_Queue

1. 큐(Queue)란?

: Queue는 사전적으로 "줄을 서다"를 의미한다. 줄을 서서 기다린다는 것처럼 먼저 들어오면 데이터가 먼저 나가는 형식이며, 일명 FIFO(FirstInFirstOut) 방식이다.

위의 그림에서 볼 수 있듯이 큐는 앞과 뒤가 다른 역할을 수행한다. 큐의 앞 부분인 front는 삭제 연산만 수행

큐의 뒷 부분인 rear는 삽입 연산만 수행한다.

 

2. 구현 방식

지난 번과 마찬가지로 자바를 통해 import 방식이 아니라 직접 구현해 보도록 하겠다.

[MyQueue.java]

public class MyQueue {
	
	// 배열 길이 5로 고정
	private final int LEN = 5;
	private int[] arr = new int[LEN];
	
	// front와 rear 변수를 통해 처음과 끝 가쥰울 잡음
	// 동일 위치로 잡음
	// 데이터 삽입 시 rear가 한 칸씩 뒤로 밀림
	private int frontIdx = 0;
	private int rearIdx = 0;
	
	// 데이터 삽입 위치를 알아야 함 -> rearIdx 이용, 인덱스 0으로 지정
	public void push(int _data) {
		// rearIdx가 전체 배열의 길이를 벗어나는지 검사
		// 배열이 가득 찼다면 더이상 데이터를 추가할 수 없음
		if (isFull()) {
			System.out.println("Queue Overflow");
			return;
		}
		
		// frontIdx가 0이 아니고, rearIdx가 LEN이면 전체 데이터를 앞으로 이동
		if (frontIdx > 0 && rearIdx == LEN) {
			System.out.println("Repositioning");
		
		// 비어있는 공간만큼 앞으로 이동해야 함
			for (int i = frontIdx; i < rearIdx; ++i) {
				System.out.println(
                        i + "(" + arr[i] + ") -> " +
                        (i - frontIdx) + "(" + arr[i - frontIdx] + ")");

				arr[i - frontIdx] = arr[i]; 
			}
			// rearIdx의 위치 역시 이동해야 함
			rearIdx -= frontIdx;
			frontIdx = 0;
			
			System.out.println(
                    "Done: F(" + frontIdx + "), R(" + rearIdx + ")");
        }
		
		// frontIdx가 0이고, rearIdx가 LEN이 아니면 rearIdx 자리에 데이터 추가
		// rearIdx 위치에 데이터 삽입
		arr[rearIdx] = _data;
		// rearIdx 한 칸 이동
		++rearIdx;
	}
	
	public int pop() {
		if (isEmpty()) {
			System.out.println("EMPTY!!");
			return -1;
		}
		
		// 데이터가 빠질 때마다 frontIdx를 뒤로 이동
		int returnData = arr[frontIdx];
		++frontIdx;
		
		// frontIdx랑 rearIdx가 같으면 현재 데이터가 없다는 의미이므로 맨 앞으로 위치를 초기화시킴
		if (frontIdx == rearIdx) {
			frontIdx = rearIdx = 0;
		}
		
		return returnData;
	}
	
	// 데이터 꽉 찼는지 확인 기능
	public boolean isFull() {
		return frontIdx == 0 && rearIdx == LEN;
	}
	
	 // 데이터가 없는 경우
	public boolean isEmpty() {
		// frontIdx와 rearIdx의 위치가 같은 경우를 보면 됨
		return frontIdx == rearIdx;
	}
	
	
	public void printAll() {
		System.out.println("---------------------");
		if (isEmpty()) {
			System.out.println("printAll EMPTY");
		}
		else {
			for (int i = frontIdx; i < rearIdx; ++i) {
				System.out.println(i + ": " +arr[i]);
			}
		}
		System.out.println("---------------------");
	}
}

 

[Main.java]

public class Main {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(10);
        queue.push(20);
        queue.push(30);
        queue.push(40);
        queue.push(50);
        queue.push(60);
        queue.printAll();
        
        for (int i = 0; i < 7; ++i)
            System.out.println("pop: " + queue.pop());
        
        System.out.println("=====================");
        
        for (int i = 0; i < 5; ++i)
            queue.push((i + 1) * 100);
        System.out.println("pop: " + queue.pop());
        System.out.println("pop: " + queue.pop());
        queue.push(1234);
        queue.printAll();
  	}
}

해당 코드의 결과는 다음과 같다.