[HackerLank] Queue using Two Stacks - 문제풀이

Description

두개의 스택을 이용해서 큐를 구현하는 문제입니다.

Solution 1. Stack

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    MyQueue q = new MyQueue();

    Scanner in = new Scanner(System.in);
    while(in.hasNext()){
        int command = in.nextInt();
        if(command == 1) { // enqueue
            q.enqueue(in.nextInt());
        }else if(command == 2){ // dequeue
            q.dequeue();
        }else if(command ==3){ // peek
            System.out.println(q.peek());
        }
    }
}

public static class MyQueue<Integer> {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    public void enqueue(Integer num) {
        stack1.push(num);
    }

    public Integer dequeue() {
        if (size() == 0) {
            return null;
        }
        if (stack2.isEmpty()) {
            shiftStacks();
        }
        return stack2.pop();
    }

    public Integer peek() {
        if (size() == 0) {
            return null;
        }
        if (stack2.isEmpty()) {
            shiftStacks();
        }
        return stack2.peek();
    }

    /* Only shifts stacks if necessary */
    private void shiftStacks() {
        if (stack2.isEmpty()) { // shifting items while stack2 contains items would mess up our queue's ordering
            while ( ! stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    }

    public int size() {
        return stack1.size() + stack2.size();
    }
}

두개의 스택을 이용해서 FILO구조를 만들어 줍니다. dequeue 시점에 예비 스택에 처음 들어온 값이 마지막에 들어가도록 모든 값을 두번째 스택으로 옮긴 뒤 pop해줍니다. 해당 작업은 stack2에 꺼낼 값이 있으면 굳이 먼저 이동 시킬 필요 없으므로 필요할때만 shiftStacks 수행하면 시간복잡도를 줄일 수 있습니다.

Reference

Queue using Two Stacks | HackerRank