스택? 스택 만들어보기

스택은 데이터를 일시적으로 저장하기 위한 자료구조이다. 

데이터의 입력과 출력 순서는 후입선출(LIFO구조)이다.

스택에서 데이터를 꺼내는 작업을 팝(pop), 데이터를 넣는 구조를 푸시(push)라고 한다.

 

 

간단하게 만들어보자

data class Stack(
    private var max: Int = 0, // 스택용량
    private var ptr: Int = 0, // 쌓여있는 데이터 수
    private var stk: IntArray = intArrayOf()// 스택배열
) {

    fun create(capacity: Int) {
        this.ptr = 0
        this.max = capacity
        try {
            this.stk = IntArray(max)
        } catch (e : OutOfMemoryError) {
            this.max = 0
        }
    }

    // 데이터 푸시
    fun push(x: Int): Int {
        if (ptr >= max)
            throw OverflowIntStackException()

        return x.also {
            stk[ptr++] = it
        }
    }

    // 데이터 팝
    fun pop() {
        if (ptr <= 0)
            throw EmptyIntStackException()

        stk[--ptr] = 0
    }

    // 스택의 마지막 데이터 보기
    fun peek(): Int {
        if (ptr <= 0)
            throw EmptyIntStackException()

        return stk[ptr - 1]
    }

    // 스택의 요소 찾기
    fun indexOf(x: Int): Int {
        for (i in 0 until ptr) {
            if (stk[i] == x) {
                return i
            }
        }

        return -1
    }

    // 스택 비우기
    fun clear() {
        ptr = 0

        for (i in stk.indices) {
            stk[i] = 0
        }
    }

    // 스택의 용량 반환
    fun capacity(): Int {
        return max
    }

    // 현재 스택이 차여있는 갯수
    fun size(): Int {
        return ptr
    }

    // 스택이 비어있는지 확인
    fun isEmpty(): Boolean {
        return ptr <= 0
    }

    // 스택이 가득찼는지
    fun isFull(): Boolean {
        return ptr >= max
    }

    // 스택 데이터 출력
    fun dump() {
        if (ptr <= 0) {
            println("stack is empty")
        } else {
            for (i in 0 until ptr) {
                print("${stk[i]}, ")
            }
            println()
        }
    }

    class EmptyIntStackException : RuntimeException()
    class OverflowIntStackException : RuntimeException()

}

fun main() {
    val test = Stack().apply {
        create(10)
    }
    println("배열 생성: $test")

    test.push(1)
    test.push(77)
    test.push(80)
    test.push(1489)
    test.push(200)
    test.push(59384)

    println("test element: $test")

    test.pop()
    test.pop()
    println("pop: $test")

    println("peak: ${test.peek()}")
    println("indexOf: ${test.indexOf(200)}")
    println("capacity: ${test.capacity()}")
    println("size: ${test.size()}")
    println("empty: ${test.isEmpty()}")
    println("full: ${test.isFull()}")

    test.dump()
    test.clear()
    println("test element: $test")
}