LeetCode 232(Implement Queue using Stacks, java)

0. 문제

https://leetcode.com/problems/implement-queue-using-stacks/

Implement Queue using Stacks - LeetCode

 

1. 문제 설명

- 이 문제는 Stack 자료구조 2개를 이용하여 Queue를 구현하는 것이 핵심이다.

- Stack 자료구조 2개를 이용하여 Queue의 메서드를 모두 구현해야 한다. 

 

2. 문제 해설

a) 첫 번째 접근

- 가장 근본적인 원리를 이해하면 이 문제는 굉장히 쉽게 풀 수 있다.

- 이를 위해서는 Stack과 Queue에 대한 기초적인 이해를 기본으로 한다. 

 

- Stack과 Queue의 근본적인 차이가 무엇일까?

- 간단하게 데이터를 저장하고 추출하는 순서에 있다. 

 

- Stack은 후입 선출을 기반으로 동작하는 자료구조다. 

- Queue는 선입 선출을 기반으로 동작하는 자료구조다. 

 

- 그렇다면 후입 선출을 어떻게 선입 선출로 바꿀 수 있을까? 

- 이에 대해 고민하는 것이 첫 번째 접근이다. 

 

b) 두 번째 접근

- 후입 선출 자료구조에서 가장 첫 번째로 입력된 데이터는 어디에 위치할까?

- 가장 마지막 순서에 위치한다. 

 

- 이것이 가장 큰 힌트가 된다.

- 즉, 후입 선출을 선입 선출로 만들기 위해서 후입 선출로 저장된 자료구조를 역순으로 정렬하면 된다. 

- 그렇다면 어떻게 역순으로 정렬할 수 있을까?

 

c) 세 번째 접근

- 후입 선출을 선입 선출로 만들기 위해서 후입 선출 자료구조를 역순으로 정렬한다.

- 이를 위해서 Stack이 2개가 필요한 것이다. 

 

- 첫 번째 Stack은 후입 선출의 순서대로 데이터를 저장한다.

- 두 번째 Stack은 첫 번째 Stack에서 추출한 데이터를 저장한다. 

- 첫 번째 Stack에 가장 마지막에 저장된 데이터는 두 번째 Stack에 가장 처음으로 저장되는 데이터다. 

 

- 즉, 두 번의 후입 선출이 수행되었으므로 선입 선출의 순서를 갖는다.

- 그러므로 두 번째 Stack에 저장된 데이터는 선입 선출의 순서를 갖는다.

 

- 다음 정답 코드를 보면서 이해해보자.

 

3. 정답 코드

class MyQueue {
    
    Stack<Integer> inputStack = new Stack<>();
    Stack<Integer> outputStack = new Stack<>();

    public MyQueue() {} // 생성자
    
    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        while(inputStack.isEmpty() == false) {
            outputStack.push(inputStack.pop()); // 선입 선출로 만들기
        }
        
        int result = outputStack.pop();
        
        while(outputStack.isEmpty() == false) {
            inputStack.push(outputStack.pop()); // 다시 원상복구
        }
        
        return result;
    }
    
    public int peek() {
        while(inputStack.isEmpty() == false) {
            outputStack.push(inputStack.pop());
        }
        
        int result = outputStack.peek();
        
        while(outputStack.isEmpty() == false) {
            inputStack.push(outputStack.pop());
        }
        
        return result;
    }
    
    public boolean empty() {
        return inputStack.isEmpty();
    }
}