두 개의 스택을 이용해 큐를 만드는 문제. 인풋값을 다루는 메인함수는 주어져 있고 큐만 만들면 된다. 큐에 필요한 스택 변수와 함수도 얼개는 만들어져있는 상태에서 구현만 하면 된다.
제약조건은 인풋값과 관련된 것 외에는 특별히 신경써야 할 것은 없는 것 같다.
스택과 큐를 간단히 정리하면,
스택(Stack):
- Last-In-First-Out(LIFO) 후입선출
- push: 스택에 값을 넣는다.
- pop: 스택의 맨 앞에서 값을 하나 가져온다. 가져온 값은 스택에서 제거된다. (꺼낸다)
- peek: 스택의 맨 앞에서 값을 하나 가져온다. 가져온 값은 스택에서 제거되지 않는다.
큐(Queue):
- First-In-First-Out(FIFO) 선입선출
- enqueue: 큐의 끝에 값을 넣는다.
- dequeue: 큐의 맨 앞에서 값을 하나 가져온다. 가져온 값은 큐에서 제거된다. (꺼낸다)
- peek: 큐의 맨 앞에서 값을 하나 가져온다. 가져온 값은 큐에서 제거되지 않는다.
다음과 같이 스택 두개를 이용해 하나의 큐를 만들었다.
| import java.io.*; | |
| import java.util.*; | |
| import java.text.*; | |
| import java.math.*; | |
| import java.util.regex.*; | |
| public class Solution { | |
| public static class MyQueue<T> { | |
| Stack<T> stackNewestOnTop = new Stack<T>(); | |
| Stack<T> stackOldestOnTop = new Stack<T>(); | |
| public void enqueue(T value) { // Push onto newest stack | |
| stackNewestOnTop.push(value); | |
| } | |
| public T peek() { | |
| if(stackOldestOnTop.empty()) { | |
| while (!stackNewestOnTop.empty()) { | |
| stackOldestOnTop.push(stackNewestOnTop.pop()); | |
| } | |
| } | |
| return stackOldestOnTop.peek(); | |
| } | |
| public T dequeue() { | |
| if(stackOldestOnTop.empty()) { | |
| while (!stackNewestOnTop.empty()) { | |
| stackOldestOnTop.push(stackNewestOnTop.pop()); | |
| } | |
| } | |
| return stackOldestOnTop.pop(); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| MyQueue<Integer> queue = new MyQueue<Integer>(); | |
| Scanner scan = new Scanner(System.in); | |
| int n = scan.nextInt(); | |
| for (int i = 0; i < n; i++) { | |
| int operation = scan.nextInt(); | |
| if (operation == 1) { // enqueue | |
| queue.enqueue(scan.nextInt()); | |
| } else if (operation == 2) { // dequeue | |
| queue.dequeue(); | |
| } else if (operation == 3) { // print/peek | |
| System.out.println(queue.peek()); | |
| } | |
| } | |
| scan.close(); | |
| } | |
| } | |
스택 두 개 중 하나는 선입된 값이 가장 위(stackOldestOnTop, 출구스택)에 있도록 하고 다른 하나는 후입된 값이 가장 위(stackNewestOnTop, 입구스택)에 있도록 한다. enqueue시에는 입구스택에 스택의 push를 활용하여 값을 쌓고 dequeue시에는 출구스택에서 값을 빼 낸다. 출구스택에 값이 없을 땐 입구스택에서 값을 모두 가져와서 출구스택에 push한 뒤 출구스택의 맨 앞에서 값을 빼낸다. peek도 dequeue와 같은 방식으로 만들되 출구스택에서 값을 빼지(pop)않고 peek 한다.
예를들어, 큐에 1, 2, 3 을 순서대로 넣는다고 가정하면, 1-2-3 이 enqueue 될 때는 입구스택에 값을 쌓기 때문에 입구스택에 3|2|1] 이런 식으로 쌓이게 된다. 여기서 dequeue를 하려면 (1부터 빼내려면) 입구스택에 있는 모든 값을 출구스택으로 옮겨야 한다. 옮기는 과정에서 입구스택에서 값을 빼낼 땐 3-2-1의 순서대로 값이 빠지게 되고 빠지는 순서 그대로 다시 출구스택에 push하면 1|2|3] 이런식으로 값이 쌓이게 될 것이다. 이렇게 모두 옮기고 난 후 출구스택의 맨 앞 값을 빼내면 1이 빠진다. (dequeue)
한번 풀게 되면 스택과 큐의 특성을 둘 다 자연스럽게 익히게 되는 괜찮은 문제인 것 같다.
