04-2 큐(Queue)
이번에도 스택과 마찬가지로 데이터를 일시적으로 보관하는 자료구조인 스택에 대해 아라보자
해당 정리글은 LinkedList를 선언해서 활용하는 방식(add,pol,remove..등)이 아닌 큐에 대해 기본적인 내용을 다루고 있습니다
큐(Queue)란?
먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In First Out) 데이터의 입력과 출력 순서는 선입선출.
특징
- 인큐 (en-queue) : 큐에 데이터를 넣음
- 디큐 (de-queue) : 큐에서 데이터를 꺼낸다
- 큐의 한쪽 끝 프론트(front)는 삭제 연산만 수행
- 다른 한쪽 끝 리어(rear)는 삽입 연산만 수행
사용 사례
- 일상생활에서 많이볼 수 있다.
- 티켓 카운터,프린터 사용시 먼저한 사람 문서가 먼저 된다..등등
🎂 큐 만들기
public class IntQue {
private int[] que; // 큐의 본체
private int capacity; // 큐의 용량
private int num; // 현재 데이터 수
private int front;
private int rear;
//예외 : 빈 큐
public class EmptyInStackException extends RuntimeException {
public EmptyInStackException() {
}
}
//예외 : 가득 찬 큐
public class OverflowInStackException extends RuntimeException {
public OverflowInStackException() {
}
}
//생성자
public IntQue(int maxlen) {
num = 0;
capacity = maxlen;
try {
que = new int[capacity];
} catch (OutOfMemoryError error) {
capacity = 0;
}
}
// 인큐 메서드
public int enque(int x) throws OverflowInStackException {
if (num >= capacity) {
throw new OverflowInStackException();
}
que[rear++] = x;
num++;
if (rear == capacity) {
rear = 0;
}
return x;
}
// 디큐 메서드
public int deque() throws EmptyInStackException {
if (num <= 0) {
throw new EmptyInStackException();
}
int x = que[front++];
num--;
if (front == capacity) {
front = 0;
}
return x;
}
//큐에서 데이터를 peek(들여다본다)
public int peek() throws EmptyInStackException {
if (num <= 0) {
throw new EmptyInStackException();
}
return que[front];
}
//큐의 데이터를 초기화
public void clear() {
num = front = rear = 0;
}
//큐에서 x를 검색하여 인덱스(찾지 못하면-1)반환
public int inndexOf(int x) {
for (int i = 0; i < num; i++) {
int idx = (i + front) % capacity;
if (que[idx] == x) {
return idx;
}
}
return -1;
}
//큐의 용량을 반환
public int getCapacity() {
return capacity;
}
//큐에 쌓여있는 데이터 개수를 반환
public int size() {
return num;
}
//큐가 비어있나요 ?
public boolean isEmpty() {
return num <= 0;
}
//큐가 가득 찼나요?
public boolean isFull() {
return num >= capacity;
}
//큐 안의 모든 데이터를 프론트->리어순 출력
public void dump() {
if (num <= 0) {
System.out.println("큐가 비어있습니다");
} else {
for (int i = 0; i < num; i++) {
System.out.println((que[i + front % capacity]) + "");
}
System.out.println();
}
}
}큐로 사용할 배열 que
- 인큐하는 데이터를 저장하기 위한 큐 본체용 배열
필드 que는 실제로는 배열본체가 아니라 본체를 참조하는 배열 변수. 배열 본체는 생성자로 생성
큐의 최대 용량 capacity
- 큐의 최대 용량을 저장하는 필드, 이 값은 배열 quedㅔ 저장할 수 있는 최대 요솟수와 같다.
프론트 front
- 인큐하는 데이터 가운데 맨 앞 요소 인덱스를 저장하는 필드
리어 rear
- 인큐한 데이터 가운데 맨 뒤에 넣은 요소 하나 뒤 인덱스를 저장하는필드
다음 인큐할 때 데이터가 저장될 요소의 인덱스를 미리 준비해 두는 것이라고 생각하면 된다
현재 데이터 개수 num
- 큐에 쌓여 있는 데이터 개수를 나타내는 int형 필드
생성자 IntQue
- 생성자는 큐 본체용 배열을 생성하는 등의 준비 작업 수행
- 생성시 큐는 비어 있기 때문에 num,front,rear값은 모두0
- 매개변수 maxlen으로 전달받은 '큐의 용량'을 필드 capacity에 복사 -> 요솟수가 capacity인 배열 quedㅢ 본체를 생성
인큐 메서드 enque
- 큐에 데이터를 인큐하고 인큐한 값을 그대로 반환하는 메서드
- 예외) 큐가 가득차 있으면 예외 OverflowIntQueueException 실행
디큐 메서드 deque
- 큐에서 데이터를 디큐(빼고) 그 값을 반환하는 메서드
- 예외) 큐가 비어있으면 예외 EmptyIntQueueException 실행
피크 메서드 (peek)
- 맨앞의 데이터(다음 디큐할 데이터)를 들여다 보는 메서드
데이터 초기화 메서드 clear
- 모든 데이터 초기화
- num,front,rear값들을 0으로 바꿈
검색 메서드 indexOf
- 큐 본체용 배열에서 x와 값이 같은 데이터가 저장되어 있는 위치를 조사하는 메서드
최대 용량을 확인하는 메서드 getCapacity
- 큐의 최대 용량을 반환하는 메서드 (필드 capaticy값 그대로 반환)
데이터의 개수를 확인하는 메서드 size
- 현재 큐에 들어있는 데이터 개수를 반환 (필드 num값을 그대로 반환)
큐가 비어 있는지 판단하는 메서드 isEmpty
- 비어있으면 true 그렇지 않으면 false
큐가 가득차 있는지 판단하는 메서드 isFull
- 가득 찼으면 true 그렇지 않으면 false
모든 데이터를 출력하는 메서드 dump
- 큐에 들어 있는 모든(num)개 데이터를 프론트에서 리어순으로 출력하는 메서드
🗓 2022/11/23(수) 느낀점
스택을 이해한 상태에서 공부를 하니 조금 더 와닿았지만, 그래도 확실히 스택보다는 내용이 조금 더 많다 복잡하기도 복잡하고.. 알고리즘을 풀면서 LinkedList를 사용하며 이해해 봐야겠다!
걍 하자 저스트 뚜잇