Queue
1. 정의
선입 선출(FIFO: First In First Out)의 성격을 지닌 자료구조
2. 선언
import java.util.Queue;
import java.util.LinkedList;
// 자료형에 넣은 자료형만 삽입, 삭제 가능
Queue<자료형> 변수명 = new LinkedList<>();
// 어떤 자료형이든 삽입/삭제 가능 (이전에 int형을 넣었어도 String형 삽입 가능
Queue 변수명 = new LinkedList();3. 메서드
3.1 삽입
q.add(삽입할 value);
반환 값(boolean) : 성공 시 true, 실패 시 Exceptino 발생
q.offer(삽입할 value);
반환 값(boolean): 성공 시 true, 실패 시 false 반환
3.2 삭제
q.remove();
반환 값(삭제된 value의 자료형) : 삭제된 value
공백 큐이면 Exception(”NoSuchElementException”) 발생
q.remove(삭제할 value);
반환 값(boolean) : 큐에 해당 value가 존재하면 해당 값 삭제 후 true, 존재하지 않으면 false 반환
q.poll();
반환 값(삭제된 value의 자료형) : 삭제된 value
공백 큐이면 null 반환
3.3 큐의 front에 위치한 value 반환
q.element();
반환 값(큐 head에 위치한 value의 자료형) : 큐 head에 위치한 value
공백 큐이면 Exception(”NoSuchElementException”) 발생
q.peek();
반환 값(큐 head에 위치한 value의 자료형) : 큐 head에 위치한 value
공백 큐이면 null 반환
3.4 큐 초기화(=공백 큐 만들기)
q.clear();
반환 값(void): X
3.5 큐 크기
q.size();
반환 값(int): 큐 사이즈 반환
3.6 큐에 해당 원소가 존재하는지?
q.contains(찾을 value);
반환 값(boolean): 해당 값이 존재할 때 true, 해당 값이 없을 때 false 반환
3.7 공백 큐인가?
q.isEmpty();
반환 값(boolean): 공백 큐이면 true, 공백 큐가 아니면 false 반환
4. 기능 구현
선형 큐
=1차원 배열을 이용한 큐
- 큐의 크기 = 배열의 크기
- front : 마지막으로 삭제된 인덱스
- rear: 저장된 마지막 원소의 인덱스
상태 표현
- 초기 상태 : front = rear = -1
- 공백 상태: front = rear
- 포화 상태: rear = n-1 (n: 배열의 크기, n-1: 배열의 마지막 인덱스)
초기 공백 큐 생성
크기 n인 1차원 배열 생성
front 와 rear 를 -1로 초기화
삽입 : enQueue(item)
마지막 원소 뒤에 새로운 원소를 삽입
rear 값을 증가시켜 새로운 원소를 삽입할 자리를 마련
삭제 : deQueue()
가장 앞에 있는 원소를 삭제
front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소 이동
새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능
공백 상태 및 포화 상태 검사 : isEmpty(), isFull()
공백 상태 : front = rear
포화 상태 : rear = n-1 (n: 배열의 크기, n-1: 배열의 마지막 인덱스이므로 꼬리가 배열 마지막 인덱스랑 같으면 포화 상태)
검색: Qpeek()
가장 앞에 있는 원소를 검색해 반환하는 연산
현재 front의 한 자리 뒤(front+1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환
public class APS기본_Queue_구현 {
// createQueue 연산 구현
static int[] queue = new int[10];
static int front = -1, rear = -1;
public static void main(String[] args) {
for(int i=0; i<11; i++) {
enQueue(100);
}
int peekData = Qpeek();
System.out.println(peekData);
}
// 1. 삽입
// 삽입할 때 실패여부 확인을 위해 boolean 타입으로 반환 가능
public static void enQueue(int data) {
// 삽입 위치: rear
// queue[rear] = data;
// rear +=1;
if(isFull()) {
System.out.println("큐가 꽉차있어요");
return; // 아래 삽입 연산이 수행되지 않도록
}
queue[++rear] = data;
}
// 2. 삭제
public static int deQueue() {
// 삭제 위치: front (가장 최근 삭제 "된" 원소의 인덱스)
// int item = queue[front+1];
// front+=1;
// return item;
if(isEmpty()) {
System.out.println("큐가 비어있어요");
// 큐에 들어갈 수 없는 범위의 데이터를 넣어서 이상한 데이터가 나온거구나...를 확인할 수 있도록!
return -1; // 리턴값이 있어야해서 ㅠㅠ
}
return queue[++front];
}
// 3. 포화 상태 확인
public static boolean isFull() {
// 데이터가 추가로 들어갈 수 있는지 확인 -> rear
return rear == queue.length - 1;
}
// 4. 공백 상태 확인
public static boolean isEmpty() {
// 빠져나올 데이터가 있는지 확인 -> front
return front == rear;
}
// 5. 삭제하기 전에 삭제될 데이터를 확인하는 연산
public static int Qpeek() {
// 확인만 하는거니까 front 포인터를 변경시킬 필요X
return queue[front+1];
}
}5. 문제점
잘못된 포화 상태 인식
배열 앞 부분에 활용할 수 있는 공간이 있음에도 불구하고, rear = n-1 인 상태로 인식해 더 이상의 삽입을 수행하지 않게 됨
해결 방법1
매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞 부분으로 모두 이동시킴
하지만, 이렇게 되면 원소 이동에 많은 시간이 소요 되어 큐의 효율성이 급격히 떨어짐
해결 방법2
1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용
