[자료구조] 스택(Stack)

스택이란?

스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조이다.

스택은 위와 같은 형태이다.

위의 빈 공간으로 데이터가 들어오고 나갈 수 있다.

위의 사진에서 2라는 데이터를 stack에 넣고, 값을 빼내고자 할 때 2부터 값이 나오는 것을 알 수 있다.

즉, 마지막으로 들어간 값이 처음으로 나온다는 Last Input First Output(LIFO) 형태를 따른다.

구현

스택의 기능은 다음과 같다.

• push: 스택에 값을 넣는다.
• pop: 스택에서 가장 위에 있는 값을 빼내고 이를 출력한다.
• size: 스택에 들어있는 원소의 개수를 출력한다.
• empty: 스택이 비어있는지 아닌지 출력한다.
• peek 또는 top:  스택에서 가장 위에 있는 값을 출력한다.

아래 코드로 기능들을 어떻게 구현했는지 확인할 수 있다.

class Stack {
    companion object {
        const val MAX = 10000
    }

    private val arr = IntArray(MAX)
    private var top = -1

    fun push(num: Int) {
        if(top == MAX - 1) {
            println("Stack is Full")
            return
        }

        arr[++top] = num
    }

    fun pop() {
        if(top == -1) println(-1) else println(arr[top--])
    }

    fun size() {
        println(top + 1)
    }

    fun empty() {
        if(top == -1) println(1) else println(0)
    }

    fun top() {
        if(top == -1) println(-1) else println(arr[top])
    }
}

push

데이터를 넣어주는 것이므로 ++top을 한 위치에 값을 넣어준다.

만약 top이 MAX - 1과 같다면, 스택이 꽉 찬 것이므로 더 이상 값을 넣을 수 없다는 것을 처리해줘야한다.

pop

pop은 값을 꺼내면서 이 값을 보여줘야한다. 따라서 println(arr[top--])를 통해 값을 출력 후 top을 내리면서 값을 지울 수 있도록 해준다.

만약 top이 -1이라면 스택이 비어있는 것이므로 처리해줘야 한다.

size

스택에 들어가있는 데이터의 갯수를 출력해준다. 우리는 이를 top을 통해 알 수 있다.

top이 -1부터 시작하므로 top + 1한 값이 스택의 크기인 것을 알 수 있다.

empty

top이 -1이라면 비어있는 것이므로 true를 반환해주거나 상황에 맞는 처리 해주면 된다.

top이 1이 아니라면 최소 1개의 데이터가 들어있는 것이므로 상황에 맞게 처리해준다.

peek 또는 top

스택의 맨 위의 값을 보여주는 것으로 top의 값을 보여주면 된다.

pop과는 달리 값을 빼내는 것이 아니므로 출력의 기능만을 한다.