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));
    }
}

순차적 추가는 시간차이가 거의 없지만, 앞쪽에 추가할 때에는 배열이 훨씬 오래걸리고, 전체 데이터 조회 소요시간은 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);


    }
}