Stack

Stack

한 쪽 끝에서만 입출력이 가능한 자료구조

Last In First Out 구조다

 

push x

index
3
2
1	top
0	x

pop 

index
3
2	top
1	13
0	12

index
3
2
1	top
0	12

 

동작에 따른 시간 복잡도

• 원소 추가 / 제거 O(1)
• 제일 상단 원소 확인 O(1)

제일 상단이 아닌 나머지 원소들의 확인 / 변경은 원칙적으로 불가능하다

구현

배열, 연결리스트로 구현이 가능하다 

[구성] 

• 원소들을 담을 배열 
• 다음 원소가 삽입될 위치의 인덱스 값

push  :  배열 사이즈를 넘어가지 않도록 유의

data[top++] = x

 

pop : 원소가 하나도 없을 때 호출하지 않도록 한다

top--

 

top : pop과 마찬가지로 원소가 하나도 없을 때 호출하지 않도록 한다

data[top-1]

 

BOJ

10828. 스택

class Stack (private val size: Int) {
    private val data = Array<Int?>(size) { null }
    private var top = 0

    fun push(x: Int) {
        if (top != size) {
            data[top++] = x
        }
    }

    fun pop(): Int {
        return if (top != 0) {
            data[(top--)-1]!!
        } else -1
    }

    fun size(): Int {
        return top
    }

    fun empty(): Int {
        return if(top == 0) 1 else 0
    }

    fun top(): Int {
        return if (top != 0) {
            data[top-1]!!
        } else -1
    }
}

10773. 제로

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var answer = 0
    val k = readLine().toInt()
    val stack = Stack<Int>()

    for (i in 1..k) {
        when (val number = readLine().toInt()) {
            0 -> {
                stack.pop()
            }
            else -> {
                stack.push(number)
            }
        }
    }

    for (i in stack.indices) {
        answer += stack.pop()
    }

    print(answer)
}

 

kotlin 에서의 Stack

코틀린에서는 Stack을 제공하지 않기 때문에 improt.java.util.Stack을 사용하도록 한다

pop(), push(), peek() 등의 함수 제공

 

참고

https://youtu.be/0DsyCXIN7Wg