[자료구조] Stack으로 Queue 구현하기

 

enqueue() 구현에 사용할 Stack을 inStack, dequeue() 구현에 사용할 Stack을 두 번째 outStack으로 선언하였다.

 

[ enqueue() ]

inStack에 push()하여 데이터를 저장하도록 구현하였다.

 

[ dequeue() ]

outStack이 비어있다면 inStack에서 데이터를 가져온다. 이 결과 가장 먼저 들어온 데이터가 outStack의 top에 위치하게 된다. outStack.pop()으로 가장 먼저 들어온 데이터를 반환한다. outStack이 비어있지 않다면 pop()을 해서 데이터를 추출하고, outStack의 데이터를 다 추출하면 inStack에서 데이터를 가져오게 된다.

 

구현 코드

---

import java.util.Stack;

public class StackQueue<E> {
    Stack<E> inStack;
    Stack<E> outStack;

    public StackQueue() {
        this.inStack = new Stack<>();
        this.outStack = new Stack<>();
    }

    public void enqueue(E e) {
        inStack.push(e);
    }

    public E dequeue() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop()); 
            }
        }

        return outStack.pop();
    }

}

outStack이 비어있을 때만 inStack에서 데이터를 가져온다. 

 

public class Main {

    public static void main(String[] args) {
        StackQueue<Integer> stackQ = new StackQueue<>();

        stackQ.enqueue(1);
        stackQ.enqueue(2);
        stackQ.enqueue(3);
        stackQ.enqueue(4);

        System.out.println(stackQ.dequeue());
        System.out.println(stackQ.dequeue());
        System.out.println(stackQ.dequeue());
        System.out.println(stackQ.dequeue());
    }
}

 

 

시간복잡도

---

enqueue()는 push() 연산 한번만 이루어지기 때문에 시간복잡도는 O(1)이다.

 

dequeue()는 두 가지 경우를 고려해봐야 한다. 

첫 번째는 worst case인 outStack이 비어있는 경우이다. inStack에 있는 n개의 데이터를 전부 pop(), push()를 수행하여 outStack으로 옮겨주어야 한다. 따라서 총 2*n 번의 연산이 수행되어 O(n)의 시간복잡도를 갖는다.

두 번째는 outStack이 비어있지 않은 경우이다. 이 경우는 pop()만 해주면 되기 때문에 O(1)의 시간복잡도를 갖는다.

이를 종합해보았을 때 dequeue()는 amortized O(1)의 시간복잡도를 갖는다고 할 수 있다. 

 

 

 

 

 

🌈 참고 링크

• https://www.inflearn.com/