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

 

push()에 사용할 Queue를 q1, pop()에 사용할 Queue를 q2라고 하였다.

 

[ push() ]

q1.add()를 하여 데이터를 저장한다.

 

[ pop() ]

q1에서 pop할 1개의 데이터를 놔두고, 나머지 n-1개의 데이터를 q2로 이동시킨다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터가 q2로 옮겨진다. q1에 남아있는 데이터를 q1.remove()하여 가장 최근에 저장된 데이터를 반환한다. 다음에 진행될 pop()을 위해 q2가 비어있지 않을 경우, q1과 q2의 이름을 swap한다. 

 

 

구현 코드

---

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

public class QueueStack<E> {
    Queue<E> q1;
    Queue<E> q2;

    public QueueStack() {
        this.q1 = new LinkedList<>();
        this.q2 = new LinkedList<>();
    }

    public void push(E e) {
        q1.add(e);
    }

    public E pop() {
        // pop할 데이터 한개만 남기고 이동
        while (q1.size() > 1) {
            q2.add(q1.remove());
        }
        E result = q1.remove();

        // q1, q2 swap
        if (!q2.isEmpty()) {
            Queue<E> tmp = q1;
            q1 = q2;
            q2 = tmp;
        }

        return result;
    }
}

 

public class Main {

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

        qStack.push(1);
        qStack.push(2);
        qStack.push(3);
        qStack.push(4);
        qStack.push(5);

        System.out.println(qStack.pop());
        System.out.println(qStack.pop());
        System.out.println(qStack.pop());
        System.out.println(qStack.pop());
        System.out.println(qStack.pop());
    }
}

 

 

시간복잡도

---

push()는 add()를 한번만 하면 되기 때문에 O(1)의 시간복잡도를 갖는다.

pop()은 q1에 저장되어 있는 n개의 데이터 중 n-1개를 q2로 옮겨야 하므로, O(n)이 된다. 

 

 

 

 

 

 

🌈 참고 링크

• https://www.inflearn.com/course/