[자료구조] 스택(Stack)이란 (Swift)

스택(Stack)이란

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LAST IN FIRST OUT 형식의 자료구조 입니다.

LAST IN FIRST OUT 이란 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다. 이는 먼저 들어온 데이터가 먼저 나가는 '큐' 와 가장 큰 차이점을 가집니다.

 

구현

스택은 마지막으로 들어온것이 먼저 나가는 구조입니다. 가장 최근에 스택에 추가한 항목이 가장 먼저 제거가 됩니다.

본인이 사용하는 언어로 Array 를 통해 제일 마지막으로 들어온 데이터를 출력해주는 형태로 구현이 가능합니다

이때 생성, 삽입, 삭제 시간 복잡도를 계산하면서 구현하면은 더욱더 좋습니다.

 

 

시간복잡도

데이터 삽입시 시간복잡도 :  O(1)

데이터 삭제시 시간복잡도 : O(1)

 

 

 

스택의 구현

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 testStack = Stack<Int>()
testStack.push(1) // [1]
testStack.push(2) // [1,2]
testStack.pop() // 2 반환

 

struct를 통해 구현을 해주었지만 일반 배열을 통해 popLast() or removeLast()를 사용하여 구현할수 있다

 

var testStack : [Int] = []
testStack.append(1) // [1]
testStack.append(2) // [1,2]
testStack.popLast() // 2반환

 

 

왜 사용해야할까 or 나만의 고민

스텍은 함수의 실행과 매우 유사하다 -> 재귀적인 처리를 사용해야할때 스텍 자료구조를 사용하면 매우효과적

가장 최근에 실행한 데이터를 처리하고싶을때 사용

데이터 저장 , 읽는 속도가 매우 빠르다 -> O(1)

 

 

 

 

 

참조

https://babbab2.tistory.com/85

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

https://velog.io/@kimhyo_0218/JavaScript-%EC%8A%A4%ED%83%9DStack-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0