Implement Stack using Queues

LeetCode의 Queue, Stack 튜토리얼에서 마지막 섹션의 두 번째 문제인 Implement Stack using Queues다.

Explore - LeetCode

이번 문제에서는 지난 문제(스택을 이용한 큐 구현)처럼 큐를 이용하여 스택을 구현하는 것을 목표로 하고 있다. 역시 큐 자료구조에서 사용할 수 있는 연산(push, pop, size, empty 등)만 사용하여 구현해보라고 하고 있는데 역시 두 개의 큐를 이용하여 구현해볼 수 있었다.

 

일단 생각한 것은 선입선출로 데이터가 삭제되는 특성상 가장 최근의 데이터를 삭제하려면 큐에서 맨 마지막으로 삽입된 데이터만 빼고 다른 큐에 옮겨놓은 후 다시 옮겨야겠다는 것이다. 그리고 큐에서 제일 최근에 삽입한 데이터는 스택에서 제일 먼저 삭제될 데이터기 때문에 데이터를 삽입할 때마다 peek 메서드가 반환할 변수를 업데이트해주는 것을 기반으로 구현해보았다.

import java.util.Queue;
import java.util.LinkedList;


class MyStack {
    private Queue<Integer> queue = new LinkedList<>();
    private Queue<Integer> bufferQueue = new LinkedList<>();
    int front;
    
    /** Initialize your data structure here. */
    public MyStack() {}
    
    /** Push element x onto stack. */
    public void push(int x) {
        front = x;
        queue.add(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int retVal;
        int queueSize = queue.size();
        
        if(queueSize >= 2){
            for(int index = 0;index < queueSize - 2; index++){
                bufferQueue.add(queue.poll());
            }
            
            front = queue.poll();
            retVal = queue.poll();
            
            for(int index = 0; index < queueSize - 2; index++){
               queue.add(bufferQueue.poll());
            }
            queue.add(front);
        } else {
            front = -1;
            retVal = queue.poll();
        }
        
        return retVal;
    }
    
    /** Get the top element. */
    public int top() {
        return front;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.size() == 0 && bufferQueue.size() == 0;
    }
}

Stack과는 달리 Queue는 인터페이스기 때문에 LinkedList를 활용하여 구현해보았다. 물론 문제에서 허용하는 메서드만 사용하였다.

 

언급했듯이 큐에서 가장 최근에 삽입된 데이터는 스택에서 삭제될 데이터기 때문에 push 메서드에서 front 변수를 항상 업데이트하는 것을 볼 수 있다. 이는 top 메서드(큐의 peek)에서 반환 값으로 사용된다. 그리고 삭제 연산에서 큐에 저장된 데이터의 개수에 따라 분기하는 것을 볼 수 있는데 이는 삭제 연산 시 가장 최근에 삽입된 데이터를 삭제 및 반환하고 front 변수를 업데이트하기 위함이다.

예를 들어 위처럼 7개의 데이터가 큐에 삽입되어 있을 경우 2개는 빼고 5개의 데이터만 bufferQueue에 옮겨놓는다. 그리고 옮겨지지 않은 마지막 두 개 중 최근의 것(7)이 삭제 및 반환할 데이터기 때문에 이를 변수에 저장해 두고 그 앞에 있는 것(6)이 그다음으로 삭제될 데이터기 때문에 이를 front 변수에 등록한다. 그리고 bufferQueue에 옮겨졌던 데이터들을 다시 queue로 옮긴 후 front 변수에 등록된 데이터(6)만 마지막으로 추가해줌으로써 스택처럼 가장 최근에 삽입된 요소를 삭제한 큐를 얻을 수 있다.

그럼 큐에 2개보다 적은 데이터가 들어있으면 어떨까? 이때는 front로 참조할 데이터가 남지 않기 때문에 그냥 스택에 있는 값을 반환해주고 끝난다. 이 경우 front는 초기값으로 재설정하거나 아니면 참조할 때 큐가 비어있는지 확인하고 참조해야 할 것이다.

 

...
// Removes the element on top of the stack.
public void pop() {
    while (q1.size() > 1) {
        top = q1.remove();
        q2.add(top);
    }
    q1.remove();
    Queue<Integer> temp = q1;
    q1 = q2;
    q2 = temp;
}
...

개선을 위해 솔루션을 확인해보니 굳이 bufferQueue로 옮겼다가 다시 queue로 옮길 필요가 없이 그냥 위처럼 queue와 bufferQueue를 치환하는 방법도 있었다. 이 경우 Queue<Integer> 타입의 임시 변수가 필요하지만 훨씬 더 간단하고 직관적인 방법이라 좋은 것 같다. 그리고 삭제 연산이 일어났을 때 큐에 있는 값들을 하나(삭제, 반환할 것)만 유지하고 전부 다른 큐로 옮기는 것을 볼 수 있었는데 이 경우 내가 작성한 코드처럼 큐의 크기가 2 이상일 경우와 미만일 경우로 분기를 나눌 필요가 없기 때문에 더 효율적인 것 같다.

...
public void push(int x) {
    q2.add(x);
    top = x;
    while (!q1.isEmpty()) {                
        q2.add(q1.remove());
    }
    Queue<Integer> temp = q1;
    q1 = q2;
    q2 = temp;
}
...

만약 삽입 연산 시마다 큐를 스택으로 변환하는 과정을 거친다면 위에서 큐끼리 치환하는 과정을 비슷하게 적용할 수 있을 것이다. 대신 여기서는 비어있는 두 번째 큐에 새로 삽입된 데이터를 넣고 원래 큐에 있던 데이터들을 전부 추가하는 방식으로 구현하였다. 한쪽 큐에 모든 데이터를 넣었다면 큐끼리 치환해서 원래 구조를 유지하고 있다.

그림으로 나타내면 위처럼 할 수 있을 것이다. 이 편이 좀 더 간단해 보이기도 한다.