-
큐 2개로 스택 구현하기 with KotlinTech/Algorithm 2023. 10. 15. 15:21반응형
'2개의 큐로 스택을 어떻게 구현할 수 있을까?'에 대한 내용입니다. 큐(Queue)와 스택(Stack)은 프로그래밍에서 자주 사용되는 자료 구조로, 각각 First-In-First-Out(FIFO)과 Last-In-First-Out(LIFO)의 특성을 가지고 있습니다. 이 두 자료 구조의 동작 방식이 다르기 때문에, 하나를 이용해 다른 하나를 구현하는 것은 꽤 재미있는 문제로 다가옵니다.
기본 원리
스택을 구현하기 위해 큐 2개를 사용하는 기본 원리는 다음과 같습니다:
- 원소를 스택에 '푸시'하기 위해서는, 큐 A를 이용합니다.
- 원소를 스택에서 '팝'하거나 '피크'하기 위해서는, 큐 B를 이용하여 큐 A의 원소를 하나 빼고, 나머지 원소들을 큐 B로 이동시킨 뒤, A와 B의 역할을 바꾸어 팝/피크 연산을 수행합니다.
코틀린 코드 예시
아래는 2개의 큐를 이용해 스택을 구현하는 간단한 코틀린 코드입니다
import java.util.LinkedList import java.util.Queue class StackUsingQueues { private var queueA: Queue<Int> = LinkedList() private var queueB: Queue<Int> = LinkedList() fun push(item: Int) { queueA.offer(item) } fun pop(): Int { if (isEmpty()) throw EmptyStackException() while (queueA.size > 1) { queueB.offer(queueA.poll()) } val poppedItem = queueA.poll() swapQueues() return poppedItem } fun peek(): Int { if (isEmpty()) throw EmptyStackException() while (queueA.size > 1) { queueB.offer(queueA.poll()) } val itemToPeek = queueA.peek() queueB.offer(queueA.poll()) swapQueues() return itemToPeek } private fun swapQueues() { val temp = queueA queueA = queueB queueB = temp } fun isEmpty(): Boolean = queueA.isEmpty() } class EmptyStackException : RuntimeException("Stack is empty.")
사용 예시:
fun main() { val stack = StackUsingQueues() stack.push(1) stack.push(2) stack.push(3) println(stack.pop()) // 3 println(stack.peek()) // 2 stack.push(4) println(stack.pop()) // 4 }
마무리
이 글을 통해 2개의 큐를 사용하여 스택을 구현하는 방법에 대해 알아보았습니다. 물론, 이 방법은 효율적이지 않을 수 있습니다만, 다른 자료 구조를 이용하여 어떻게 다른 자료 구조를 흉내낼 수 있는지에 대한 재미있는 접근 방법을 제공합니다. 이해에 도움이 되셨길 바랍니다!
반응형'Tech > Algorithm' 카테고리의 다른 글
문자열 뒤집기 (0) 2023.10.29 배열을 오른쪽으로 N번 회전하기 (0) 2023.10.15 두 개의 스택을 사용하여 큐 구현하기 (1) 2023.10.15 중괄호 짝 맞추기 문제 풀이 (0) 2023.10.15 List and Stack (0) 2018.10.20