99클럽 코테 스터디 4일차 TIL + 스택/큐

232. 스택을 사용하여 Queue 구현

두 개의 스택만 사용하여 선입선출(FIFO) 큐를 구현합니다. 구현된 큐는 일반 큐의 모든 기능( push, peek, pop, 및 empty)을 지원해야 합니다.

클래스 를 구현합니다 MyQueue:

• void push(int x)요소 x를 대기열의 맨 뒤로 밀어넣습니다.
• int pop()큐의 앞에서 요소를 제거하여 반환합니다.
• int peek()큐의 앞에 있는 요소를 반환합니다.
• boolean empty()true큐가 비어있는지 여부를 반환하고, 그렇지 않으면 반환합니다 false.

참고사항:

• 스택의 표준 연산 만 사용해야 합니다 . 즉 push to top, peek/pop from top, , size, is empty연산만 유효합니다.
• 언어에 따라 스택이 기본적으로 지원되지 않을 수 있습니다. 스택의 표준 연산만 사용하는 한, 리스트나 데크(양방향 큐)를 사용하여 스택을 시뮬레이션할 수 있습니다.

 

예시 1:

입력 
["MyQueue", "push", "push", "peek", "pop", "empty"] 
[[], [1], [2], [], [], []] 출력 
[null, null, null, 1, 1, false] 설명 
MyQueue myQueue = new MyQueue(); 
myQueue.push(1); // 큐는 [1]입니다. myQueue.push( 
2); // 큐는 [1, 2]입니다. (가장 왼쪽이 큐의 앞부분입니다.) 
myQueue.peek(); // 1을 반환합니다. 
myQueue.pop(); // 1을 반환합니다. 큐는 [2]입니다. 
myQueue.empty(); // false를 반환합니다.

 

제약사항:

• 1 <= x <= 9
• 최대 통화는 , , , 로만 100 가능합니다 .pushpoppeekempty
• pop및 에 대한 모든 호출이 peek유효합니다.

 

 

---

큐..? 홀리

 

- 우선 스택과 큐에 대한 정의를 생각해보자

 

1) 스택

- 스택은 LIFO, 마지막에 들어온 것이 가장 먼저 나간다.

 

2) 큐

- 큐는 FIFO, 선입선출이다.

 

 

문제에서 <스택 2개를 이용해서 큐를 구현하라>라고 했으니

-> 스택에 1,2,3이 순서대로 들어오면 

3

2

1

과 같은 순서로 stack1에 저장이되고, FIFO를 구현하기 위해 stack1에서 pop한 것을 stack2에 저장하면 

 

1

2

3

과 같은 순서로 stack2에 저장된다.

 

 

이렇게 해서 stack2에서 pop을 하면 큐를 구현할 수 있는 것이다.

 

 

 

** 전체 코드

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

 

 

- 원리만 안다면 쉽게 해결할 수 있는 문제였다.

- Stack선언 시 stack으로 선언해서 오류가 났다 ^^ 

- 이론으로만 배웠지 코드를 직접 짜는 것은 처음이었기에 재밌었다.......!