Queue

특징

"원소들을 순서대로 처리해야 할 때 좋다."
FIFO: First In First Out
back에 집어넣는 것을 enqueue라고 하고, front에서 꺼내오는 것을 dequeue라고 한다.

구현

직접 구현

동적 배열과, head를 가리키는 index로 구현할 수 있다.
하지만 그냥 배열이라면.. head index와 tail index를 따로 둬서 circular하게 동작하는 queue를 만들 수 있다.

Built-in Library 사용

• offer()
• poll()
• peek()

BFS

구현

Queue를 이용해서 구현된다.
시작 원소 enque → 1단계 떨어진 원소들 enqueue → 시작 원소 deque → 남은 첫 원소에서 1단계 떨어진 원소들 enqueue → 첫 원소 deque → ...
따라서 시작 원소로부터 몇 단계 떨어졌는지 알 수 있고 거리를 구하기가 쉽다.

사용 시나리오

(1) 순회 (traversal)
(2) 최단 경로 찾기

Template

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> visited;  // store all the nodes that we've visited
    int step = 0;       // number of steps needed from root to current node
    // initialize
    add root to queue;
    add root to visited;
    // BFS
    while (queue is not empty) {
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in visited) {
                    add next to queue;
                    add next to visited;
                }
            }
            remove the first node from queue;
        }
        step = step + 1;
    }
    return -1;          // there is no path from root to target
}

visited hashset 을 두는 이유는 graph 가 cycle 이면 무한 루프에 빠지기 때문.. 따라서 visited hashset을 두지 않아도 되는 경우는 다음과 같다.
1. tree 순회와 같이 cycle이 없음이 확실할 때
2. 같은 노드를 여러번 순회해야 할 때

Stack

특징

LIFO: Last In First Out
back 에 집어넣는 것을 push라고 하고, back 에서 꺼내오는 것을 pop이라고 한다.

구현

직접 구현

동적 배열만 있으면 된다. pop 할 땐 size-1 index에서 꺼내오기만 하면 되기 때문이다.

Built-in Library

• push()
• pop()
• peek()

DFS

구현

stack 을 이용해서 구현된다.
가장 깊은 노드에 도달한 후에만 역추적하여 다른 경로를 시작한다.
시작 원소 push → 타고타고 들어가서 더 이상 갈 수 없을 때까지 push → 빠져나오면서 방문하지 않은 길 나올 때까지 pop → 다시 거기부터 타고타고 들어가서 더 이상 갈 수 없을 때까지..

Template

재귀 버전
여기서 call stack의 크기는 DFS의 최대 깊이와 같다.

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visited;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

stack 버전 (stackoverflow 방지)

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> stack;
    add root to visited;
    add root to stack;
    while (stack is not empty) {
        Node cur = the top element in stack;
        remove the cur from the stack;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to visited;
                add next to stack;
            }
        }
    }
    return false;
}