[자료구조] Stack

Swift에서 Stack을 구현하고 싶다면 배열을 사용해서 구현할 수 있다.

 

 

Stack이란?

c

b

a

위와 같은 스택 구조가 있다면 a -> b -> c 순으로 스택에 들어갔을 것이고 나올 때는 c -> b -> a 순서로 나오게 된다.

즉, 스택은 FILO 구조이다.

 

구조의 마지막에 추가/삭제 되기 때문에 시간 복잡도는 O(1)를 갖게 되며 그러므로 오버헤드는 발생하지 않는다.

 

Stack 구현

아래와 같이 구조체와 배열을 사용해서 스택을 구현할 수 있다.

struct Stack<T> {
    private var stack: [T] = []
    
    public var count: Int {
        return stack.count
    }
    
    public var isEmpty: Bool {
        return stack.isEmpty
    }
    
    public mutating func push(_ element: T) {
        stack.append(element)
    }
    
    public mutating func pop() -> T? {
        return isEmpty ? nil : stack.popLast()
    }
}

 

그리고 실제 사용을 할 때는 아래와 같이 사용하면 된다.

var stack = Stack<Int>()
stack.push(3)
stack.push(2)
// 3, 2
stack.pop()
// 3

 

그러나, 위의 코드를 보면 알 수 있는 것처럼 스택의 경우 위의 구조체/배열을 통해서 사용할 수도 있지만, 배열을 스택처럼 사용해도 된다. 

즉, Swift에서는 굳이 Stack을 만들어서 사용하지 않아도 append() popLast() 메서드 등을 통해서 충분히 배열을 스택처럼 사용할 수 있다.