-
[알고리즘/Stack/Queue] Stack으로 Queue 구현, Queue로 Stack 구현Mhwan's Study/Algorithms 2021. 1. 6. 02:08
스택 2개로 큐를 만들 수 있고, 큐 2개로 스택을 만들 수 있다. 개인적으로 이 알고리즘을 처음 알았을 때 참신함에 소름이 돋았던 기억이 난다.
스택은 LIFO형태이고, 큐는 FIFO형태 이므로 들어오고 나갈때 저장된 순서를 뒤집을 수 있다면 스택으로 큐를 구현할 수 있고, 큐로 스택을 구현할 수 있다. 그래서 2개가 필요한것이다.
# Stack으로 Queue 구현 (뺄때 다른 스택으로 옮겨서 빼자!)
두개의 스택인 A, B 스택이 있다.
- enQueue : A스택에 push
- deQueue : B 스택에 남은게 있다면 B에 있는 것을 pop하고, 남은게 없다면 A스택에 있는 것을 모두 pop해서 B로 push하고 B에 있는 것을 pop한다.
123456789101112131415161718192021public class Queue {Stack<Integer> stackA;Stack<Integer> stackB;public Queue(){stackA = new Stack<>();stackB = new Stack<>();}public void enQueue(int v) {stackA.push(v);}public int deQueue() {if (stackB.isEmpty()) {while (!stackA.isEmpty()) {stackB.push(stackA.pop());}}return stackB.pop();}}cs # Queue로 Stack 구현 (넣어줄 때 순서를 바꿔서 넣자)
2개의 큐 Main, sub 큐가 있다.
- push : Main큐에 데이터가 있다면 Main큐에 있는 것을 모두 deQueue해서 sub큐로 넣는다. 그 후 main큐에 삽입하려는 데이터를 삽입하고, sub큐로 옮겨 놓은 것을 모두 deQueue해서 main큐로 넣어준다.
- pop : main큐에 있는 것을 dequeue해준다
12345678910111213141516171819202122232425public class Stack {LinkedList<Integer> mainQueue;LinkedList<Integer> subQueue;public Stack(){mainQueue = new LinkedList<>();subQueue = new LinkedList<>();}public void push(int v) {if (mainQueue.isEmpty()) {mainQueue.offer(v);} else {while (!mainQueue.isEmpty()) {subQueue.offer(mainQueue.poll());}mainQueue.offer(v);while (!subQueue.isEmpty()) {mainQueue.offer(subQueue.poll());}}}public int pop() {return mainQueue.poll();}}cs 'Mhwan's Study > Algorithms' 카테고리의 다른 글
[알고리즘/다익스트라] 다익스트라(Dijkstra) 알고리즘 (0) 2021.01.15 [알고리즘/투 포인터] 2020 카카오 인턴십 - 보석 쇼핑 (0) 2021.01.06 [알고리즘/투포인터] 투포인터 알고리즘 (0) 2021.01.06 [알고리즘/Stack] 유효한 괄호가 있는지 판별 (0) 2021.01.06 [알고리즘/Stack] 후위표기식으로 변환 및 계산 (0) 2021.01.06