[LeetCode] 232. Implement Queue using Stacks

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

✅ 문제

Stack 2개를 활용하여 문제에서 주어진 Queue의 메서드를 모두 구현해야한다.

 

📌  접근방법

Stack과 Queue의 차이점은 데이터를 저장하고 추출하는 순서에 있다.

• Stack은 후입 선출(LIFO)을 기반으로 동작하는 자료구조.
• Queue는 선입 선출(FIFO)을 기반으로 동작하는 자료구조.

처음에 후입 선출을 어떻게 선입선출로 바꿀 수 있을까 고민했다.

후입 선출 자료구조에서 가장 처음 입력된 데이터는 가장 마지막 순서에 위치한다.

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

어떻게 역순으로 정렬할 수 있을까?

이 때 Stack이 2개 필요하다.

 

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

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

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

 

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

그러므로 두번째 Stack에 저장된 데이터는 Queue처럼 선입 선출의 순서를 가지게 된다.

 

🔑 풀이

import java.util.*;

class MyQueue {

    Stack<Integer> inputStack; // 입력 스택 (첫번째 스택)
    Stack<Integer> outputStack; // 출력 스택 (두번째 스택)

    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        peek(); // 출력 스택이 비어있다면, 입력스택의 요소를 출력 스택으로 옮김
        return outputStack.pop();
    }
    
    public int peek() {
        if(outputStack.isEmpty()) { // 출력 스택이 비어있다면, 입력 스택의 데이터를 이동
            while(!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop()); // 선입선출의 순서인 큐처럼 만들기 (출력 스택)
            }
        }
        return outputStack.peek(); // 출력 스택의 최상단 요소가 큐의 첫번째 요소
    }
    
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
}

 

• 데이터 입력 (push)
  • 새 데이터를 inputStack에 그대로 추가
  • outputStack에는 영향을 주지 않는다.
• 데이터 출력 (pop)
  • pop()을 호출하면 가장 첫 번째 데이터를 찾기 위해 peek()을 먼저 호출.
  • s2가 비어 있다면, s1의 데이터를 하나씩 outputStack로 옮긴다.
  • outputStack의 최상단 데이터를 제거하고 반환.
• 첫 번째 데이터 확인 (peek)
  • outputStack가 비어 있지 않다면, 최상단 데이터를 바로 반환.
  • outputStack가 비어 있다면 inputStack의 데이터를 outputStack로 한 번만 옮기고, 다시 inputStack으로 되돌리지 않는다.
• 큐가 비어 있는지 확인 (empty)
  • inputStack과 outputStack이 모두 비어 있다면 true를 반환.