Queue를 활용해서 Stack을 만들기

저번 Stack을 활용해서 Queue만들기글을 참고하면, stack과 queue의 기본 구조에 대해서 이해할 수 있다.

 

Stack을 활용해서 Queue만들기 (tistory.com)

Stack을 활용해서 Queue만들기

큐는 선입 선출의 구조를, 스택은 후입 선출의 구조를 갖는다.

 

큐를 활용해서 스택만들기

큐활용해서 스택을 만들기 위해서는 두개의 큐가 필요하다.

아까와 같이 편의상 첫번째 큐를 q1, 두번째 큐를 q2라고 하겠다.

• push 구현 방법
  • q1으로 enqueue해서 데이터를 저장한다.
• pop 구현 방법
  • q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()한다.
  • 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
  • q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
  • 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

코드

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


public class test1<T>{
	
	 Queue<T> q1 = new LinkedList<>();
	 Queue<T> q2 = new LinkedList<>();
	
	public void push(T t) {
		 q1.offer(t);
	}
	
	public T pop() {
		
		Queue<T> temp = new LinkedList<>();
		while(q1.size() > 1) {
			q2.offer(q1.poll());
		}
			
			temp = q1;
			q1 = q2;
			q2=temp;

			return q1.poll();
		}
	       
	}