[Java] 자바 두 개의 스택(Stack)으로 큐(Queue) 구현하기

스택은 많이 사용되는 자료구조 중 하나이다.

나중에 들어온 것이 먼저 나오는 구조로서

LIFO (Last In First Out)의 형태를 띈다.

 

2개의 스택을 활용해서 큐를 구현하는 방법을 알아보자.

---

1. 원리

 

스택을 하나 사용하면 LIFO지만, 2개의 스택을 사용해서 FIFO(First in First Out) 형태인 큐 자료구조를

구현할 수 있다.

 

스택과 큐에서 자료가 어떤 방식으로 들어오고(push) 나가는지(pop)만 이해하면 어렵지 않다.

스택 :   1, 2, 3을 push하고 pop하면 3, 2, 1 순으로 나오게 된다.

큐 : 1, 2, 3을 enqueue하고 dequeue하면 1, 2, 3 순으로 나오게 된다.

 

즉, 스택과 큐는 서로 역순(reverse)이다. 나오는 자료를 역순 뒤집어 주기만 하면

2개의 스택으로 하나의 큐를 구현할 수 있다.  

 

---

2. 수도 코드

1. Enqueue Operation

Push every input element to the Stack#1

2. Dequeue Operation

If(Stack#2 is empty)
       pop every element in the Stack#1
       and push them to the Stack#2 until Stack#1 is Empty
pop from Stack#2

 

---

3. 구현 예제

 

import java.util.Stack;

//2개의 Stack을 이용해서 Queue구현
class Qstack {
	Stack<Integer> oldStack;
	Stack<Integer> newStack;
	
	public Qstack() {
		oldStack = new Stack<>();
		newStack = new Stack<>();
	}
	
	public void enqueue(int a) {
		oldStack.push(a);
	}
	
	public int dequeue() {
		int result = -1;
		
		if(newStack.isEmpty()) {
			while(!oldStack.isEmpty()) {
				newStack.push(oldStack.pop());
			}
			result = newStack.pop();
		}
		
		 //oldStack에 남아있는 값이 있으면 다시 #1로 옮겨준다.
		if(!newStack.isEmpty()) {
			while(!newStack.isEmpty()) {
				oldStack.push(newStack.pop());
			}
		}
		
		return result;
	}
}	

public class Qs {
	public static void main(String[] args) {
		Qstack a = new Qstack();
		a.enqueue(1);
		a.enqueue(2);
		a.enqueue(3);
		
		System.out.println(a.dequeue());
		System.out.println(a.dequeue());
		System.out.println(a.dequeue());
	}
}

 

 

 

---

참고 문헌 : Do it! 자바 완전정복

 

스택오버플로우

https://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks/69436#69436