99클럽 코테 스터디 5일차 TIL + 스택/큐(2)

 

 

225. 큐를 사용하여 스택 구현

 

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

클래스 를 구현합니다 MyStack:

• void push(int x)x 요소를 스택의 맨 위로 푸시합니다.
• int pop()스택 맨 위의 요소를 제거하고 반환합니다.
• int top()스택의 맨 위에 있는 요소를 반환합니다.
• boolean empty()true스택이 비어 있으면 반환하고 , false그렇지 않으면 반환합니다.

참고사항:

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

 

예시 1:

입력
["MyStack", "푸시", "푸시", "상단", "팝", "비어 있음"]
[[], [1], [2], [], [], []]
산출
[null, null, null, 2, 2, 거짓]

설명
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 2를 반환합니다.
myStack.pop(); // 2를 반환합니다.
myStack.empty(); // False를 반환합니다.

 

 

---

 

 

오 어제는 두 개의 스택을 이용해서 큐를 구현하는 거였다면, 오늘은 두 개의 큐를 이용해서 스택을 구현하는거다.

 

즉, FIFO를 LIFO로 만들면 된다.

 

 

[목표]

** pop() 호출 시 LIFO 순서로 동작해야한다.

- 큐는 양방향이니 스택처럼 단순히 두 스택을 이동하는 동작은 아닐 것임.

 

 

 

 

=> 그렇게 생각해서 나온 코드 1차

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new Queue<Integer>();
        queue2 = new Queue<Integer>();
    }
    
    public void push(int x) {
        queue1.push(x);
    }
    
    public int pop() {
        if(queue2.isEmpty()){
            while(!queue1.isEmpty()){
                queue2.push(queue1.pop());
            }
        }
        return queue2.pop();
    }
    
    public int top() {
        if(queue2.isEmpty()){
            while(!queue1.isEmpty()){
                queue2.push(queue1.pop());
            }
        }
        return queue2.top();
    }
    
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

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

 

 

<틀린 부분>

 

1) 하핳.. Queue는 new Queue<Integer>로 생성할 수 없다 ... ㅎㅎㅎㅎ 뭐하냐

-> Queue는 new LinkedList<>();로 생성해야함. 

 

2) queue에서는 push()가 아닌 offer()를 사용해야한다.

 

 

** 코드 2차

 

 

 

 

- 여기서 의문을 가지게 된 점이 있는데

 

1. 왜 queue1과 queue2를 교체해야 하는가?

- 답은 단순하다.

- > 다음 연산에서 queue1이 비어있으면 사용이 불가능하므로 queue1과 queue2를 교체해서 항상 queue1이 데이터를 유지하게 해야하는 것이다.

 

2. 교체 시 저장변수로 int temp를 사용하면 안될까?

- 안된다.

-> queue1은 Queue<Integer> 타입이므로 전체 큐를 int 변수에 저장할 수 없다.

 

 

3. top()메서드 -  queue2.offer(queue1.poll());에서 마지막 요소를 queue2로 이동하면 반환값이 없어지는 것 아닌가? 이 코드가 꼭 필요한가?

- 필요하다. 

왜냐하면 top() 메서드는 값을 반환하는 것이 아닌 확인하는 메서드이다.

 

int topElement = queue1.peek(); 

이 코드에서 pop하지않고 확인만 한다. 

큐1의 마지막 요소를 큐2로 모두 이동시키고 큐1과 큐2를 서로 교체하면 큐1이 다시 [1,2,3] 상태가 되어서 다음 pop이나 

push 호출 시 정상으로 동작가능하다. 

 

 

 

 

!! 만약  queue2.offer(queue1.poll()); 가 없다면?

 

=> 마지막 요소가 큐1에서 제거되어서 큐2로 이동하지 못한다.

후에 큐1과 큐2를 교체하면 큐1에 요소 하나가 없기 때문에 비정상적인 상태가 되어 이후 연산에 영향을 줄 수 있다.  

 

 

 

 

 

**회고

- 스택은 비교적 코드 생성에 어려움이 없었다면, 큐를 다룰 때 몰랐던 개념이나 생각할 점들이 많았던 것 같다.

- 점차 하나씩 배우면서 코드를 짜다보니 다음에 관련된 문제가 나오면 안 틀릴 수 있겠다라는 자신감이 생긴 것 같다.

- 그래도 더 열심히 잘 하자