02. 스택과 큐

스택(Stack)이란?

스택(stack)은 쌓아올리는 걸 뜻한다.

젠가를 쌓을 때를 생각해보자. 보통 아래에서부터 나무 블록을 차곡차곡 쌓아서 탑을 완성하지 않는가?
이렇듯 스택은 데이터를 정해진 방향으로 쌓는 것이다.

스택의 TOP은 가장 최근에 들어온 자료를 가리킨다. 그렇기 때문에 삽입되는 새로운 데이터는 top 위에 쌓이고, 삭제할 때도 top에서부터 삭제된다.

이건 젠가와는 다르다. 젠가는 마음대로 원하는 곳에 있는 나무 블록을 숭숭 뽑지만, 스택은 무조건 최근에 쌓인 데이터부터 제거한다.

이를 후입선출(LIFO, Last-In-First-Out)이라고 부른다.

스택 활용

• 웹 브라우저 뒤로 가기: 현재 페이지 이전에 접속했던 웹 정보를 보여준다.
• 문자열 역순 출력하기
• 실행 취소하기
• 후위 표기법 계산

스택 활용 코드

Stack<String> st = new Stack<String>();
    
    st.push("0");
    st.push("1");
    st.push("2");
    
    while(!st.isEmpty()){
        System.out.println(st.pop());
    }

큐(Queue)란?

큐는 줄을 서서 기다리는 것을 뜻한다.

우리가 보통 줄을 설 때를 생각해 보자. 먼저 줄을 선 사람이 먼저 이용하고, 점점 순번이 당겨지는 형식을 취하고 있지 않은가?

이걸 선입선출(FIFO, First-In-First-Out)이라고 부른다.

한쪽에서 작업이 이뤄지는 스택과 달리 큐는 양쪽에서 이뤄진다.
삭제 연산이 수행되는 곳을 Front, 삽입 연산이 수행되는 곳을 Rear라고 부르며, 각각의 연산 작업만 수행한다는 특징이 있다.

이때, 삽입 연산은 인큐(enQueue), 삭제연산은 디큐(dnQueue)라고 한다.

큐 활용

• 우선순위가 같은 작업 예약
• 은행 업무, 콜센트 고객 대기
• 프로세스 관리
• 너비 우선 탐색
• 캐시 구현

큐 활용 코드

    Queue<String> queue = new LinkedList<String>();
    
    queue.offer("0");
    queue.offer("1");
    queue.offer("2");
    
    while(!queue.isEmpty()){
        System.out.println(queue.poll());