[자바 알고리즘 인터뷰] 9장 스택,큐 (4) 큐를 이용한 스택 구현

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

 

 

- 큐를 이용해 다음 연산을 지원하는 스택을 구현하라. 

 

push(x) : 엘리먼트 x를 스택에 삽입한다. 

pop() : 스택의 첫 번째 엘리먼트를 삭제한다. 

top() : 스택의 첫 번째 엘리먼트를 가져온다. 

empty() : 스택이 비어있는지 여부를 리턴한다. 

 

 

풀이 1) push()할 때 큐를 이용해 재정렬 

 

- 큐를 선언 하고 큐 추상 자료형의 기본 연산으로 구현 

 

- 가장 복잡한 부분은 push()이다. 

- 엘리먼트를 삽입한 후에 방금 삽입한 엘리먼트를 맨 앞에 두는 상태로 전체를 재정렬하면 나머지는 기본적인 큐 연산으로 쉽게 구현이 가능하다. 

 

class MyStack {
    //큐 변수, 구현체는 LinkedList로 선언
    Queue<Integer> queue = new LinkedList<>();

    public void push(int x)
    {
        //엘리먼트 삽입
        queue.add(x);
        //맨 앞에 두는 상태로 전체 재정렬
        for(int i=1; i<queue.size(); i++)
        {
            queue.add(queue.remove());
        }
    }

    public int pop()
    {
        //재정렬한 상태이므로 큐 연산으로 추출
        return queue.remove();
    }

    public int top()
    {
        //재정렬한 상태이므로 큐 연산으로 조회
        return queue.peek();
    }

    public boolean empty() 
    {
        //크기를 비교해 비어 있는지 확인
        return queue.size() == 0;
    }
}

/**
 * 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();
 */

0밀리초