[Data Structure] 스택 (Stack)

안녕하세요!

오늘은 Stack에 대해서 포스팅해보려고 합니다!

 

 

1. Stack이란?

Stack은 값을 한쪽 끝에서만 추가하거나 삭제할 수 있는 것으로, LIFO (Last-In-First-Out) 구조입니다.

새로운 원소를 아래부터 차례대로 하나씩 쌓는 것으로, 원소를 지울 때에는 제일 위에 있는 원소가 제일 먼저 지워집니다.

그렇기 때문에 가장 나중에 들어온 원소가 먼저 나가겠죠? 그래서 Stack은 LIFO 구조입니다.

제일 위에 있는 원소를 top element, 제일 아래에 있는 원소를 bottom element라고 합니다. 

즉, Stack은 top의 위치에서만 원소의 삽입과 제거가 이루어지는 순차화된 리스트입니다.

 

a0: bottom element, a3: top element

 

Stack이 뭔지 알아봤으니, 이제 Stack의 성질에 대해서 알아보도록 할게요!

Stack에 원소를 추가하거나 삭제하는 것은 한쪽 끝에서만 가능하다고 했죠? 

그렇기 때문에 원소의 추가/제거의 시간복잡도는 O(1)입니다.

Stack의 제일 위에 있는 원소를 확인할 때의 시간복잡도도 O(1)입니다. 제일 위의 원소만 확인하면 되는 것이기 때문이죠!

그리고 Stack의 제일 위에 있는 원소를 제외한 나머지 원소들은 확인하거나 변경하는 것이 불가능합니다.

 

 

 

2. Stack 구현해보기

 

Stack을 구현하는 코드는 다음과 같습니다.

 

struct Stack<T> {
    private var stack: [T] = []
    
    // stack이 비어있는지 여부 확인
    var isEmpty: Bool {
        return stack.isEmpty
    }
    
    // stack의 제일 위의 원소 확인
    var top: T? {
        return stack.last
    }
    
    // stack의 원소 갯수
    var count: Int {
        return stack.count
    }
    
    // stack에 원소 추가
    mutating func push(_ element: T) {
        stack.append(element)
    }
    
    // stack의 마지막 원소 빼기
    mutating func pop() -> T? {
        return stack.popLast()
    }
}

 

다양한 자료형으로 사용하기 위해 Generic 으로 선언하였습니다.

그리고 stack이란 배열에 스택을 만들어서 사용하면 된답니다!

 

var myStack = Stack<Int>()

myStack.push(0)
myStack.push(1)
myStack.push(2)
myStack.push(3)

print(myStack) // Stack<Int>(stack: [0, 1, 2, 3])
print("top:", myStack.top) // 3
print("stack size:", myStack.count) // 4

myStack.pop() // 제일 위의 원소인 3을 pop

print("top:", myStack.top) // 2

myStack.pop() // 제일 위의 원소인 3을 pop
myStack.pop() // 제일 위의 원소인 2를 pop
myStack.pop() // 제일 위의 원소인 1을 pop

print("isEmpty:", myStack.isEmpty) // true
print("top:", myStack.top) // nil

 

 

실제로 사용을 해보면 아래와 같이 결과도 확인할 수 있습니다.