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

https://leetcode.com/problems/implement-queue-using-stacks/

 

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

 

push(x) : 엘리먼트 x를 큐 마지막에 삽입한다. 

pop() : 큐 처음에 있는 엘리먼트를 제거한다. 

peek() : 큐 처음에 있는 엘리먼트를 조회한다. 

empty() : 큐가 비어 있는지 여부를 리턴한다. 

 

 

풀이 1) 스택 2개 사용 

 

- 가장 먼저 삽입된 아이템을 끄집어 내야 하는데, 스택은 아무리 추가, 삭제를 반복해도 가장 가장 마지막에 삽입된 아이템만 넣고 빼기를 반복하므로 하나의 스택만을 이용해서는 풀 수 없다.

 

- 이 문제를 풀기 위해서는  2개의 스택이 필요하다. 

 

- 특히 추출시 pop()과 조회 시 peek()는 결국 같은 데이터를 끄집어낸다는 점에 착안해, 이번에는 pop()을 할 때 peek()를 호출해 한 번에 처리하는 형태로 다음과 같이 구현한다. 

 

class MyQueue {
    //삽입할 때 사용하는 스택 선언
    Deque<Integer> input = new ArrayDeque<>();
    //추출할 때 사용하는 스택 선언
    Deque<Integer> output = new ArrayDeque<>();
    
    public void push(int x) {
        //삽입은 삽입 스택에 단순 추가
        input.push(x);
    }
    
    public int pop() {
        //추출 스택 조회하면서 비어있다면 처리 진행
        peek();
        //추출 스택에 마지막 값 추출
        return output.pop();
    }
    
    public int peek() {
        //추출 스택에 저장된 게 없다면 진행
        if(output.isEmpty()) {
            //삽입 스택이 비워질 때까지 진행
            while(!input.isEmpty())
            {
                //삽입 스택에서 추출한 결과를 추출 스택에 삽입(역순으로 저장된다.)
                output.push(input.pop());
            }
        }
        //가장 나중에 삽입된 결과 조회
        return output.peek();
    }
    
    public boolean empty() {
        //두 스택이 모두 비어 있는 것으로 처리
        return input.isEmpty()&&output.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();
 */

0밀리초