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

https://hyunki99.tistory.com/26

이전 글과 비슷하게 2개의 큐로도 스택을 구현할 수 있다.

 

큐는 많이 사용되는 자료구조 중 하나이다.

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

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

 

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

---

1. 원리

1. 메인 큐와 임시 큐를 준비한다.
2. 메인 큐에 1개의 원소가 남을 때까지 dequeue하고, 임시 큐에 넣는다.
3. 마지막 남은 1개의 원소는 result 변수에 저장한다.
4. 임시 큐에 남아있는 원소들을 다시 메인 큐로 이동시킨다.
5. result를 리턴한다.

---

2. 예제코드

 

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

class StackQ{
	Queue<Integer> mainQueue;
	Queue<Integer> tempQueue;
	
	public StackQ() {
		mainQueue = new LinkedList<>();
		tempQueue = new LinkedList<>();
	}
	
	public void push(int a) {
		mainQueue.offer(a);
	}
	
	public int pop() {
		int result=-1;
		
		if(mainQueue.isEmpty()) {
			return -1;
		}
		
		while(mainQueue.size() != 1) {
			tempQueue.offer(mainQueue.poll());
		}
		result = mainQueue.poll();
		
		//나머지를 다시 main큐로 옮겨준다.
		if(!tempQueue.isEmpty()) {
			while(!tempQueue.isEmpty()) {
				mainQueue.offer(tempQueue.poll());
			}
		}
		
		return result;
	}
}

public class Sq {
	public static void main(String[] args) {
		StackQ sq = new StackQ();
		sq.push(1);
		sq.push(2);
		sq.push(3);

		System.out.println(sq.pop()); //3
		
		sq.push(4);
		System.out.println(sq.pop()); //4
		
		System.out.println(sq.pop()); //2
		System.out.println(sq.pop()); //1
	}
}

 

---

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

https://ryu-e.tistory.com/96