안녕하세요 오늘은 자료구조의 스택의 반대 개념인 큐(Queue)에 대해 알아보겠습니다.
Queue는 스택과는 다르게 가장 먼저 들어간 데이터가 가장 먼저 나가는 구조를 말합니다.
'선입선출'이라고 하며, First In First Out(FIFO)라고도 합니다. 예시로, 은행에 번호표가 있습니다.
은행에 가면 대기표를 발급받아 기다리는데, 번호표를 먼저 뽑은 순서대로 부르는 구조가 바로 Queue 구조입니다.
Enqueue : 데이터에 큐를 넣는 동작
Dequeue : 큐에서 데이터를 꺼내는 동작
1. 선형 Queue 분석
선형 Queue는 1차원 배열을 사용하여 구현합니다. Shift를 해서 앞으로 땡겨지는데, 이러한 구조 자체가 비효율적이라는 단점이 있습니다. 이러한 문제를 해결하기 위해 나온 개념이 원형 Queue입니다. 원형 Queue는 선형 Queue의 반복적 데이터 이동의 단점을 보완한 알고리즘입니다. Front와 Rear가 큐 사이즈 내에서 회전합니다. 원형 Queue는 다음 시간에 알아보겠습니다.
2. 코드 구현
① 필드
package queue;
import java.util.Scanner;
public class Queue {
int[] queue; //queue배열
int front; //queue의 맨 앞
int rear; //queue의 맨 뒤
Scanner sc; //스캐너queue 패키지를 만들고, Scanner를 import 합니다. 필드에는 Queue 배열과, Queue 배열의 맨 앞인 front, 맨 뒤인 rear, Scanner를 정의합니다.
② isFull 메서드
// 큐가 꽉 찼는지 확인
public boolean isFull() {
if (front == 0 && rear == queue.length) {
return true;
}
else {
return false;
}
}isFull 메서드는 Queue가 꽉 차있는지 확인합니다. front가 0이고, rear가 queue의 길이와 같다면 꽉 차있으니 true를 반환하고 아니면 false를 반환합니다.
③ shift 메서드
//데이터 쉬프트 연산
public void shift() {
if(front !=0 && rear == 5) {
while(front !=0) {
for(int i = front; i < rear; i++) {
queue[i-1] = queue[i];
queue[i] = 0;
}
front--;
rear--;
}
}
}shift 메서드는 front가 0이 아니고, rear가 5일 때, 뒤에 있는 데이터를 앞으로 옮겨주는 역할을 합니다.
④ enqueue 메서드
// 큐에 데이터를 넣음
public void enqueue() {
if (isFull()) {
System.out.println("큐가 꽉찼습니다.");
return;
}
// 데이터 입력
shift();
System.out.println("Input your data");
int data = sc.nextInt();
queue[rear] = data;
rear++;
}enqueue 메서드는 큐에 데이터를 넣는 메서드입니다. 만약 큐에 데이터가 가득 차 있으면 isFull 메서드를 조건에 넣어주고, 하나라도 비어 있으면 데이터를 입력받아 큐에 넣어줍니다.
⑤ dequeue 메서드
// 큐에 데이터를 뺌
public boolean dequeue() {
queue[front] = 0;
front++;
return true;
}dequeue 메서드는 큐에서 데이터를 빼는 메서드입니다. 현재 front의 값을 제거해 주고 front 값에 1을 더해줍니다.
⑥ print 메서드
// 화면 출력 및 선택
public void print() {
while (true) {
System.out.println("=======선형 Queue=======");
System.out.println("1. Enqueue || 2. Dequeue || 3. Exit");
System.out.print("Select : ");
int num = sc.nextInt();
// 선택 1. Enqueue
if (num == 1) {
enqueue();
for (int i = 0; i < queue.length; i++) {
System.out.print(queue[i] + " ");
}
System.out.println("Enqueue 성공");
}
else if (num == 2) {
boolean check = false;
check = dequeue();
if (check == true) {
System.out.println("Dequeue 성공");
}
for (int i = 0; i < queue.length; i++) {
System.out.print(queue[i] + " ");
}
System.out.println();
}
else if (num == 3) {
System.out.println("Finish");
break;
}
}
}print 메서드는 화면에 출력을 해줍니다. 사용자로부터 Enqueue 인지 Dequeue 인지 입력을 받아 메서드를 불러옵니다. 데이터 0을 넣으면 화면에서 볼 수 없기 때문에 Enqueue와 Dequeue가 성공했다고 출력해 줬습니다.
⑦ 생성자
// 생성자에서 초기화
public Queue() {
queue = new int[5];
front = 0;
rear = 0;
sc = new Scanner(System.in);
}필드 값들을 생성자에서 초기화했습니다. 필드에서 직접 초기화 하지 않고, 생성자에서 따로 초기화했습니다.
⑧ main 함수
public static void main(String[] args) {
Queue q = new Queue();
q.print();
}
}main 함수에서는 Queue 생성자 q를 만들고, q.print();로 print 메서드를 불러왔습니다. main 함수는 최대한 간결하게 작성하였습니다.
3. 실행 결과
정상적으로 출력되는 것을 확인할 수 있습니다.
