하루에 하나씩 자료 구조를 정리하고 있다.
직접 써보면서 정리하는 것을 좋아하지만 손글씨가 매우 좋지 않아 오히려 가독성이 떨어지는 슬픈 상황ㅠㅠ
학창시절 필기했던 노트를 나중에 다시 봤을 때 알아보기 힘들었던 경험이 있기에 블로그로 적어본다.
(애초에 인터넷에 있는 이미지들이 내 그림보다 고퀄리티다.)
Queue
선입선출 (First In First Out; FiFO)의 자료구조. 먼저 들어온 데이터가 먼저 나간다.
자료가 나가는 부분을 Front, 자료가 들어오는 부분을 Rear(Back이라고도 한다)
입력동작을 Enqueue, 출력동작을 Dequeue라고 한다.
자바에서의 Queue 사용
// 선형 자료구조 - 큐
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue queue = new LinkedList();//Queue는 인터페이스라 바로 못쓰고 linkedlist로 쓴다.
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. stack은 없는 상태에서 pop 시키면 예외 발생했으나 queue는 null
}
}큐는 스택과 다르게 인터페이스다. LinkedList로 구현한다.
add() :입력동작
poll() : 출력동작
peek() : 조회
contains() : 해당 데이터가 존재하는지 여부
size() : 크기 조회,
isEmpty() : 큐가 비어있는지 여부
Clear() : Clear~
큐큐가 빈 상태에서 poll하면 null로 출력된다.
Queue의 종류
위키에는 선형 큐와 환형 큐(원형 큐)가 나와있지만 많은 종류가 있는 것 같다.
선형 큐는 막대 모양의 큐로 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 것이 단점이다.(A와 B가 빠진 공간 사용이 문제)
환형 큐는 배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우(큐가 꽉차서 더이상 자료를 넣을 수 없는 현상)가 발생하는 선형 큐의 문제점을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.(A가 빠진 공간에 자료를 보낸다.)
자바에서의 환형큐(원형큐) 구현
// 배열 관점에서 dequeue 한 공간을 채워주지 않아서 꽉 찼을 때 빈 공간으로 데이터를 넣어줘야 함
// 그래서 원형 큐 형태로 구현
class MyQueue2 {
int[] arr;
int front = 0;
int rear = 0;
MyQueue2(int size) {
arr = new int[size+1];//수를 더하면서 rear는 뒤로 빠지고 front자리는 공백으로.
//dequeue시 front가 뒤로 움직이는 방식 원형큐는 한자리 비워놓는다 그래서 size+1
}
public boolean isEmpty() {
return this.rear == this.front;//같으면 비어있으니 true , 다르면 false
}
public boolean isFull() {
return (this.rear+1)%this.arr.length == this.front;
}
public void enqueue(int data) {
if(this.isFull()){
System.out.println("Queue is full");
return;
}
this.rear = (this.rear+1)%this.arr.length;
this.arr[this.rear]=data;
}
public Integer dequeue() {
if(this.isEmpty()){
System.out.println("Queue is empty");
return null;
}
front = (front+1)%this.arr.length;
return this.arr[front];
}
public void printQueue() {
int start = (this.front+1)%this.arr.length;
int end = (this.rear+1)%this.arr.length;
for (int i = start; i !=end ; i=(i+1)%this.arr.length) {
System.out.print(this.arr[i]+" ");
}
System.out.println();
}
}
(학습 중 추가로 기록할 부분이 생기면 내용 추가하겠습니다)