[Java] 배열로 Queue를 구현해보자!

Queue는 FIFO(First In First Out)의 구조를 가진 자료구조로 BFS를 구현할 때 많이 사용이 됩니다. 라이브러리가 있다면 사용하면 간단하게 Queue를 이용할 수 있지만 라이브러리를 쓰지 못하는 곳에서는 Queue를 구현해야만 합니다.

그렇다고 Queue를 구현하기에는 먼가 벅차게 느껴질 때!!! Queue에 들어가는 자료의 개수가 어느정도 일지 대략적으로라도 알 수 있을 경우는 배열을 이용해서 Queue처럼 사용할 수 있습니다! 

int[] queue = new int[100];

예제로 사용할 queue라는 이름의 배열을 만들었습니다. 이제 queue 배열 안의 index를 가르킬 2개의 변수를 선언하겠습니다.

int front = -1;
int end = -1;

front는 queue 배열의 앞부분 즉, FIFO 를 구현하기 위해서 앞에서부터 자료를 선택하기 위한 변수입니다.

end는 queue 배열의 빈 공간 즉, 후에 들어온 자료를 넣어주기 위한 변수입니다.

queue에 자료를 넣어보겠습니다. int형 배열이므로 int형 변수를 넣어주었습니다.

queue[++end] = 3;

3을 넣어주었습니다. 몇 개의 자료를 더 넣어줘 보겠습니다.

queue[++end] = 7;
queue[++end] = 8;
queue[++end] = 1;
queue[++end] = 2;

빈 공간을 가리키는 end 변수를 +1 씩 시켜주면서 배열의 빈공간에 변수들을 넣어주었습니다. 이제 넣은 변수들을 꺼내보겠습니다.

1

int data = queue[++front];

간단하게 앞쪽부터 자료를 가리키는 front 변수를 +1 시켜줌으로서 처음 넣었던 자료에 접근하였습니다. 나머지 자료들도 모두 꺼내보겠습니다.

data = queue[++front];
data = queue[++front];
data = queue[++front];
data = queue[++front];

나머지 자료들도 front 값을 +1 씩 시켜줌으로서 FIFO 구조에 알맞게 앞서 넣은 자료에 먼저 접근하도록 하였습니다.

위의 배열이 queue와 같이 FIFO 구조로 잘 동작하고 있는지 출력을 해보았습니다. 최종 코드는 다음과 같습니다.

int[] queue = new int[100];
int front = -1;
int end = -1;
 
System.out.println("3 넣음");
queue[++end] = 3;
System.out.println("7 넣음");
queue[++end] = 7;
System.out.println("8 넣음");
queue[++end] = 8;
System.out.println("1 넣음");
queue[++end] = 1;
System.out.println("2 넣음");
queue[++end] = 2;
 
int data = queue[++front];
System.out.println(data+" 뻄");
data = queue[++front];
System.out.println(data+" 뻄");
data = queue[++front];
System.out.println(data+" 뻄");
data = queue[++front];
System.out.println(data+" 뻄");
data = queue[++front];
System.out.println(data+" 뻄");

출력은 다음과 같이 잘 나왔습니다.

3 넣음
7 넣음
8 넣음
1 넣음
2 넣음
3 뻄
7 뻄
8 뻄
1 뻄
2 뻄

queue에 넣을 자료의 개수만 대략적으로 알 수 있다면 그보다 넉넉히 배열을 선언해서 Queue의 역활로 사용할 수 있는 것에 대해 알아보았습니다! 다음엔 Class를 이용해서 실제 Queue를 구현해 보겠습니다.