[자료구조] 자바 - 큐(Queue)이란?

 

안녕하세요 이번 포스팅은 바로

"자료구조 중 큐(Queue)"

입니다

 

자료구조는 컴퓨터공학과처럼 코딩하는 전공을

진학하면 배우는 과목입니다.

​

지금 배우는 주제인 큐는 스택과 더불어 가장 기초적이면서도

다른 곳에서도 많이 쓰인다고 보시면됩니다.

​

이러한 큐를 두가지 방법으로 해보겠습니다.

하나는 직접 큐함수(add,delete)를 만들어보는 것이고

​

또 다른 하나는 기존에 있던 라이브러리를 통해

큐 함수(add,delete)를 써보는 것입니다.

 

 

큐(Queue)의 정의

---

한 쪽 끝에서만 삽입과 삭제가 이루어지는 스택과는 달리

한 쪽 끝에서는 삭제, 반대쪽 끝에서는 삽입만 가능한 순서화 리스트이다.

그리고 가장 먼저 삽입된 원소가 가장 먼저 삭제되는 형태인데 

이는 First in First out(FIFO)라 불린다.

 

삽입과 삭제가 이루어지는 함수 add와 delete가 존재하며

add는 rear의 위치에서 발생하고 delete는 front의 위치에서 발생한다.

이런 식으로 rear에서는 삽입이 이루어지고 front에서는 삭제가 이루어진다.

 

 

 

큐(Queue) 직접 구현 - JAVA

---

<변수선언>

	static int rear = -1;
	static int front = -1;	
	static int full;
	static Integer[] queue;

 

스택은 한 곳에서 삽입과 삭제가 이루어지기 때문에 top 하나만 선언해주었지만

큐의 경우는 삽입,삭제가 반대 쪽에서 이루어지므로 rear,front 두 가지 변수를 선언합니다.

이때 rear,front 둘 다 -1로 초기화를 해주는데 이는 아직 값이 없다는 가정을 하는 것입니다.

 

그리고 full은 스택이 가득찼는 지 확인하기 위해 사용을 해줍니다.

stack은 큐를 배열로 설정해줍니다.

 

 

<ADD>

	static void add(int num) {
		if(rear+1==full)
			System.out.println("queue full");
		else
			queue[++rear] = num;
	
	}

rear는 삽입이 일어나는 곳인데 rear+1이 full의 위치와 같다면 스택이 가득찼음을 의미합니다.

이유는 num을 삽입할 때 전위연산자를 쓰기 때문에 if문에서도 +1을 해준 후 비교를 해줍니다.

그리고 if문을 통해 같으면 "stack full" 출력해줍니다.

 

else일 경우 스택에 값을 넣어주는데 이때 먼저 rear의 값을 증가시킨 뒤 num을 넣습니다.

이는 앞서 초기화에서  rear를 -1로 했는 이유이기도 합니다.

 

 

스택의 크기를 4로 주어 설정했기 때문에 add 함수 호출이 5번이 되는 시점 부터는

계속 "stack full"이 지속적으로 출력되는 것을 볼 수 있습니다.

 

 

<DELETE>

	static void delete() {
		if(rear==front)
			System.out.println("queue empty");
		else
			System.out.println(queue[++front]);
	}

delete 역시 if문이 존재하는데 이때 if문은 rear와 front를 비교해줍니다.

rear와 front가 같은 위치에 있다는 것은 스택에 값이 없다는 것을 의미하고 "stack empty"를 출력해줍니다.

이 역시 초기에 rear = -1 front = -1을 해주어 스택에 값이 없다는 것을 의미해줍니다

 

 

 

스택과는 다르게 delete를 했을 때 먼저 들어간 3 부터 나오는 것을 볼 수 있습니다.

또한, add를 3번 호출했기 때문에 delete가 4번 호출될 때 부터 "queue empty"를 출력하는 모습을 볼 수 있습니다.

 

 

 

 

 

 

 

큐(queue) 직접구현 - 최종코드

---

import java.util.Scanner;
public class Queue {	
	static int rear = -1;
	static int front = -1;	
	static int full;
	static Integer[] queue;	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		full = sc.nextInt();
		queue = new Integer[full];		
			
	}
	static void add(int num) {
		if(rear+1==full) {
			System.out.println("queue full");
		}
		else
			queue[++rear] = num;	
	}
	static void delete() {
		if(rear==front)
			System.out.println("queue empty");
		else
			System.out.println(queue[++front]);
	}

}

scanner를 이용해 배열의 크기를 받았습니다.

 

 

끝으로

---

이상으로 자료구조에 있어 가장 기초적이라고 할 수 있는

큐에 대해 알아보고 직접 구현해 보았습니다.

​

이보다 더 좋은 코드가 많기 때문에 작성된 코드는

단순 참고용으로 보시면 될 거 같습니다.

​

궁금한 점이나 문제점이 있으시면 댓글 남겨주시면 감사하겠습니다.

​

이상으로 읽어주셔서 감사합니다!!