99클럽 코테 스터디 4일차 TIL + [LeetCode 232번] Implement Queue using Stacks

 

오늘의 학습 키워드

• 스택, 큐
• 자바로 큐 구현

LeetCode 232번] Implement Queue using Stacks

문제 요약

• 오직 2개의 스택만을 이용해서 큐를 구현하라
• push, pop, peek, empty 함수를 구현

해결 방법

 

• 두 개의 스택:
  • inputStack: 새로운 원소가 들어오는 스택
  • outputStack: 원소가 나가는 스택
• push(x) 메소드:
  • 새로운 원소를 항상 inputStack 넣음
• pop()과 peek() 메소드:
  • outputStack이 비어있으면, inputStack의 모든 원소를 꺼내서 outputStack에 넣음. (이 과정에서 원소들의 순서가 뒤집히게 되면서  마지막이 처음으로 오게됨
  • 그 후 outputStack의 맨 위 원소를 반환
• empty() 메소드:
  • 두 스택이 모두 비어있으면 큐도 비어있는 것

 

 

 

알고리즘:

1. inputStack에서 outputStack으로 옮길 때 원소들의 순서가 뒤집힌다는 점을 활용한 것

Java 코드 구현

import java.util.Stack;
class MyQueue {
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;

    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        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();
    }
}

 

오늘의 회고

What?

일단 너무 어렵다,, 그래서 이해를 하기위해

스택과 큐를  arrayList로 직접 만들어 보고  구현을 진행했다.

How?

스택은 마지막에 넣은게 먼저 나오니까 다른스택에 넣어주면 

큐처럼 처음에 넣은게 먼저 나오도록 할수있다.

123  - > 321   -> 123 

Point?