[99클럽 코테 스터디 5일차 TIL] Implement Stack using Queues

 

 

 

 

오늘의 키워드

• stack
• queue

 

 

leetcode 225번 - Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/

 

 

 

문제

Implement a last-in-first-out (LIFO) stack using only two queues.

The implemented stack should support all the functions of a normal stack (push, top, pop, and empty)

 

 

두개의 큐를 사용해서 스택을 구현하는 문제이다.

 

 

 

입력예제

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

 

출력예제

[null, null, null, 2, 2, false]

 

 

풀이

1. 두개의 큐를 생성한다. (하나는 temp용)

2. q에 add 한다.

3. q의 add, poll, peek 을 이용해서 temp 큐에 FIFO 해주면서 스택의 push, pop, peek을 구현한다.

4. q가 isEmpty인지 확인한다.

 

 

class MyStack {
    private Queue<Integer> q;
    private Queue<Integer> temp;

    public MyStack() {
        q = new LinkedList<>();
        temp = new LinkedList<>();
    }
    
    public void push(int x) {
        q.add(x);
    }
    
    public int pop() {
        for(int i=0; i<q.size()-1; i++){
            temp.add(q.poll());
            q.add(temp.poll());
        }

        return q.poll();
    }
    
    public int top() {
        int n =0;
        for(int i=0; i<q.size(); i++){
            n = q.poll();
            temp.add(n);
            q.add(temp.poll());
        }

        return n;
    }
    
    public boolean empty() {
        return q.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();
 */

 

 

어제 문제와 유사해서 쉽게 풀 수 있었다. 스택과 큐의 함수가 헷갈릴 때가 있는 데

다시 한번 정리할 수 있어 좋았다. 문제를 풀땐 생각하지 못했는데 TIL을 작성하면서

굳이 temp 큐에 안넣어도 똑같은 것 같아서 temp만 q로 변경해보았다.

 

 

 

class MyStack {
    private Queue<Integer> q;
    private Queue<Integer> temp;

    public MyStack() {
        q = new LinkedList<>();
        temp = new LinkedList<>();
    }
    
    public void push(int x) {
        q.add(x);
    }
    
    public int pop() {
        for(int i=0; i<q.size()-1; i++){
            q.add(q.poll());
        }

        return q.poll();
    }
    
    public int top() {
        int n =0;
        for(int i=0; i<q.size(); i++){
            n = q.poll();
            q.add(n);
        }

        return n;
    }
    
    public boolean empty() {
        return q.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();
 */

 

 

 

큐 하나만으로도 스택을 구현할 수 있게 수정했다.