[리트코드] 232. Implement Queue using Stacks 스택을 사용하여 큐를 구현하라

 

 

Contents

문제설명

먼저 들어온 것이 먼저 나가는 (선입선출) '큐'를 오직 두가지 스택을 사용해서 구현하라.
구현된 큐는 모든 큐의 기능에 사용할 수 있다(push, peek, pop, empty)

MyQueue 클래스 구현:

void push(int x)는 x를 큐의 뒤로 밀어낸다.
int pop()은 큐의 맨 앞의 요소를 제거하고 그것을 반환한다.
int peek()은 큐의 맨 앞의 요소를 반환한다.
boolean empty()은 만약 큐가 비어있으면 true를 반환하고, 비어있지 않다면 false를 반환한다.

Notes:

반드시 스택의 표준 운영만을 사용하세요. 즉, 맨 위에서 밀어내기, 맨 위에서 보기/팝하기, 크기 및 빈 작업만 사용할 수 있습니다.
언어에 따라 스택이 기본적으로 지원되지 않을 수 있습니다. 스택의 표준 작업만 사용하는 경우 리스트 또는 데크(이중 종단 큐)를 사용하여 스택을 시뮬레이션할 수 있습니다.

---

예시

 

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

---

문제 풀이

class MyQueue {

    Stack<Integer> input;
    Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }

    public void push(int x) {
        input.push(x);
    }

    public int pop() {

        if (output.empty()) {
            while(!input.empty()) {
                output.push(input.pop());
            }
        }

        return output.pop();

    }

    public int peek() {

        if (output.empty()) {
            while(!input.empty()) {
                output.push(input.pop());
            }
        }

        return output.peek();

    }

    public boolean empty() {
        return input.size() == 0 && output.size() == 0 ? true:false;
    }
}

 

---

문제점

pop과 peek에 공통으로 들어가는 부분을 따로 메소드로 만들어 사용하면 더 깔끔한 코드를 만들 수 있다.

if (output.empty()) {
    while(!input.empty()) {
    output.push(input.pop());
    }
}