<Queue>

먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터 저장하는 자료구조

• enqueue : 데이터 추가
• dequeue : 데이터 추출

1) 구현

• Queue 인터페이스 - LinkedList 클래스
• Queue 인터페이스 - ArrayDeque 클래스

// LinkedList
Queue<Integer> q = new LinkedList<>();
// ArrayDeque
Queue<Integer> q = new ArrayDeque<>();

public class ArryDequeExample {
    public static void main(String[] args) {
        Queue<Integer> q = new ArrayDeque<>();

        // enqueue
        q.add(1); // [1]
        q.add(2); // [1, 2]
        q.add(3); // [1, 2, 3]

        // front
        System.out.println(q.peek()); // 1
        // front + dequeue
        q.remove(); // [2, 3]

        // empty
        while (!q.isEmpty()) {
            System.out.println(q.remove());
        }

        System.out.println(q);
    }
}

2) 문제적용

• BFS 구현
  • 현재 정점에 인접한 정점들을 저장하고, 순차적으로 front에서 dequeue 해서 각 정점을 방문
• Queue - 투 포인터(two pointer) 사용
  • 한 큐에서 dequeue된 값은 다른 큐에 enqueue된다는 특성을 이용해서 2개의 queue들을 1개의 queue로 이어서 투 포인터 알고리즘으로 2개의 큐로 나누는 지점을 찾아가는 방식
• FIFO 활용
  • 문제에서 요구하는 풀이방식이 먼저 온 데이터를 먼저 출력해야되는 FIFO형태의 문제인 경우

---

<Stack>

가장 최근에 추가한 데이터가 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터 저장하는 자료구조

• push : top에 데이터 추가
• pop : top에서 데이터 추출

1) 구현

stack 클래스로 구현 가능하지만 Deque(인터페이스)+ArrayDeque(클래스)가 성능이 좋음

• Deque 인터페이스 - ArrayDeque 클래스

Deque<Integer> st = new ArrayDeque<>();

public class StackExample {
    public static void main(String[] args) {
        Deque<Integer> st = new ArrayDeque<>();

        //push (추가)
        st.push(1); //st: [1]
        st.push(2); //st: [2, 1]
        st.push(3); //st: [3, 2, 1]

        //peek (top 요소)
        System.out.println(st.peek()); //3

        //pop (추출)
        st.pop(); //st: [2, 1]
        st.pop(); //st: [1]
        st.pop(); //st: []

        st.push(4); //st: [4]
        st.push(5); //st: [5]

        //Empty
        while (!st.isEmpty()) {
            st.pop();
        }

        System.out.println(st); //st: []
    }
}

2) 문제적용

• Stack - 짝 맞추기
  • 유효 괄호쌍 검사, 동일 블록 제거하기 등
    올바른 괄호
    Valid Parentheses
• Stack - 되돌리기
  • stack에 임시로 데이터를 저장하다가 top에서 가장 최근에 push 했던 값을 확인
• DFS(재귀)
  • 핵심 : 재귀적 함수 호출
    • 현재 수행 중인 함수에서 자기 자신을 다시 호출해서 또다른 메모리 공간 차지
    • 재귀적 함수 호출은 push 를, 함수 종료는 pop 을 하는 것과 같은 형태