Queue 큐 / LinkedList / BFS
1. Queue 개요
Queue이란?
: 대기열처럼 작동하는 자료구조. -자료가 일렬로 놓인 선형 자료구조
- 제일 먼저 추가된 자료가 먼저 나오는 선입선출 자료구조. (First In First Out)
- ** front & rear : 큐의 양쪽 지점을 위한 변수 (초기값 -1)
- Queue에 데이터 추가 : enQueue > rear의 크기 증가 후 arr[rear]에 할당
- Queue에서 데이터를 회수 : deQueue > front의 크기 증가 후 arr[front]에 할당
- Queue가 비었는지 확인 : isEmpty > front == rear
- Queue의 제일 앞에 있는 데이터를 확인 : peek()
- Queue가 가득 차있는지 확인 (고정된 배열을 사용하는 경우) : isFull()
- 구현해본 코드
package codingTest.d1207;
// 큐의 형태로 데이터를 관리하는 클래스
public class MyQueue {
// 데이터를 담기 위한 배열
private int[] arr = new int[16];
// 제일 앞의 데이터가 어딘지 front (어디서 데이터를 뺄지)
private int front = -1;
// 제일 뒤의 데이터가 어딘지 rear (어디에 데이터를 넣을지)
private int rear = -1;
// 데이터를 큐에 담기 위한 enQueue
public void enQueue(int x) {
// 넣어줄 공간을 설정
rear++;
// 해당 위치에 넣어준다.
arr[rear] = x;
}
// 데이터 회수하는 deQueue
public int deQueue(int x) {
// 데이터를 가져올 공간을 설정
front++;
// 해당 위치에서 가져옴
return arr[front];
}
// 큐가 비어있는지 확인하기 위한 isEmpty
public boolean isEmpty() {
if (front == rear) {
return true;
} return false;
}
// 큐가 채워져있는지 확인하기 위한 isfull()
// 잘못된 포화 상태 인식
public boolean isFull() {
// front가 이동한 상황은 고려가 되지 않는다.
return this.rear == arr.length -1;
}
}
>> 이렇게 배열을 사용하게 되면 ? deQueue를 통해 앞쪽의 공간이 확보되었으나, rear을 기준으로 본다면 가득 차있다고 인식할 수 있다. ...
(선형 Queue의 문제점)
앞쪽으로 이동할수도 없고 ..ㅠㅡㅠ
>> 그러면 데이터가 원형으로 저장된다고 생각한다면...?
실제로는 일자로 되어있지만 원형으로 상상.
> enQueue > rear에 (rear+1)%size 후 arr[rear]에 할당
> deQueue > front에 (front+1)%size 후 arr[front] 반환
* 실제 사이즈보다 배열의 크기가 하나 더 커야한다. 왜냐하면 포화 상태와 공백 상태를 비교하기 위해서는 front 위치를 비워두어야 하기 때문!!
배열의 크기가 실제사이즈와 같으면...? 공백 상태에도 rear == front, 포화 상태에도 rear == front이기 때문에 조건이 겹친다.
배열의 크기를 하나 더 키우면 빈 공간이 있으므로 다음번에 넣을 곳이 front라면? 가득 차있는 상태이다.
- 이걸 코드로 구현하면 이렇게 된다.
package codingTest.d1207;
public class MyCyQueue {
// 크기를 4로 먼저 만들어보자.
private int size = 4;
// 실제로 만들 배열의 크기는 size+1
private int offset = size+1;
// 데이터를 담기 위한 배열
private int[] arr = new int[offset];
private int front = 0;
private int rear = 0;
// 데이터를 넣기 위한 enqueue
public void enQueue(int x) {
// 큐가 가득 차있을 경우 예외 발생
if (this.isFull()) {
throw new RuntimeException("queue is full");
}
arr[rear] = x;
rear = (rear+1) % offset;
}
// 데이터를 빼기 위한 deQueue
public int deQueue() {
// 큐가 비어있을 경우 예외 발생
if(this.isEmpty()) {
throw new RuntimeException("queue is empty");
}
int value = arr[front]; // 현재 위치의 값을 회수
// 위치 재설정
front = (front+1) % offset;
return value;
}
// 큐가 비어있는지 확인하기 위한 isEmpty()
public boolean isEmpty() {
return rear == front;
}
// 큐가 차있는지 확인하기 위한 isFull()
public boolean isFull() {
// 다음번에 넣을 곳이 front라면 가득 차있는 상태이다.
return (rear+1) % offset == front;
}
public static void main(String[] args) {
MyCyQueue myQueue = new MyCyQueue();
myQueue.enQueue(0);
myQueue.enQueue(1);
myQueue.enQueue(2);
myQueue.enQueue(3);
// 4개 넣고 상태 확인
System.out.println(myQueue.isFull());
System.out.println(myQueue.isEmpty());
// 4개 제거
System.out.println(myQueue.deQueue());
System.out.println(myQueue.deQueue());
System.out.println(myQueue.deQueue());
System.out.println(myQueue.deQueue());
// 4개 제거 후 상태 확인
System.out.println(myQueue.isFull());
System.out.println(myQueue.isEmpty());
}
}
> 이렇게 하면 문제가 해결되어 오류없이 잘 된다.ㅎㅎ
- Queue는 인터페이스이므로 선언 시 구현체는 LinkedList를 보통 활용. (스택은 클래스이다)
- interface Queue<T> (자바 컬렉션 프레임워크에서 제공하는 인터페이스)
- - enQueue >> add(), offer()
- - deQueue >> remove(), poll()
- - peek >> element(), peek()
~> 오류 상황에 대한 대처가 좀 다르다. (예외 발생 vs. 지정된 값 반환하는지에 차이)
파랑 : 시도하고 실패할 경우 예외를 발생시킨다.
노랑 : 시도하고 실패할 경우 false(offer), null(poll&peek)를 반환한다.
2. LinkedList 연결 리스트
: 여러 자료를 저장하기 위한 자료구조의 일종.
- 하나의 자료 저장할 때 다음 자료의 위치를 같이 저장.
- 배열과 다르게 메모리상 물리적 순서가 보장되지 않음.
1) 데이터를 끝에 추가할 때 : 새로운 노드 생성하여 마지막 노드의 link에 해당 노드 할당.
2. 데이터를 중간에 추가할 때 : 새로운 노드 생성하여 삽입할 위치 전의 노드에 link에 이 노드를 할당하고, 새로운 노드의 link에 본래의 link에 있던 노드를 할당.
3. 데이터를 중간에서 제거할 때 : 제거할 노드 앞쪽의 link에 뒤쪽의 노드를 할당.
cf) ArrrayList
ArrayList | LinkedList | |
데이터 추가할 때 | 내부 배열이 너무 작으면 데이터 전체를 복사 | 노드만 추가하면 되기 때문에 동적으로 크기 조절이 수월함 |
데이터 조회할 때 | 위치를 알면 바로 조회가 가능 | 연결된 노드를 거쳐야 정확한 데이터를 조회 가능 |
> 결론 : 데이터의 추가 제거가 빈번할 때에는 LinkedList / 데이터의 위치에 기반한 조회가 빈번할 때 ArrayList
- 테스트 코드
- 데이터를 앞쪽에 10000개 넣고,
- 뒤쪽에 10000개 넣고,
- 각 데이터를 순서 기준으로 조회
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ListComparison {
public static void main(String[] args) {
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
System.out.println("ArrayList");
ListComparison.rearInsert(arrayList);
ListComparison.frontInsert(arrayList);
ListComparison.getElements(arrayList);
System.out.println("LinkedList");
ListComparison.rearInsert(linkedList);
ListComparison.frontInsert(linkedList);
ListComparison.getElements(linkedList);
}
// 데이터를 뒤쪽에 10000개 넣는다.
public static void rearInsert(List<String> list){
long start = System.nanoTime();
for (int i = 0; i < 10000; i++) {
list.add("hello");
}
long end = System.nanoTime();
System.out.println(String.format("뒤쪽에 추가 소요시간: %15d ns", end - start));
}
// 데이터를 앞쪽에 10000개 넣는다.
public static void frontInsert(List<String> list) {
long start = System.nanoTime();
for (int i = 0; i < 50000; i++) {
list.add(0, "hello");
}
long end = System.nanoTime();
System.out.println(String.format("앞쪽에 추가 소요시간: %15d ns", end - start));
}
// 각 데이터를 순서 기준으로 조회 (.get)
public static void getElements(List<String> list) {
long start = System.nanoTime();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long end = System.nanoTime();
System.out.println(String.format("데이터 조회 소요시간: %15d ns", end - start));
}
}
![](https://blog.kakaocdn.net/dn/TxcDe/btsBzM5pTXH/XHiFlCyr82fxJWei20NDLk/img.png)
순차적 추가는 시간차이가 거의 없지만, 앞쪽에 추가할 때에는 배열이 훨씬 오래걸리고, 전체 데이터 조회 소요시간은 LinkedList가 훨씬 오래 걸린다.
>> 그럼 큐는 왜 LinkedList를 쓸까?
Queue는 자료의 추가와 제거가 잦기 때문에~~
>> 이건 직접 해보고 추가하겠습니다~
3. Breadth First Search(BFS) 너비 우선 탐색
: 현재 상태에서 직접적인 연관관계에 있는 모든 정보를 먼저 확인하는 것
- 스택 대신 큐를 사용한다.
1) 시작 지점을 결정하고 큐에 넣는다.
2) 큐에서 deQueue하고, deQueue한 점은 방문했다고 표시. + 여기서 deQueue한 점의 인접점들을 큐에 enQueue.
4) 다음 다시 deQueue
4) 큐가 빌 때까지 반복.
즉,
> 데이터의 연결관계를 나타내는 것이 필요하고, (int[][] 2차원 배열 혹은 인접행렬 리스트)
얘네를 enQueue/deQueue 할 Queue가 필요하고,
방문 여부를 확인할 boolean[] 배열이 필요하고,
방문 순서를 저장할 곳이 필요하다.
- BFS 코드
package codingTest.d1207;
import java.util.*;
// 너비 우선 탐색
public class BreadthFirstSearch {
public static void main(String[] args) {
String[] edges = { // 연결 정보
"1 2",
"1 3",
"2 4",
"2 5",
"3 7",
"4 6",
"5 6",
"6 7"
};
// 총 점의 개수
int nodeCount = 7;
// 각 점이 연결되었는지를 판단하기 위한 배열
int[][] map = new int[nodeCount+1][nodeCount+1];
// 주어진 연결 정보를 바탕으로 map을 채워 넣는다. 연결되어 있다면 1
// 1. 주어진 선의 갯수만큼 반복
for (int i=0; i< edges.length; i++) {
// 하나의 정보를 나누어서 출발 종점을 구분해 각각 변수에 할당
String[] edgeInfo = edges[i].split(" ");
int leftNode = Integer.parseInt(edgeInfo[0]);
int rightNode = Integer.parseInt(edgeInfo[1]);
// 각각의 정점의 map[left][right] = 1로 넣어줌
map[leftNode][rightNode] = 1;
map[rightNode][leftNode] = 1;
}
// 1번에서 출발해서, 모든 점들을 방문할 때 어떤 순서로 방문하는지
Queue<Integer> toVisit = new LinkedList<>();
List<Integer> visitOrder = new ArrayList<>();
boolean[] visited = new boolean[nodeCount+1];
toVisit.offer(1);
while(!toVisit.isEmpty()) {
int next = toVisit.poll();
if (visited[next]) continue;
visited[next] = true;
visitOrder.add(next);
for (int i=1; i<nodeCount; i++) {
if(visited[i]) continue;
if(map[next][i]==1) {
toVisit.offer(i);
}
}
}
System.out.println(visitOrder);
}
}
'Coding test > Algorithm' 카테고리의 다른 글
DP(Dynamic Programming) (0) | 2023.12.28 |
---|---|
Brute Force / 순열 / 조합 / 멱집합 (1) | 2023.12.17 |
정렬 Sorting (버블/선택/카운팅/이진 탐색) (2) | 2023.12.05 |
알고리즘 (3) | 2023.12.04 |
정렬 알고리즘 (선택, 삽입, 버블 정렬) (0) | 2023.08.28 |