[알고리즘] 스택이란?

💡스택(Stack)

데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(FILO)방식

즉, 마지막으로 넣었던 값이 가장 먼저 뽑히는 구조

• 탑 : 가장 나중에 추가된 항목의 위치
• 베이스: 남아 있는 항목 중에서 가장 먼저 추가된 항목의 위치

 

스택의 장단점

- 장점
구조가 단순해서 구현이 쉽다.
데이터의 삽입과 삭제가 빠르다.

- 단점
맨 위의 원소만 접근 가능하다.
탐색을 하려면 원소를 하나하나 꺼내서 옮겨가면서 해야한다. O(n)

✌🏻 스택의 주요 메소드

스택에는 자주 사용되는 메소드 (method)가 존재한다.

add, push

스택에 값을 넣기 위해서는 add 또는 push를 사용하기도 한다. 두 함수는 모두 스택에 값을 넣을 때 사용하며, 새로 넣은 값은 가장 마지막에 위치한다.
맨 위에 값을 삽입하므로 O(1)

peek

peek는 다음에 나올 값을 확인하는 메서드이다. 하지만 스택은 후입선출의 원리로 구성되어있다. 따라서 가장 마지막에 위치한 값을 호출하게 된다. 마찬가지로 단순하게 호출만 하기 때문에 값이 제거되지 않는다.
마지막 값만 확인하면 되므로 O(1)

pop

pop은 큐의 poll과 같다. 값을 호출하는 동시에 제거하게 된다.  peek을 했을 경우, 가장 뒤에 위치한 값이 사라지지 않지만 pop 이후에는 값이 사라진다. 따라서 필요에 따라 peek과 pop을 적절하게 활용해야 한다.
마지막 값만 삭제하면 되므로 O(1)

size

size는 모든 자료구조와 마찬가지로 크기를 반환하는 메서드이다. 반환 값은 int 형태를 띄게되며, 스택이 비게되면 0을 반환한다.

clear

clear 역시 익숙한 메서드이다. 생성된 스택을 한번에 비우는 메서드로, 스택 자체가 사라지는 것은 아니다.

isEmpty

isEmpty는 스택이 모두 비었는지를 확인하는 메서드이다. 반환값은 boolean 형태로 주로 while과 함께 사용된다.

⏰ 스택 시간복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색: O(n)

삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가진다.
하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.

사용 예시 (Kotlin)

import java.util.*

fun main(args:Array<String>){
    var s = Stack<Int>()

    s.push(1) // 객체를 스택에 추가
    s.push(3)

    s.peek() // 맨 위의 객체 반환 (비어 있는 상태이면 EmptyStackException 발생)
    println(s)

    s.pop() // 맨 위의 객체 삭제하고 반환 (비어 있는 상태이면 EmptyStackException 발생)
    println(s)
}