스택과 큐는 선형자료구조입니다.

** 선형자료구조 : 자료들간의 앞뒤 관계가 1:1의 선형관계로 존재하는 구조

STACK

• 나중에 들어간 원소가 먼저 나오는 자료구조입니다.
• LIFO구조
• 함수의 콜스택, 문자열 역순출력, 연산자 후위표기법등의 연산에 주로 이용됩니다.
• 탐색 : O(N)
• 삽입 / 삭제 : O(1)

QUEUE

• 먼저 들어간 원소가 먼저 나오는 구조입니다.
• FIFO구조
• 메세지 큐, 버퍼, BFS탐색 등에 주로 이용됩니다.
• 탐색 : O(N)
• 삽입 / 삭제 : O(1)

스택2개로 큐 구현하기

1. inbox에 데이터를 삽입한다(push) -> A,B
2. inbox에 있는 데이터를 추출(pop)하여 outbox에 삽입(push) 한다. -> B,A
3. outbox에 있는 데이터를 추출(pop)한다. -> A,B 순으로 출력된다.

코드

package Stack;

import java.util.Stack;

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();
        }
    }
}