두 개의 스택을 사용하여 큐 구현하기

스택과 큐의 기본 개념

스택 (Stack)

스택은 데이터를 후입선출(LIFO: Last-In-First-Out) 방식으로 저장하는 자료 구조입니다. 즉, 가장 나중에 들어간 데이터가 가장 먼저 나오게 됩니다.

큐 (Queue)

반면에 큐는 선입선출(FIFO: First-In-First-Out) 방식으로 데이터를 저장합니다. 처음 들어간 데이터가 가장 먼저 나오게 되죠.

스택 두 개로 큐를 만들기

스택 두 개를 사용하여 큐의 동작을 구현할 수 있습니다. 기본 알고리즘은 다음과 같습니다:

• Enqueue (데이터 추가): 첫 번째 스택을 사용하여 데이터를 추가합니다.
• Dequeue (데이터 제거): 만약 두 번째 스택이 비어 있다면, 첫 번째 스택의 모든 요소를 두 번째 스택으로 옮긴 후, 두 번째 스택에서 데이터를 제거합니다. 만약 두 번째 스택에 데이터가 있으면, 그냥 두 번째 스택에서 데이터를 제거합니다.

코틀린 구현 예제

아래는 코틀린으로 위 알고리즘을 구현한 코드 예제입니다

import java.util.*

class QueueUsingStacks<T> {
    private val stack1: Stack<T> = Stack()
    private val stack2: Stack<T> = Stack()

    fun enqueue(item: T) {
        stack1.push(item)
    }

    fun dequeue(): T {
        if (stack2.isEmpty()) {
            while (stack1.isNotEmpty()) {
                stack2.push(stack1.pop())
            }
        }
        if (stack2.isEmpty()) {
            throw EmptyStackException()
        }
        return stack2.pop()
    }
}

fun main() {
    val queue = QueueUsingStacks<Int>()

    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)

    println(queue.dequeue())  // 출력: 1
    println(queue.dequeue())  // 출력: 2

    queue.enqueue(4)

    println(queue.dequeue())  // 출력: 3
    println(queue.dequeue())  // 출력: 4
}

결론

스택과 큐는 프로그래밍에서 굉장히 기본적이면서도, 다양한 문제 해결에 활용되는 자료 구조입니다. 이런 기본적인 자료 구조를 어떻게 다루는지 이해하고, 다양한 방식으로 활용할 수 있는 능력은 문제 해결 능력 향상에 큰 도움이 됩니다.

위에서 소개한 방법 외에도 자료 구조를 활용한 다양한 문제 해결 전략들이 존재합니다. 자료 구조와 알고리즘은 프로그래밍의 기본이자 핵심이므로, 계속해서 연습하고 탐구해 나가는 것이 중요합니다.

기대하실 바, 이 포스트가 스택과 큐, 그리고 두 스택을 이용한 큐의 구현에 대한 기본적인 이해를 돕는 데에 도움이 되었길 바랍니다.