[ 자료구조 ] Queue

큐의 개념

• 선입 선출, FIFO 구조(First In First Out)

• 삽입하는 연산 : Enqueue(Add)
• 꺼내는 연산 : Dequeue(Poll)

 

---

 

큐의 특성을 활용하는 분야

먼저 들어온 것을 먼저 처리하는 큐의 동작 방식은 주로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 활용됨

• 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 즉 키보드 입력이나 마우스 움직임을 처리할 때

 

---

 

큐의 ADT

ADT (Abstract Data Type, 추상 데이터 타입) : 데이터의 구현 방법을 명시하지 않고, 해당 데이터가 가져야 할 연산들을 정의 한 것 , 데이터 타입이 가져야 할 기능(메소드)들의 명세서

 

구분	정의	설명
연산	boolean isFull()	큐에 들어있는 데이터 개수가 maxsize인지 확인
	boolean isEmpty()	큐에 들어있는 데이터가 없는 지 확인
	void add(ItemType item)	큐에 데이터를 add
	ItemType poll()	큐에서 최근에 add 한 데이터를 꺼내고 반환
상태	int front	큐에서 가장 마지막에 poll한 위치를 기록
	int rear	큐에서 최근에 add한 데이터의 위치를 기록
	ItemType data[maxsize]	큐의 데이터를 관리하는 배열, maxsize개의 데이터 관리

 

1 단계 : isFull , add

1️⃣ isFull() 연산으로 현재 큐가 가득 찼는지 확인하고 큐가 가득 차지 않았으므로

2️⃣ rear을 +1 한 후 rear가 가리키는 위치에

3️⃣ 3을 add 함 (반대로 isFull 인 ture이면 데이터를 add하지 않음)

 

2 단계 : poll

1️⃣ isEmpty() 연산으로 큐가 비었는지 확인, front와 rear의 값이 같은지 확인해서 큐에 원소가 없는데 poll하는 동작을 방지함

2️⃣ 만약 비어있지 않다면(isEmpty가 false) front를 +1 하면 front와 rear가 0으로 같아지게 되고

3️⃣ isEmpty() 연산 시 큐가 빈 것(isEmpty가 true)으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리 가능

⭐ 실제 데이터가 있어도 `front==rear` 이므로 빈 큐로 생각하게 됨

 

3 단계 : 계속해서 add

1️⃣ 5를 add하면 isFull() 연산을 수행해 큐가 가득 찼는지 검사하고, 가득차지 않았다면 add

2️⃣ 계속해서 같은 방식으로 6, 8을 add하면 front는 0, rear은 3이 됨

 

4 단계 : 가득찬 상태에서 add

1️⃣ rear가 3이므로 maxsize-1과 같게 되므로

2️⃣ isFull() 연산은 true으므로 add하지 못하게 됨

⚠️ 이때, 실제 data에 저장된 데이터는 2, 5, 6, 8 로 4개지만 큐는 5, 6, 8 로 3개, 즉 큐는 front 의 다음 부터 rear까지를 큐가 관리하는 데이터로 생각해야 함
➡️ 메모리 공간 낭비, 큐를 한 방향으로 관리하고 있기 때문(큐를 원형으로 개선가능)

 

---

 

큐 구현

1. Queue의 인터페이스 활용하기

자바 컬렉션 프레임워크에서 Queue의 구현체로 사용하는 클래스는 ArrayDeque, LinkedList가 있음

• add 연산 : add()
• poll 연산 : poll()

❗add()메서드 대신 offer()메서드도 사용가능하지만 내부적으로 메서드 호출횟수가 offer가 1회 더 많기 때문에 add메서드를 사용하는 것이 근소한 차이로 빠름

 

 

import java.util.Queue;
import java.util.ArrayDeque;

// 큐를 구현한 ArrayDeque 객체 생성
Queue<Integer> queue = new ArrayDeque<>();

// 큐에 데이터 추가
queue.add(1);
queue.add(2);
queue.add(3);

// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.poll();
System.out.println(first); // 1

// 큐에 데이터 추가
queue.add(4);
queue.add(5);

// 큐의 맨 앞 데이터를 제거하면서 반환
first- queue.poll();
System.out.println(first); // 2

 

2. 덱(ArrayDeque) 클래스 활용하기

Deque(Double Ended Queue) 은 양 끝에서 삽입 또는 삭제할 수 있는 큐를 구현한 것

• add 연산 : add() / addLast()
• poll 연산 : poll() / pollFirst()

 

import java.util.ArrayDeque;

// 큐를 구현한 ArrayDeque 객체 생성
ArrayDeque<Integer> queue = new ArrayDeque<>();

// 큐에 데이터 추가
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);

// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.pollFirst();
System.out.println(first); // 1

// 큐에 데이터 추가
queue.addLast(4);
queue.addLast(5);

// 큐의 맨 앞 데이터를 제거하면서 반환
first- queue.pollFirst();
System.out.println(first); // 2