선형자료구조 - 큐

📌 큐

1. 선입선출(First In First Out; FIFO) 자료구조

- 먼저 들어온 데이터가 먼저 나가는 구조

 

 

2. 입력 순서대로 데이터 처리가 필요할 때 사용

- ex) 프린터 출력 대기열, BFS(Breath-First Search) 등

- 프린터 출력 대기열 : 문서 작업 요청 후 여러 개가 쌓이면 가장 먼저 요청한 작업을 수행, PC가 종료되어도 프린터 내부 Pool에서 큐 구조로 먼저 들어온 요청을 수행

 

- BFS(Breath-First Search) : 트리 구조, 너비 우선 탐색으로 root 상단부터 시작해 아래로 진행하는 데이터 탐색 등

 

너비 우선 탐색(BFS) 알고리즘 (출처 : https://www.geeksforgeeks.org/level-order-tree-traversal)

 

 

 

 

큐 기본 구조

• 선입선출(FIFO) 구조를 따름

 

• 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐

 

큐 기본 구조 (출처 : https://minosaekki.tistory.com/11)

 

• 큐에서 데이터가 꺼내지는 곳은 Front, 꺼내는 동작은 Dequeue

 

• 큐에서 데이터가 추가되는 곳은 Rear, 추가 동작은 Enqueue

 

 

 

큐 기본 연산

• 데이터 추가(Enqueue)
  • 큐에 데이터 추가
    
    

 

• 데이터 꺼내기(Dequeue)
  • 큐에서 데이터 꺼내기

 

큐 기본 연산 (출처 : https://coding-factory.tistory.com/602)

 

 

 

큐 기본 코드

import java.util.LinkList;
import java.util.Queue;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
        
 		// queue queue = new Queue();
        // 위 queue는 내부함수로 인터페이스로 구현이 되어있기 때문에 바로 객체를 생성해서 사용하지 못하고,
        // 추상클래스나 인터페이스는 내부 자바 메서드를 추가적으로 구현해서 사용해야함
        
        Queue queue = new LinkedList(); 
        // LinkedList()에 queue에 필요한 연산이 포함되어있음, 다형성을 이용하여 사용
        
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        System.out.println(queue);  // [1, 2, 3, 4, 5]
        
        System.out.println(queue.poll());  // 1
        System.out.println(queue);  // [2, 3, 4, 5]
        
        System.out.println(queue.poll());  // 2
        System.out.println(queue);  // [3, 4, 5]
        
        System.out.println(queue.peek());  // 3
        System.out.println(queue);  // [3, 4, 5]
        
        System.out.println(queue.contains(3));  // true
        System.out.println(queue.size());       // 3
        System.out.println(queue.isEmpty());    // false 
        
        queue.clear();
        System.out.println(queue);  // []
        System.out.println(queue.poll());  // null

 

 

---

큐는 가장 먼저 추가된 데이터가 가장 먼저 제거되는 FIFO 원칙을 따르고,

기본 기능으로서 큐의 맨 뒤에 새로운 데이터를 추가하는 enqueue,

큐의 앞쪽(Front) 데이터를 제거하고 반환하는 dequeue,

큐의 맨 앞쪽(Front) 데이터를 제거하지 않고 반환하는 peek,

큐가 비어있는지 확인하는 isEmpty를 잘 숙지해야 되겠다.

 

구현 방법으로는 배열을 사용하면 고정된 크기의 큐를 만들 수 있고, 연결 리스트를 사용하면 동적으로 크기를 조절할 수 있다.

Java에서 'Queue' 인터페이스를 통해 다양한 큐 구현체 사용 가능(예 : LinkedList)

 

응용 분야로는 운영체제(OS)에서 프로세스를 처리할 때

대기 중인 프로세스들을 큐에 저장하고 차례대로 처리 가능한 프로세스 스케줄링,

이벤트 기반 시스템에서 발생한 이벤트를 큐에 저장하고, 순서대로 처리하는 이벤트 처리,

데이터 패킷을 큐에 저장하고 차례대로 전송할 수 있는 네트워크 데이터 전송이 있다.