자바(Java) Queue 클래스 및 예제

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. 큐(Queue)

- 큐(Queue)는 컴퓨터의 기본 자료구조 중 하나로, 줄을 지어 순서대로 처리하는 처리하는 자료구조라고 할 수 있다. 큐는 LIFO(Last-In First-Out)의 특징을 가진 스택(Stack)과 다르게 FIFO(First-In First-Out)의 특징을 가지고 있다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조를 말한다. 

 

2. 큐(Queue)의 사용 사례

- 큐(Queue)는 우리가 실생활에서도 사용되는 사례를 볼 수 있다.

- 프린터를 할 때 먼저 프린터를 한 사람이 문서가 프린터가 된다던지.

- 너비 우선 탐색(BFS, Breadth-First Search)

- 캐시(Cache)

- 티켓 카운터(먼저 줄 선 사람이 티켓을 가져가는 것처럼)
- 윈도우 시스템 메시지 처리기

- 프로세스 관리

 

3. 큐의 연산

- 큐(Queue)는 FIFO(First-In First-Out) 특징을 가진다.

 

* 아래의 3개는 큐(Queue)에서 오버플로우(Overflow)나 언더플로우(Underflow)가 발생하면 예외를 던진다.

1) add(A) : A를 큐(Queue)에 넣는다.

2) remove() : 맨 처음에 들어간 데이터를 제거한다.

3) element() : 큐(Queue)에서 가장 앞에 있는 것을 반환한다.

 

* 아래의 3개는 큐(Queue)에서 오버플로우(Overflow)나 언더플로우(Underflow)가 발생하면 null 또는 false를 반환한다.

4) offer(A) : A를 큐(Queue)에 넣는다. 

5) poll() : 맨 처음에 들어간 데이터를 제거한다.

6) peek() : 큐(Queue)에서 가장 앞에 있는 것을 반환한다.

 

7) isEmpty() : 큐(Queue)가 비어있으면 true, 비어있지 않으면 false를 반환한다.

 

4. 큐(Queue)에서의 오버플로우(Overflow)와 언더플로우(Underflow)

1) 오버플로우(Overflow)

- 큐(Queue)의 크기만큼 데이터가 꽉 차서 데이터를 넣지 못할 때

 

2) 언더플로우(Underflow)

- 큐(Queue)가 비어있는데, 데이터를 꺼내려고 하는 경우

 

5. 큐(Queue)의 종류

1) 선형 큐(Queue)

- 선형 큐(Queue)는 스택처럼 생긴 큐(Queue)를말한다.

- 크기가 제한되어 있고, 큐(Queue)에서 삭제가 일어나면 삭제된 자리는 비어있게 된다.

- 그렇기에 비어있는 자리를 옮겨야 하는 단점을 가지고 있다.

 

2) 환형 큐(Queue)

- 선형 큐(Queue)의 단점을 보완하기 위해 만들어진 큐(Queue)

- 큐(Queue)에서 front가 큐의 크기가 되면 데이터를 다시 앞으로 보내어 원형으로 큐(Queue)구현

 

3) 링크드 큐(Queue)

- 연결리스트로 구현한 큐(Queue)로, 큐의 크기를 쉽게 늘릴 수 있는 장점을 가지고 있다.

- 큐(Queue)의 크기를 쉽게 늘릴 수 있어 삽입, 삭제가 용이하고, 오버플로우가 발생하지 않는다.

 

6. 큐(Queue)의 Enqueue와 Dequeue)

1) Enqueue

- 큐의 맨 뒤에서 데이터를 추가

 

2) Dequeue

- 큐의 맨 앞에서 데이터를 삭제

 

7. 링크드리스트(LinkedList)를 사용한 큐(Queue) 구현

1) 큐(Queue) 선언

- 큐(Queue)는 링크드리스트(LinkeList)를 사용하여 생성해야 하기 때문에, 아래를 import해야 합니다.

- import java.util.LinkedList;

- import java.util.Queue;

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		// LinkedList를 이용한 Int형 Queue 선언 
		Queue<Integer> int_Queue = new LinkedList<>();
		
		//LinkedList를 이용한 String형 Queue 선언
		Queue<String> string_Queue = new LinkedList<>();
	}
}

 

2)큐(Queue)의 추가

// LinkedList를 이용한 Int형 Queue 선언 
		Queue<Integer> int_Queue = new LinkedList<>();
				
		int_Queue.add(1); //int_Queue에 1추가
		int_Queue.add(2); //int_Queue에 2추가
		int_Queue.add(3); //int_Queue에 3추가

 

3)큐(Queue)의 삭제

// LinkedList를 이용한 Int형 Queue 선언 
		Queue<Integer> int_Queue = new LinkedList<>();
				
		int_Queue.add(1); //int_Queue에 1추가
		int_Queue.add(2); //int_Queue에 2추가
		int_Queue.add(3); //int_Queue에 3추가
		
		int_Queue.poll(); //int_Queue 앞에 삭제
		int_Queue.remove(); //int_Queue 앞에 삭제

 

8. 우선순위 큐(PriorityQueue) 구현

import java.util.PriorityQueue;

public class Solution {
	public static void main(String[] args) {
		//int형 PriorityQueue
		PriorityQueue<Integer> int_PriorityQueue = new PriorityQueue<>();

		//int형 PriorityQueue(우선순위 높은 순)
		PriorityQueue<Integer> int_PriorityQueue = new PriorityQueue<>(Collections.reverseOrder());

		//String형 PriorityQueue
		PriorityQueue<String> string_PriorityQueue = new PriorityQueue<>(); 

		//String형 PriorityQueue(우선순위 높은 순)
		PriorityQueue<String> string_PriorityQueue = new PriorityQueue<>(Collections.reverseOrder());