개요

Last in First out (LIFO)

후입선출 스택하면 가장 먼저 떠올라야 하는 개념이다 Stack은 바구니에 차곡차곡 쌓아서 꺼내쓰는 데이터 형태를 생각하면 된다.

이러한 Stacking Tower를 어릴적에 갖고 놀았던 기억이 있는 사람이 있을 수 있다.

Stack은 이러한 형태를 띄는 데이터 구조이다.

동작

Stack의 데이터를 입력하는것을 PUSH, 데이터를 가져오는것을 POP이라고 한다.

Stack은 배열같은 다른 데이터들과 다르게 중간의 데이터만 쏙 가져오는것이 불가능하다.

무조건 입력의 역순으로 한개씩 데이터를 가지고 나와야만 한다.

예를들어 12345순으로 5개의 데이터가 들어갔다면 데이터의 출력은 54321 순서로 가능하다.

Stack의 동작

• push: 스택 맨뒤에 데이터를 추가한다.
• pop: 스택 맨 뒤 항목을 반환하는 동시에 제거한다.
• top/peek: 맨 뒤의 데이터를 조회한다.
• empty: 스택이 비어있는지 조회한다.
• size: 스택 크기를 확인한다.

Swift Code

struct Stack<T>{
    var stack:[T] = []
    
    public var count: Int {
        return stack.count
    }
    
    public var isEmpty: Bool{
        return stack.isEmpty
    }
    
    public mutating func push(_ data: T){
        stack.append(data)
    }
    
    //pop하는 값이 없을 수 도 있음, 옵셔널 타입으로 반환
    public mutating func pop() -> T?{
        return isEmpty ? nil : stack.popLast()
    }
    
    public func peek() -> T{
    	return stack.last()
    }
    
    public func peek() -> T?{
        return stack.last
    }
    
    public func size() -> Int{
        return stack.count
    }
    
}

그리고 Swift에서는 직접적으로는 Stack을 제공하지는 않지만 배열의 마지막 요소를 삭제하는 부분에서는 .popLast() 라는 기능과 키워드를 사용하는것으로 보아 간접적으로라도 배열을 이용해서 stack을 이용하라는 애플의 의도가 보인다.

push는 .append(), pop은 .popLast()프로퍼티를 이용하는 형태로 구현가능하다.

활용

1. 재귀 알고리즘
2. 웹사이트의 뒤로가기
3. 애플리케이션의 실행취소기능 (undo)

등등 다양한 곳에서 사용된다.