[Swift] 스택(Stack)은 프링글스.

스택은 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조이며, LIFO 원칙을 따릅니다.

 

LIFO는 Last In First Out 원칙으로,

배열에 데이터를 들어온 순서대로 넣고(Push), 가장 늦게 들어온 데이터를 먼저 꺼내는 것(Pop)을 의미합니다.

 

무슨 말이지 잘 모르겠다면…

 

이 글의 제목처럼 스택은 프링글스.를 생각하면 쉽습니다!

프링글스를 포장할 때는 아래부터 차례대로 쌓겠지만, 우리가 먹을 때는 제일 마지막에 넣은 과자를 먼저 먹겠죠!

 

이런 것을 바로 LIFO 원칙을 가진 Stack 구조로 생각하면 됩니다.

 

정리하자면!

스택은 push 연산으로 값을 차례대로 삽입하고, pop 연산으로 가장 최근에 저장된 값을 삭제하는 기본적인 자료구조를 의미합니다.

---

Swift로 Stack 구현

기본적으로 push와 pop 연산을 구현해야 하며, 추가적으로 top, isEmpty, count 연산을 구현하겠습니다.

배열 생성

// 제네릭으로 빈 배열 생성
private var datas: [T] = []

 

제네릭으로 구현된 빈 배열을 생성합니다. 이 배열은 Stack에 필요한 데이터를 저장하는 데 사용됩니다.

또한, 외부에서 직접적인 접근을 막기 위해 private로 선언해줍니다.

삽입 (push) - O(1)

// 데이터 삽입(push)
mutating func push(_ data: T) {
    datas.append(data)
}

 

배열의 삽입(push) 메서드에서는 append(_ newElement: Element) 메서드를 사용하여 데이터를 추가합니다.

이는 배열의 끝에 데이터를 덧붙이는 것으로, 대부분의 경우에는 O(1)의 시간 복잡도를 갖습니다.

 

다만, 배열의 용량(capacity)이 부족하여 새로운 저장소를 할당해야 할 때는 O(n)의 시간 복잡도가 발생할 수 있습니다.

 

배열은 일반적으로 지수 전략을 사용하여 저장 공간을 확장합니다. 이는 현재 저장 공간의 2배, 2^2배, 2^3배...와 같은 방식으로 용량을 늘립니다.

 

따라서 대부분의 상황에서 배열의 append(_:) 메서드는 평균적으로 O(1)의 시간 복잡도를 보장할 수 있습니다.

 

append(_:) | Apple Developer Documentation

삭제 (pop) - O(1)

// 데이터 삭제(pop)
mutating func pop() -> T? {
   return datas.popLast()
}

 

Swift에서 배열의 마지막 요소를 삭제하는 두 가지 메서드로 removeLast()와 popLast()를 생각해볼 수 있습니다.

 

removeLast()의 경우, 리턴 타입이 Self.Element이기 때문에 배열이 비어있을 경우 사용하면 런타임 에러가 발생할 수 있습니다.

 

그러나 popLast()의 경우 리턴 타입이 Self.Element?으로 정의되어 있어 빈 배열에서 사용해도 nil을 리턴하므로 안전하게 처리할 수 있습니다.

 

두 메서드의 시간 복잡도는 모두 O(1)이기 때문에 여기서는 popLast()를 사용하여 삭제(pop) 메서드를 구현하였습니다.

 

removeLast() | Apple Developer Documentation

popLast() | Apple Developer Documentation

조회 (count, isEmpty, top) - O(1)

// 배열에 담긴 데이터의 개수 조회
var count: Int {
    return datas.count
}

// 스택이 비어있는지 여부 조회
var isEmpty: Bool {
    return datas.isEmpty
}

// 가장 최근 데이터 조회
func top() -> T? {
    return datas.last
}

 

스택에 담긴 데이터의 개수를 나타내는 count와 스택이 비어있는지 여부를 나타내는 isEmpty는 Swift의 배열 타입에서 제공하는 count와 isEmpty 프로퍼티를 활용합니다.

 

count와 isEmpty 프로퍼티는 일반적으로 O(1)의 시간 복잡도를 가지지만, 주의해야 할 점이 있습니다.

 

만약, 해당 컬렉션 타입이 RandomAccessCollection 프로토콜을 준수하지 않는다면 count의 시간 복잡도는 O(n)이 될 수 있습니다.

 

예를 들어, Dictionary와 Set 타입은 RandomAccessCollection 프로토콜을 준수하지 않아 count의 시간 복잡도가 O(n)입니다.

우리가 사용하는 배열은 RandomAccessCollection 프로토콜을 준수하므로 count는 O(1)입니다.

 

(RandomAccessCollection은 간단하게 말해서 인덱스를 통해 배열의 요소에 접근할 수 있게 해주는 프로토콜입니다! 인덱스를 관리해주기 때문에 count를 계산하는 것도 쉽겠죠?!)

 

스택의 가장 위에 쌓여 있는 데이터를 조회하기 위해 top() 메서드는 Swift의 배열 타입에서 제공하는 last 프로퍼티를 활용하고,

이 또한 O(1)의 시간 복잡도를 가집니다.

 

count | Apple Developer Documentation

isEmpty | Apple Developer Documentation

last | Apple Developer Documentation

---

스택을 구조체로 구현하는 이유

스택은 굳이 구조체로 만들어주지 않아도, 아래처럼 배열로만 스택에서 요구하는 기능을 구현할 수 있습니다.

var stack: [Any] = [] 
stack.append(data)  // push
stack.popLast   // pop
stack.isEmpty   // isEmpty
stack.last      // peek

 

그런데, 왜 스택을 굳이 구조체로 구현해야 하는지 생각해봅시다.

 

스택에서 우리가 원하는 주된 기능은 데이터를 삽입(push)하고 삭제(pop)하는 것입니다.

그러나 배열 타입으로 데이터를 관리하다 보면 내부 값을 실수로 다른 함수를 사용해 참조하거나 변경할 수 있는 문제가 발생할 수 있습니다.

 

이런 실수를 방지하기 위해 우리는 처음부터 제공되는 연산을 명확히 지정하고, 내부 값을 조작할 때에는 오로지 그 연산만을 사용할 수 있도록 구조체로 만드는 것이 좋습니다.

 

이런 설계는 코드의 신뢰성을 향상시키고 유지보수를 용이하게 만들어 줍니다

(나중에 배울 Queue와 Dequeue도 이와 비슷한 원리로 구조체로 구현합니다.)

 

그럼에도 한 가지 의문이 생길 수 있습니다.

 

'isEmpty나 count도 빼야 되는 거 아니야?'라는 의문이 생길 수 있습니다.

 

사실, 스택의 기본 개념에는 없어야 하는 기능이 맞습니다.

하지만, 이러한 기능들은 사용자의 편의를 위해 추가된 연산입니다.

 

이러한 편의성을 제공하는 연산은 데이터를 훼손하지 않으면서도 스택의 핵심 목적을 벗어나지 않는 선에서 추가되어야 합니다.

---

Swift 전체 코드

struct Stack<T> {
    // 제네릭으로 빈 배열 생성
    private var datas: [T] = []
    
    // 배열에 담긴 데이터의 개수
    var count: Int {
        return datas.count
    }
    
    // 스택이 비어있는지 여부
    var isEmpty: Bool {
        return datas.isEmpty
    }
    
    // 데이터 삽입(push)
    mutating func push(_ data: T) {
        datas.append(data)
    }
    
    // 데이터 삭제(pop)
    mutating func pop() -> T? {
       return datas.popLast()
    }
    
    // 가장 최근 데이터 조회
    func top() -> T? {
        return datas.last
    }
    
}

 

---

마무리

정리해서 올리고 싶은 내용이 한 두 개가 아니네요..

공부한 것들을 다 올리고 싶지만 글로 정리하는 것도 시간이 오래 걸려 좀 힘들어요. 😭

 

그래도, 열심히 공부하고 글을 잘 정리해서 꾸준히 올리겠습니다!

(많이 올리면 언젠가는 누군가가 봐주겠죠..)

 

사실, 글을 작성하는 과정에서 잘못된 내용을 방지하기 위해 노력하고 있어요.

정확한 내용을 전달하기 위해 한 번 더 찾아보는 과정에서 많은 공부가 되고 있어서,

이 부분이 저에게 큰 도움이 되고 있습니다.🤓

---

잘못된 내용이나 궁금하신 점이 있다면 댓글 남겨주세요. 🤓

읽어주셔서 감사합니다.

---

📝 참고 자료

한국외대 신찬수 교수님의 Data Structures with Python 강의

https://babbab2.tistory.com/85

https://jeonyeohun.tistory.com/319

[Swift:자료구조] Stack 와 struct