2개의 Stack을 이용해 Queue를 구현해보자 (Java)

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 2개의 스택을 이용해서 Queue를 구현해 보는 시간을 갖도록 하겠습니다. 사실 Queue라는 것은 이미 자바의 컬렉션 프레임워크로 제공이 되는 것이고 내부적으로 최적화되어 구현되어 있기 때문에, 프로그래머가 따로 구현하지 않고 이걸 가져다가 사용하는 것이 더욱 빠르고 성능이 좋습니다. 스택을 이용해 큐를 구현한다는 것은 성능적인 측면에서의 의미가 아니라, 그냥 하나의 퍼즐이며, 스택을 이용하면 큐를 구현할 수도 있구나! 하고 알아가는 용도로만 사용하면 됩니다.

 

 문제에서는 다음과 같이 MyQueue라는 클래스를 쥐어주고, 이 클래스의 메소드를 구현하는 것을 요구합니다. 물론! 구현할 때 2개의 스택을 사용해야겠죠?

class MyQueue {
    public MyQueue() {

    }
    
    public void push(int x) {

    }
    
    public int pop() {

    }
    
    public int peek() {
   
    }
    
    public boolean empty() {
  
    }
}

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

 

2개의 스택으로 큐를 어떻게 구현할까?

 문제 풀기전까지는 꽤 간단하지 않을까? 생각했지만 어려웠습니다.. 알고리즘을 공부하는 학생으로써, 이미 많은 실력좋은 사람들이 올려놓은 풀이와 아이디어를 보며 경외심이 드네요.. 

 

 2개 스택으로 큐를 구현하는 아이디어는 다음과 같습니다!

 

 

 Input 스택, 그리고 Output 스택 이렇게 총 두 개의 스택을 두는 것입니다. 이 두 개 스택만 있으면 큐를 완벽하게 구현해낼 수가 있습니다. 그리고 각각의 용도는 위에 써져 있는 대로입니다.

 

그러면 이 두개 스택을 이용해서 큐의 ADT를 어떻게 구현할 것인가 예를 들어보도록 합시다.

 

첫 번째 예시

 Queue에 다음과 같은 연산을 해 보도록 합시다.

 

 A 삽입 → B 삽입 → C 삽입 → POP → POP

 

Queue는 FIFO(First In First Out)자료구조이므로, 위와 같은 예시에서는 A B 데이터가 출력되는 결과로 이어져야 합니다!

 위와 같은 상태에서 POP을 2회 진행하니, A B라는 결과가 나옵니다. 우리가 예상했던 대로 잘 동작하네요!

 

두 번째 예시

그럼 두 번째 예시를 한번 더 들어보겠습니다.

이번에는 좀 더 복잡한 예시를 들어볼까요?

두 번째 예시에서는 큐에 다음과 같은 연산을 진행해보도록 하겠습니다.

 

A 삽입 → B 삽입 → C 삽입 → POP → POP → D 삽입 → E 삽입 → POP → POP

 

 

 

 스택 2개를 이용해 큐를 구현하면 이런 구조가 된답니다!

 주저리 주저리 설명했지만 핵심은 다음과 같습니다.

 

1. Input Stack, Output Stack 두개를 이용한다!
2. Input Stack은 데이터 삽입용, Output Stack은 데이터의 추출 및 탐색용이다!
3. Output Stack에서 데이터를 추출할 때, 이 Output Stack이 비어있다면 Input Stack의 모든 원소를 추출해 Output Stack에다가 넣는다!

 

소스코드

class MyQueue {
    Deque<Integer> input; // 데이터 삽입용 스택
    Deque<Integer> output; // 데이터 추출용 스택

	// 생성자를 통한 데이터 삽입용 / 출력용 스택을 초기화
    public MyQueue() {
        input = new ArrayDeque<>();
        output = new ArrayDeque<>();
    }
    
    // 데이터의 삽입은 Input Stack으로!
    public void push(int x) {
        input.push(x);
    }
    
    // 큐로부터 데이터를 추출
    public int pop() {
    	//Output Stack이 비어있다면
        if(output.isEmpty()) {
        	//Input Stack의 모든 원소를 Output Stack에다가 때려박는다
            while(!input.isEmpty())
                output.push(input.pop());
        }

		// Output Stack에서 데이터를 추출
        return output.pop();
    }
    
    // 상동
    public int peek() {
        if(output.isEmpty()) {
            while(!input.isEmpty())
                output.push(input.pop());
        }

        return output.peek();     
    }
    
    // Input stack과 Output stack이 모두 비어있어야 empty상태이다
    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();
 */

 

긴 글 읽어주셔서 감사드립니다. 이해가 되지 않는 곳이 있다면 댓글로 남겨주시면 최대한 도와드리겠습니다^^