ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 큐 2개로 스택 구현하기 with Kotlin
    Tech/Algorithm 2023. 10. 15. 15:21
    반응형

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

    반응형

    '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
Designed by Tistory.