먼저 들어간 데이터가 먼저 나오는 구조 (선입선출) (FIFO, First-In, First-Out)
마트에서 계산 대기할 때, 영화관 입장 시 등등
데이터 삽입 시 위치를 알기 위한 Rear 변수 필요 데이터 반환 시 위치를 알기 위한 Front 변수 필요
데이터 삽입과 반환이 이루어지는 위치가 다름 (스택은 동일한 위치에서 pop과 push가 이루어지지만, 큐는 Rear, Front를 통해 위치를 알아내야 함)
추상자료형 (ADT)
자료형
반환값
설명
initialize()
void
큐(Queue) 초기화
isEmpty()
boolean
큐가 비어있는지 확인
enqueue(Data)
void
큐에 데이터 삽입
dequeue()
Data
맨 앞에 있는 데이터 반환 및 삭제
peek()
Data
맨 앞에 있는 데이터 반환 후 삭제하지 않음
배열기반 큐 구현
삽입
삭제
삭제 과정의 문제점 - 아래와 같이 Rear가 배열의 끝까지 이동했지만, 삭제된 공간에는 데이터가 저장되지 않음
- dequeue 시 삭제된 빈 공간을 뒤에 데이터들이 채워줘야하는데, 잦은 데이터의 이동이 발생할 경우 성능에 문제가 생길 수 있어 이를 해결하기 위해 front와 rear의 위치만 변경하도록 해야함
해결방법 - rear와 front가 가리키는 인덱스가 배열의 크기보다 클 경우 front또는 rear값을 0으로 설정하여 배열의 첫번째를 가리킬 수 있도록 함 (원형 큐)
구현 Queue 인터페이스 구현
package Queue;
publicinterfaceQueue{
// 큐(Queue) 초기화voidinitialize();
// 비어있는지 확인booleanisEmpty();
// 큐에 데이터 삽입voidenqueue(Object data);
// 큐의 맨 앞에있는 데이터 반환 후 삭제Object dequeue();
// 큐의 맨 앞에있는 데이터 반환 후 삭제하지 않음Object peek();
}
Queue 구현
package Queue.Array;
import Queue.Queue;
publicclassArrayQueueimplementsQueue{
privatefinalstaticint QUEUE_SIZE = 5;
int frontIndex = 0;
int rearIndex = 0;
int countOfData = 0;
Object[] queue = null;
@Overridepublicvoidinitialize(){
queue = new Object[QUEUE_SIZE];
frontIndex = 0;
rearIndex = 0;
countOfData = 0;
}
@OverridepublicbooleanisEmpty(){
if (countOfData == 0){
returntrue;
}
returnfalse;
}
@Overridepublicvoidenqueue(Object data){
if (countOfData == QUEUE_SIZE){
System.out.println("더이상 데이터를 추가할 수 없습니다.");
return;
}
// 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 rear를 0으로 초기화if (rearIndex == QUEUE_SIZE){
rearIndex = 0;
}
countOfData++;
queue[rearIndex++] = data;
}
@Overridepublic Object dequeue(){
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
returnnull;
}
// 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 front를 0으로 초기화if (frontIndex == QUEUE_SIZE){
frontIndex = 0;
}
countOfData--;
return queue[frontIndex++];
}
@Overridepublic Object peek(){
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
returnnull;
}
return queue[frontIndex];
}
}
테스트 구현
package Queue.Array;
import Queue.Queue;
publicclassArrayQueueMain{
publicstaticvoidmain(String[] args){
Queue queue = new ArrayQueue();
queue.initialize();
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
// 데이터 삽입 후 출력
System.out.println("데이터 삽입 후 출력");
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
System.out.println("데이터 삭제 후 하나 추가 출력 ");
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
queue.enqueue(6);
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
}
}
연결 리스트 기반 큐 구현
배열 기반의 큐와 동일하게 front와 rear 변수 필요
삽입 시 첫 번째 노드와 두 번째 이후의 노드 추가 과정이 다름
삽입
삭제 - front로 큐가 비어있는지 판별할 수 있기 때문에 삭제 시 rear는 신경쓰지 않아도 됨
구현
- 인터페이스는 동일하게 구현
LinkedList 큐 구현
package Queue.LinkedList;
import Queue.Queue;
publicclassLinkedListQueueimplementsQueue{
classNode{
Object data;
Node nextNode;
}
Node front = null;
Node rear = null;
int countOfData = 0;
@Overridepublicvoidinitialize(){
front = null;
rear = null;
countOfData = 0;
}
@OverridepublicbooleanisEmpty(){
if (front == null){
returntrue;
}
returnfalse;
}
@Overridepublicvoidenqueue(Object data){
Node newNode = new Node();
newNode.data = data;
// 큐가 비어있는 경우 첫 번째 노드 추가if (isEmpty()){
front = newNode;
rear = newNode;
}
// 두 번째 이후의 노드 추가일 경우 rear의 다음 node 주소를 설정 후 rear값 변경else {
rear.nextNode = newNode;
rear = newNode;
}
countOfData++;
}
@Overridepublic Object dequeue(){
if (isEmpty()){
System.out.println("데이터가 없습니다.");
returnnull;
}
// 제일 앞 쪽 데이터 반환
Object data = front.data;
// front의 다음 노드를 front로 변경
front = front.nextNode;
return data;
}
@Overridepublic Object peek(){
if (isEmpty()){
System.out.println("데이터가 없습니다.");
returnnull;
}
return front.data;
}
}
테스트 구현
package Queue.LinkedList;
import Queue.Queue;
publicclassLinkedListQueueMain{
publicstaticvoidmain(String[] args){
Queue queue = new LinkedListQueue();
queue.initialize();
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
// 데이터 삽입 후 출력
System.out.println("데이터 삽입 후 출력");
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
System.out.println("데이터 삭제 후 하나 추가 출력 ");
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
queue.enqueue(6);
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
}
}
