[자료구조] 스택(Stack)이란?

스택이란?

• 스택은 프로그래밍에서 자주 쓰이는 자료구조 중 하나이다.
• 이름에서 알 수 있듯이 데이터를 쌓으며 사용하는 자료구조이다.

스택의 특징

• 스택은 나중에 넣은 값이 가장 먼저 나온다는 후입선출(LIFO, Last-In-First-Out) 형식의 선형 자료구조이다.
• 스택은 데이터를 한쪽으로만 넣을 수 있으며, 중간에 있는 데이터를 삭제할 수는 없다.
• 배열, 또는 연결리스트로 구현이 되어 구현하기 쉽다.
• 스택은 한정된 용량을 갖고있어, 저장 용량보다 초과하여 데이터를 저장할 경우 스택 오버플로우(Stack Overflow)가 발생한다.
• 함수 호출, 오류 발생 시 디버깅 역추적(Traceback) 할 때 도움을 준다.
• 스택의 연산은 삽입, 삭제, 읽기로 이루어진다.

시간복잡도

1. 삽입(Push)
   • 스택의 최상단에 요소를 추가하는 연산이다.
   • 따라서 시간복잡도는 O(1)이다.
2. 삭제(Pop)
   • 스택의 최상단에 있는 요소를 삭제하는 연산이다.
   • 따라서 시간복잡도는 O(1)이다.
3. 읽기(Peek)
   • 스택의 최상단에 있는 요소를 읽는 연산이다.
   • 따라서 시간복잡도는 O(1)이다.
4. 검색(Search)
   
   • 스택에 원하는 데이터가 있는지 순회한다.
   • 따라서 시간복잡도는 O(n)이다.

장단점

1. 장점
   • 간단한 구조로 기본적인 연산의 속도가 O(1)로 빠르다.
   • 프로그램에서 함수 호출을 관리하기 용이하며 재귀함수를 처리할때도 좋다.
   • 데이터를 역순으로 뒤집을 수 있으며, 뒤로가기 등의 동작을 구현하는데 좋다.
2. 단점
   • 적절한 용량을 정하지 못하면 메모리 낭비 or 스택 오버플로우가 발생하게 된다.
   • 중간에 있는 데이터에 접근하기 어렵다.

예제

class Stack(length: Int) {
    private val size: Int
    private var index = -1
    private var arr = emptyArray<Int>()

    init {
        size = length
        arr = Array(size) { 0 }
    }

    fun push(element: Int) {
        if(index == size - 1) {
            println("배열이 꽉 차 더 삽입을 할 수 없습니다.")
            return
        }

        index += 1
        arr[index] = element
        println("Stack Push Element : $element")
    }

    fun peek(): Int {
        return if(index == -1) {
            println("배열이 비어있습니다.")
            -1
        } else {
            arr[index]
        }
    }

    fun pop(): Int {
        return if(index == -1) {
            println("배열이 비어있습니다.")
            -1
        } else {
            index -= 1
            println("Stack Pop Element : ${arr[index + 1]}")
            arr[index + 1]
        }
    }

    fun search(element: Int): Boolean {
        var isExist = false
        if(index == -1) {
            println("배열이 비어있습니다.")
            return isExist
        }

        for (i in 0 until index) {
            if(arr[index - i] == element) {
                isExist = true
                break
            }
        }

        return isExist
    }
}

fun main() {
    var stack = Stack(5)

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)
    stack.push(6)

    stack.pop()
    stack.pop()

    println("Stack Peek : " + stack.peek())
    println("Stack Search 3 : " + stack.search(3))

    stack.pop()
    stack.pop()
    stack.pop()
    stack.pop()
}