[Data Structure] 큐(Queue)란?

1. 큐(Queue)의 개념

큐(Queue)

큐(Queue)는 "줄을 서다"라는 의미를 갖고 있으며, 입구와 출구가 모두 뚫려 있는 터널과 같은 형태이다.

사람이 줄을 서서 기다린다는 것처럼 먼저 들어온 데이터가 먼저 나가는 형태의 구조로 LIFO(Last In First Out) 방식인 스택(Stack)과는 달리 FIFO(First In First Out)방식을 가지고 있다.  

 

Enqueue는 큐(Queue)에 데이터를 입력하는 동작이고, Dequeue는 큐(Queue)에 데이터를 출력하는 동작이다.

 

2. 스택(Stack)에서의 오버플로우(Overflow)와 언더플로우(Underflow)

- 오버플로우(Overflow) : 큐(Queue)의 크기만큼 데이터가 꽉 차서 데이터를 넣지 못할 때 발생한다.

- 언더플로우(Underflow) : 큐(Queue)이 비어 있는 상황에서 데이터를 꺼내려고 할 경우에 발생한다.

 

3. 자바(Java) 라이브러리 큐(Queue) 관련 메서드

큐(Queue) 관련 메서드

3 - 1. 데이터 추가( add(item), offer(item) )

공통점

- 큐(Queue)의 가장 뒷부분에 데이터를 추가하며 값 추가 성공 시 true를 반환한다.

 

차이점

- add(item) : 큐(Queue)가 꽉 찬 경우(Overflow), IllegalStateException 에러가 발생한다.

- offer(item) : 큐(Queue)가 꽉 찬 경우(Overflow), false를 반환한다. 

3 - 2. 데이터 삭제( remove(), poll() )

공통점

- 큐(Queue)의 가장 앞부분의 데이터를 반환 후 삭제한다.

 

차이점

- remove() : 큐(Queue)가 비어있을 경우(Underflow) NoSuchElementException 에러가 발생한다.

- pull() : 큐(Queue)가 비어있을 경우(Underflow) null를 반환한다. 

3 - 3. 데이터 읽기 ( element(), peek() )

공통점

- 큐(Queue)의 가장 앞부분의 데이터를 읽는다.

 

차이점

- element() : 큐(Queue)가 비어 있는 경우(Underflow) NoSuchElementException 에러가 발생한다.

- peek() : 큐(Queue)가 비어 있는 경우(Underflow)  null을 반환한다.

 

3 - 4. 기타(clear(), isempty())

- clear() : 큐(Queue)를 비운다.

- isempty() : 큐(Queue)가 비었는지 확인한다. 

 

4. 큐(Queue) 의 Enqueue와 Dequeue

- Enqueue : 큐(Queue)의 맨 뒤에 데이터를 추가

- Dequeue : 큐(Queue)의 맨 앞에 데이터를 삭제

 

5. 큐(Queue) 구현

import java.util.*

public class Main{
	public static void main(String[] args){
		Queue<Intger> s = new LinkedList<>(); // int형 큐(Queue) 선언
		
		s.offer(5);	// 큐(Queue)에 5추가
		s.offer(2);	// 큐(Queue)에 2추가
		s.offer(3);	// 큐(Queue)에 3추가
		s.offer(7);	// 큐(Queue)에 7추가
		s.poll();	// 큐(Queue)에 5삭제
		s.offer(1);	// 큐(Queue)에 1추가
		s.offer(4);	// 큐(Queue)에 4추가
		s.poll(); 	// 큐(Queue)에 2추가

		while(!s.empty()){
			System.out.print(s.poll() + " ");//poll() 먼저 들어온 원소부터 추출!
		}
	}
}
//실행 결과 ==> 3 7 1 4

 

6. 큐(Queue) 사용 사례

- 순서대로 처리 되는 것

- 프로세스 관리

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

- 캐시(Cache)