문제
- 2개의 스텍을 사용하여 큐를 구현하세요.
- 예제
MyQueue queue = new MyQueue();
queue.enqueue(1);
queue.enqueue(2);
System.out.println(queue.dequeue()); // 1 출력
queue.enqueue(3);
System.out.println(queue.dequeue()); // 2 출력
System.out.println(queue.dequeue()); // 3 출력
풀이
import java.util.Stack;
public class Average_StackToQueue {
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>();
System.out.println(queue.dequeue()); // null --> feature로 정의하는지 검토, edge case 테스트 진행하는지 확인
queue.enqueue(1);
queue.enqueue(null); // 예외처리 정의하는지 검토
queue.enqueue(2);
System.out.println(queue.dequeue()); // 1
queue.enqueue(3);
System.out.println(queue.dequeue()); // 2
System.out.println(queue.dequeue()); // 3
System.out.println(queue.dequeue()); // null --> feature로 정의하는지 검토
}
public static class MyQueue<T> {
Stack<T> inQueue;
Stack<T> outQueue;
public MyQueue() {
this.inQueue = new Stack<>();
this.outQueue = new Stack<>();
}
public void enqueue(T value) {
inQueue.add(value);
}
public T dequeue() {
if (outQueue.isEmpty()) {
while (!inQueue.isEmpty()) {
outQueue.add(inQueue.pop());
}
}
// 더이상 pop할 것이 없다면, null 또는 exception 발생할것을 feature로 정의하는지 검토
if (outQueue.isEmpty()) {
// throw new NoSuchElementException("값이 없습니다.");
return null;
}
else {
return outQueue.pop();
}
}
}
}
검증
Stack은 FILO(선입후출) 구조이므로, FILO를 2번 실행하면 FIFO(선입선출)을 구현할 수 있음.
q.inQueue(1)
| | | |
| | | |
|1| | |
--- ---
q.inQueue(2)
| | | |
|2| | |
|1| | |
--- ---
q.deQueue() : 2번째 큐가 비었으면, 채워넣고 1개 pop
| | | |
| | | |
|1| |2|
--- ---
| | | |
| | |1|
| | |2|
--- ---
| | | |
| | | | ----> 1 pop
| | |2|
--- ---
q.inQueue(3)
| | | |
| | | |
|1| | |
--- ---
q.deQueue() : 2번째 큐가 안 비었으면, 그냥 1개 pop
| | | |
| | | |
|3| | | ----> 2 pop
--- ---
q.deQueue() : 2번째 큐가 비었으면, 채워넣고 1개 pop
| | | |
| | | |
| | |3|
--- ---
| | | |
| | | |
| | | | ----> 3 pop
--- ---
