[자료구조] 스택 ( Stack )

개요

 

하나하나 쌓아올리는 자료구조 입니다.

스택의 가장 큰 특징은 후입선출( LIFO, Last-In-First-Out ) 이며, 마지막으로 들어온 데이터가 먼저 나간다는 의미입니다.

배열을 움직일 필요가 없어서 오버헤드가 발생하지 않습니다.

 

데이터는 마지막에 추가되므로,

데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.

 

데이터는 마지막에서 제거되므로,

데이터의 제거는 O(1) 의 시간복잡도를 갖습니다.

 

 

Stack 을 이해하기 쉽게 그림으로 나타내면 아래와 같습니다.

스택_001

아래 그림과 같이 동작하게 됩니다.

Top	Stack 의 상단 데이터입니다. 제일 마지막에 들어온 데이터입니다.
Push	Stack 에 데이터를 추가합니다. 마지막으로 Push 한 데이터가 Top 입니다.
Pop	Stack 에서 데이터를 제외시킵니다. 그 후 Stack 의 마지막 데이터가 Top 입니다.

 

스택_002

 

 

---

구현

 

Stack 은 Swift 를 사용하여 아래와 같이 구현하며, 아래와 같이 사용할 수 있습니다.

// MARK: Stack 구현
struct Stack<T> {
    private var stack: [T] = []
    
    public var count: Int {
        // Stack 의 길이를 반환합니다.
        return stack.count
    }
    
    public var isEmpty: Bool {
        // Stack 이 비어있는지 true/ false 를 반환합니다.
        return stack.isEmpty
    }
    
    public mutating func push(_ element: T) {
        // Stack 에 데이터를 추가합니다.
        stack.append(element)
    }
    
    public mutating func pop() -> T? {
        // Stack 에서 데이터를 제거합니다.
        return isEmpty ? nil : stack.popLast()
    }
    
    public mutating func top() ->T? {
        // Stack 의 Top 데이터를 확인합니다.
        return stack.last
    }
}

var mStack = Stack<Int>()

mStack.push(10) // 데이터 추가
mStack.isEmpty  // 비어있는지 확인
mStack.top()    // Top 확인
mStack.count    // 길이 확인
mStack.pop()    // 데이터 제거
mStack.isEmpty  // 비어있는지 확인

 

위와 같이 구현해서 사용해도 상관은 없지만 굳이 구현하지 않아도 배열을 Stack 처럼 사용할 수 있습니다.

 

P.S

추가적으로 생각나거나 찾은 내용은 날짜를 덧붙여 업데이트 하겠습니다.