문제

LeetCode 232번-Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x): Pushes element x to the back of the queue.
• int pop(): Removes the element from the front of the queue and returns it.
• int peek(): Returns the element at the front of the queue.
• boolean empty(): Returns true if the queue is empty, false otherwise.

예시

입력:

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

출력:

[null, null, null, 1, 1, false]

설명:

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 {

    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    // 큐에 집어넣는다.
    public void push(int x) {
        inStack.push(x);
    }
    
    // 첫번째 요소를 제거하고 리턴한다.
    public int pop() {
        shiftStacks();
        return outStack.pop();
    }
    
    // 첫번째 요소를 리턴한다.
    public int peek() {
        shiftStacks();
        return outStack.peek();
    }
    
    // 큐가 비어있는지 확인한다.
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    // inStack에 있는 요소들을 outStack에 집어넣는다.
    private void shiftStacks() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

Stack은 FIFO 구조이고, Queue는 LIFO이다. 따라서 두 개의 Stack을 갖고 구현해야 하는 문제이다.
1. 2개의 스택 inStack과 outStack을 선언하고, 생성자에서 초기화해주었다.
2. push() 메소드를 통해서 inStack에 값을 추가한다.
3. pop() 메소드와 peek() 메소드 둘 다 inStack에 있는 값을 outStack에 넣는 과정(LIFO -> FIFO)이 필요하다. -> shiftStacks()
3-1. 만약 outStack이 비어있다면 inStack에서 pop한 요소를 outStack에 push한다. outStack이 비어있지 않다면 굳이 추가하지 않고도 outStack에 있는 요소를 반환하면 된다.
3-2. 스택에서의 pop은 맨 위에 있는 요소(가장 마지막에 추가한 요소)를 리턴하고 삭제한다.
3-3. inStack에 가장 마지막에 들어온 요소를 outStack 가장 아래에 추가한다.
4. pop() 메소드는 outStack에 가장 위에 있는 요소를 리턴하고 삭제한다.
5. peek() 메소드는 outStack에 가장 위에 있는 요소를 리턴만 한다.
6. empty() 메소드는 inStack과 outStack 모두 비어있는지의 여부를 리턴한다.

회고

Stack을 갖고 Queue를 구현할 수 있다는 점이 흥미롭다. 이제 자료구조 코테 문제를 좀 푸나보다. 주말동안 자료구조를 다시 한 번 공부해야겠다..