[Backend] 데이터 구조 (Stack)

출처 : GeeksforGeeks

Stack

package org.example.Stack

class Stack() {
    private var top: Int = -1
    private var capacity: Int = DEFAULT_CAPACITY
    private var data: Array<Int?> = arrayOfNulls(capacity)

    companion object {
        private const val DEFAULT_CAPACITY = 10
    }

    fun isFull(): Boolean = top == capacity-1

    fun isEmpty(): Boolean = top == -1

    fun size(): Int = top + 1

    fun push(element: Int) {
        if (isFull()) {
            increaseCapacity()
        }
        data[++top] = element // top을 먼저 증가시킨 후 값을 넣음
    }

    fun pop(): Int {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty.")
        }
        val element = data[top]!!
        data[top--] = null
        return element
    }

    fun peek(): Int {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty.")
        }
        return data[top]!! // top 인덱스의 값을 가져옴
    }

    fun clear() {
        for(i in 0 until top) {
            data[i] = null
        }
        top = -1 // top을 초기 상태인 -1로 되돌림
    }

    fun increaseCapacity(){
        capacity *= 2
        data = data.copyOf(capacity)
    }
}

 

결과

fun main() {
    val intStack: Stack = Stack()

    println("1. Data addition")
    println("Initial size : ${intStack.size()}")
    intStack.push(1)
    intStack.push(2)
    intStack.push(3)

    println("Updated size : ${intStack.size()}")
    println("Peek element : ${intStack.peek()}")

    println("\n2. Data removal")
    println("Removed element : ${intStack.pop()}")
    println("Decreased size : ${intStack.size()}")

    println("\n3. Check capacity is increased")
    for (i in 4 .. 100) {
        intStack.push(i)
    }
    println("Current size : ${intStack.size()}")

    println("\n4. Check stack is empty")
    intStack.clear()

    try {
        intStack.pop()
    } catch (_: NoSuchElementException) {
        println("Error Check: Stack is empty")
    }
}

/*
1. Data addition
Initial size : 0
Updated size : 3
Peek element : 3

2. Data removal
Removed element : 3
Decreased size : 2

3. Check capacity is increased
Current size : 99

4. Check stack is empty
Error Check: Stack is empty
*/

---

Stack (in Generic<T>)

package org.example.Stack

class GenericStack<T>{
    private var top: Int = -1
    private var capacity: Int = DEFAULT_CAPACITY
    @Suppress("Unchecked_cast")
    private var data: Array<T?> = arrayOfNulls<Any?>(capacity) as Array<T?>

    companion object {
        private const val DEFAULT_CAPACITY = 10
    }

    fun isFull(): Boolean = top == capacity-1
    fun isEmpty(): Boolean = top == -1
    fun size(): Int = top + 1

    fun push(element: T) {
        if (isFull()) {
            increaseCapacity()
        }

        data[++top] = element
    }

    fun pop(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty")
        }

        val element = data[top]!!
        data[top--] = null
        return element
    }

    fun peek(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Stack is empty")
        }

        return data[top]!!
    }

    fun clear() {
        for (i in 0 .. top) {
            data[i] = null
        }

        top = -1
    }

    fun increaseCapacity(){
        capacity *= 2
        data = data.copyOf(capacity)
    }
}

 

---

Powered By. ChatGPT & Gemini