큐 2개로 스택 구현하기 with Kotlin

'2개의 큐로 스택을 어떻게 구현할 수 있을까?'에 대한 내용입니다. 큐(Queue)와 스택(Stack)은 프로그래밍에서 자주 사용되는 자료 구조로, 각각 First-In-First-Out(FIFO)과 Last-In-First-Out(LIFO)의 특성을 가지고 있습니다. 이 두 자료 구조의 동작 방식이 다르기 때문에, 하나를 이용해 다른 하나를 구현하는 것은 꽤 재미있는 문제로 다가옵니다.

기본 원리

스택을 구현하기 위해 큐 2개를 사용하는 기본 원리는 다음과 같습니다:

1. 원소를 스택에 '푸시'하기 위해서는, 큐 A를 이용합니다.
2. 원소를 스택에서 '팝'하거나 '피크'하기 위해서는, 큐 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개의 큐를 사용하여 스택을 구현하는 방법에 대해 알아보았습니다. 물론, 이 방법은 효율적이지 않을 수 있습니다만, 다른 자료 구조를 이용하여 어떻게 다른 자료 구조를 흉내낼 수 있는지에 대한 재미있는 접근 방법을 제공합니다. 이해에 도움이 되셨길 바랍니다!