[DataStructure] Stack & Queue

우선, Stack과 Queue는 선형 자료구조이다.

Stack

• 나중에 들어온 원소가 먼저 나오는 구조
• LIFO(Last In First Out)형태의 자료 구조이다.
• 안드로이드에선 액티비티를 관리하는데 스택이 사용된다.
• 시간 복잡도 : O(n)
• 공간 복잡도 : O(n)
• 함수의 콜 스택, 문자열 역순 출력, 연산자 후위 표기법 등에 사용된다.

Queue

• 먼저 들어간 원소가 먼저 나오는 구조이다.
• FIFO(First In First Out) 형태의 자료 구조이다.
• 큐는 활용 분야가 되게 많다. 안드로이드의 경우, Looper의 메세지 큐가 예시 중 하나이다.
• 시간 복잡도 : O(n)
• 공간 복잡도 : O(n)
• 버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, BFS 탐색 등에 사용된다.

2개의 스택으로 큐를 구현하기

A,B 순서의 데이터를 스택에 넣고 뺴면 B,A가 된다.
이를 순서대로 다시 스택에 넣고 빼면 A,B 그대로 된다.
내부적인 동작은 다르지만 결과적으로 들어간 순서대로 나오는 큐와 같다.

관련해서 작성하신 다른 분의 코드가 있어 참고했다.

package Stack;

import java.util.Stack;

/**
 * created by victory_woo on 2020/05/06
 * Stack 2개를 이용해서 Queue 구현하기.
 */
public class StackWithQueue {
    public static void main(String[] args) {
        StackQueue<String> queue = new StackQueue<>();
        queue.enQueue("A");
        queue.enQueue("B");
        queue.enQueue("C");

        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
    }

    static class StackQueue<T> {
        private Stack<T> inBox;
        private Stack<T> outBox;

        StackQueue() {
            inBox = new Stack<>();
            outBox = new Stack<>();
        }

        void enQueue(T item) {
            inBox.push(item);
        }

        Object deQueue() {
            if (outBox.isEmpty()) {
                while (!inBox.isEmpty()) {
                    outBox.push(inBox.pop());
                }
            }

            return outBox.pop();
        }
    }
}