[210725] Queue Interface

10457 단어 queueJavaJava

Queue Interface


DFS & BFS Algorithm

BFS를 공부하다 LinkedList 사용 중 값을 단순히 참조하는 peekpoll의 차이를 알아봄

우선 자료쿠조 Queue는 FIFO 형태로 자료를 보관하고 꺼내는 버퍼
자료를 보관 시 offer 메소드 사용
가정 먼저 보관한 자료를 꺼낼 때는 poll 메소드 사용
가장 먼저 보관한 자료를 단순 참조하는 peek 메소드와
비었는지 판별하는 empty 메소드

//큐 사용 예
import java.util.Queue;
import java.util.LinkedList;
public class Program {
	public static void main(String[] args){
		Queue<String> q = new LinkedList<String>();
		q.offer("강감찬"); //"강감찬"
		q.offer("홍길동"); //"강감찬","홍길동"
		System.out.println(q.peek());//"강감찬" 참조
		//여전히 "강감찬","홍길동"
		
		System.out.println(q.poll());//"강감찬" 꺼냄, 현재 "홍길동"
		q.offer("이순신"); //"홍길동", "이순신"
		q.offer("김구"); //"홍길동", "이순신", "김구"
		while(q.isEmpty()==false){
			System.out.println(q.poll());
			//"홍길동", "이순신", "김구" 순으로 꺼냄
		}		
	}

BFS 사용 예시코드

    // BFS 함수 정의
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x + " ");
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

좋은 웹페이지 즐겨찾기