큐(Queue)는 Collection 인터페이스를 확장하는 클래스로, 선입선출(FIFO, First-In-First-Out) 방식으로 삽입과 삭제 연산을 지원합니다. 반면 스택(Stack)은 Vector 클래스의 하위 클래스로, 후입선출(LIFO, Last-In-First-Out) 구조의 객체 집합을 나타냅니다. 즉, 스택의 맨 위에 가장 마지막에 추가된 요소가 가장 먼저 제거되는 구조입니다.
이처럼 서로 다른 두 자료구조지만, 스택 두 개를 활용하면 큐의 동작 방식을 그대로 구현할 수 있습니다. 아래 예제에서는 두 개의 스택을 사용하여 큐를 구현하는 방법을 살펴보겠습니다.
동작 원리
핵심 아이디어는 간단합니다.
- 삽입(enqueue): 첫 번째 스택(stack1)에 요소를 push 합니다.
- 삭제(dequeue): 두 번째 스택(stack2)이 비어 있으면, 첫 번째 스택의 모든 요소를 pop 하여 두 번째 스택에 push 합니다. 이 과정에서 요소들의 순서가 뒤집히므로, 가장 먼저 들어간 요소가 두 번째 스택의 맨 위에 위치하게 됩니다. 이후 두 번째 스택에서 pop 하면 FIFO 순서대로 요소가 제거됩니다.
예제 코드
import java.util.*;
public class QueueUsingStackTest {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
public void enqueue(int element) {
stack1.push(element);
System.out.println(element + " inserted");
}
public void dequeue() {
if(stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
System.out.println(stack2.pop() + " removed");
}
public static void main(String args[]) {
QueueUsingStackTest test = new QueueUsingStackTest();
test.enqueue(10);
test.enqueue(50);
test.enqueue(100);
test.dequeue();
}
}실행 결과
10 inserted 50 inserted 100 inserted 10 removed
결과 분석
위 실행 결과를 보면 10, 50, 100 순서로 요소를 삽입한 후, 삭제 연산을 수행했을 때 가장 먼저 넣었던 10이 가장 먼저 제거된 것을 확인할 수 있습니다. 이는 스택의 LIFO 특성을 두 개 조합하여 큐의 FIFO 특성을 성공적으로 재현했음을 의미합니다.
참고로 이 방식의 시간 복잡도는 삽입 연산이 O(1)이며, 삭제 연산은 최악의 경우 O(n)입니다. 다만 이미 옮겨진 요소들은 두 번째 스택에 그대로 유지되므로, 전체적으로 평균적인 성능은 양호한 편입니다.