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

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Leetcode 594. Queue를 이용해 Stack을 구현하는 문제

 가끔씩 기술면접을 본 후기를 보면 스택을 이용해 큐를, 혹은 반대로 큐를 이용해 스택을 어떻게 구현할 수 있는가에 대한 질문이 종종 나오는 것을 볼 수가 있다. 사실 복잡한 문제는 아니고, 자료구조에 대한 지식이 있고 충분한 시간이 주어진다면 떠올릴 수 있지만, 한 번도 생각해보지 않았다가 질문을 마주하게 되면 당황할 수 있을 질문이다.

 

1. 문제 설명

1.1 문제 상황

문제를 통해, 우리가 어떤 상황을 해결해야 하는지 자세히 알아보도록 하자.

 

 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).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

 

• ◈ Notes:
• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

 

• Constraints:
• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

 

 오로지 Queue 두개를 이용해서 스택과 동일하게 동작하도록 하는 클래스를 구현하면 되는 문제이다. 문제에서는 다음과 같이 클래스의 메소드를 공란으로 두고, 저 안을 채워서 메소드를 구현하라고 한다. 우리가 구현한 클래스와 메소드를 이용해서 서버측에서 stack과 관련된 연산을 진행하고, 그에 대한 결과가 Expected Value와 동일하다면 정답, 그렇지 않다면 오답으로 처리하는 시스템이다.

 

 그러니까 문제를 간단히 요약하면, 큐의 ADT를 이용해서 스택의 ADT를 구현하라는 내용이다.

 

class MyStack {
    public MyStack() {
    
    }
    
    public void push(int x) {
 
    }
    
    public int pop() {

    }
    
    public int top() {

    }
    
    public boolean empty() {

    }
}

 

2. 문제 풀이

 사실 큐를 이용해 스택을 구현하는 건 아이디어를 떠올리기가 어려워서 그렇지, 풀이를 보면 간단하다! 문제에서는 두 개의 큐를 이용하라고 했지만, 본 포스팅에서는 한 개의 큐만을 이용해서 스택을 구현할 것이다. 

 큐를 이용해 스택을 구현하는 아이디어는 다음 한 문장으로 요약될 수가 있다.

 

"큐에 데이터를 삽입할 때마다, 이전에 이미 들어있었던 원소들을 새로 들어온 원소의 앞쪽으로 옮긴다"

 

 이렇게만 해 주면, queue에 들어 있는 원소들을 꺼낼 때마다 stack에서 꺼내는 순서와 동일하도록 만들 수가 있다. 문장만 봐서는 이해가 가지 않을 테니 조금 더 자세히 알아봅시다!

 

2.1 MyStack() 메소드

 

 문제에서는, 우리가 구현한 스택 클래스가 다음과 같이 활용될 것이라고 나와있었다.

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

 

 우리가 구현한 MyStack이라는 클래스의 객체를 생성하고, 이를 하나의 스택 인스턴스처럼 사용한다. 그러면, 생성자 부분에 다음과 같이, Queue를 선언하는 부분을 넣어보도록 하자.

 

class MyStack {
	Queue<Integer> queue;
    
    public MyStack() {
    	queue = new LinkedList<Integer>();
    }
	...

 

 큐는 LinkedList 기반으로 구현된 것을 사용했다. 사실 Deque나 Queue나 배열 기반으로 구현된 컬렉션 인스턴스를 사용하는 경우가 많지만, 그냥 여기서는 연결리스트 기반으로 구현된 것을 사용하겠다. 이유는 없다!

 

2.2 pop() top() empty() 메소드

 

 왜 push를 설명하지 않고 다른 메소드를 먼저 설명하느냐? 할 수도 있다. 사실 이 풀이에서 가장 복잡한 부분은 push메소드이다. 이걸 설명하기 전에 상대적으로 간단한 위 메소드들을 먼저 설명하는 것이 더 효율적이라고 생각해서 먼저 설명하는 것이다.

 

class MyStack {
	...
    public int pop() {
        return queue.remove();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

 

 보통 Queue에서 데이터의 입력이 이루어지는 입구 측을 Front, 데이터의 출력이 이루어지는 출구 측을 Back이라고 칭한다. (중요한 이야기!)

 

 예를 들어서 Queue에 1, 2, 3, 4, 5를 순서대로 넣는 연산을 진행하였다고 해 보자. 

 그러면 다음 그림과 같은 상태가 된다.

 

 (Front)          [5   4   3   2   1]           (Back)

 

 그리고 Queue연산에서 peek(), pop()이라는 메소드는 위와 같은 상태에서 가장 뒤쪽(Back)에 있는 데이터를 탐색하고, 추출하는 메소드이다. 예를 들어, 위와 같은 상태에서 queue.peek()이나 pop()을 호출하면 1이 리턴이 되는 것이다. 

 

2.3 push() 메소드

 

 코드를 먼저 제시하고 설명을 하겠다.

class MyStack {
    ...
    public void push(int x) {
        queue.add(x);
        for(int i=0; i<queue.size()-1; i++) {
            queue.add(queue.remove());
        }
    }
    ...
}

  

 코드를 설명하기 전에 스택의 개념부터 되짚어보자. 스택이라는 것은 LIFO(Last In First Out)구조이다. 즉, 가장 처음에 들어간 것이 가장 마지막에, 가장 마지막에 들어간 것이 가장 먼저 추출되는 구조라는 의미이다.

 

 그러나 큐는 FIFO(First In First Out)구조이다. 즉 가장 처음에 들어간 것이 가장 처음 나오며, 가장 마지막에 들어간 것이 가장 마지막에 추출되는 구조이다. 

 

우리가 하는 작업은 큐를 이용해 스택을 구현하는 것이다. 

예를 들어 다음과 같이 큐에 순서대로 a b c d가 입력되었다고 해 보자.

 

Queue [d c b a]

 

이 때 스택이라면 가장 나중에 입력된 알파벳 순서대로, 즉 d c b a순서대로 출력이 이루어져야 한다.

이 순서대로 출력을 하려면 Queue의 앞쪽에서부터 출력이 이루어지도록 해야 겠지만, 큐는 데이터를 Front측으로 추출할 수 없다.

 

 큐를 스택처럼 사용하기 위해서는 큐에 데이터를 삽입하는 과정에서 특수한 작업이 필요하다. 그것은 바로, 원소가 삽일될 때마다, 원소가 삽입되기 이전에 큐에 존재하고 있던 데이터를, 방급 삽입된 원소의 앞쪽으로 보내주는 루틴을 추가해주는 것이다.

 

1. Queue에 a를 삽입한다.

Queue [a]

 

2. Queue에 b를 삽입한다.

Queue [b a] → [ a  b] (b가 들어오기 이전에 존재했던 원소인 a를 모두 b의 앞으로 보낸다)

 

3. Queue에 c를 삽입한다.

Queue [c a b] → [a b c] (c가 들어오기 이전에 존재했던 원소인 a와 b를 c의 앞으로 보낸다)

 

4. Queue에 d를 삽입한다.

Queue [d a b c] → [a b c d] (d가 들어오기 이전에 존재했던 원소인 a b c를 d의 앞으로 보낸다)

 

우리는 queue에 a b c d를 순서대로 삽입하였고, 삽입할 때마다 위와 같은 특수한 과정을 수행하였다.

이 상태에서 큐의 pop연산을 통해 꺼내면 d c b a순서대로 추출이 되는데, 이는 스택에서의 LIFO구조와 일치한다!

이로써 큐를 이용해 스택을 구현할 수 있었다.

 

3. 전체 코드

class MyStack {

    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<Integer>();    
    }
    
    public void push(int x) {
        queue.add(x);
        for(int i=0; i<queue.size()-1; i++) {
            queue.add(queue.remove());
        }
    }
    
    public int pop() {
        return queue.remove();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}