[자료구조] 1. Stack(스택)이랑 친해지고 구현하기

비전공자인 나,,^^ 그래서 자료구조나 알고리즘,, 같은 CS 공부에 너무나도 목말라 있는 중,,

특히 코테를 준비하다 보니까 더더욱 이런 지식들이 필요하다는 것을 느끼는 즁,,!!!

그래서 자료구조를 열심히 파보기로 합미다✨

오늘은 먼저 스택💫을 파보자고〰️ 가보자고〰️

---

Stack 📚

사실 Stack은 이전부터 많이 들었는데 생각해 보니까 무슨 뜻인지 잘 모르고 용어를 사용했다.

그래서 뜻을 검색해 봤더니 무더기, 채우다, 쌓이다 등의 의미를 지닌 단어라고 한다.

말 그대로 어떤 물체나 작업들이 쌓여있는 것을 의미한다. 근데 막 쌓여있는 느낌보다는 정돈되어 쌓여 있는 느낌!

요런 너낌,,!!!

 

그래서 Stack은 데이터를 쌓아놓은 자료구조이다.

데이터가 "쌓이기" 때문에 어떤 항목을 스택에 넣으면 가장 위에 쌓이게 되고, 

제거할 때도 가장 위에 있는 것부터 제거가 된다. 그래서 LIFO(Last In, First Out) 특성을 갖게 됩니댜

LIFO, 후입선출 구조! 가장 마지막에 들어간게 가장 먼저 제거된다.

 

Stack에는 필수적인 작업이 두 개가 있는데 Push와 Pop이다. Stack에 데이터를 넣는 작업을 Push, 제거하는 작업을 Pop이라고 한다. Stack은 후입선출 구조이기 때문에 데이터가 한 방향에서만 추가하고 제거될 수가 있다. 그래서 가장 마지막에 push된 요소가 가장 먼저 pop 되면서 제거된다.

 

Swift에서는 Stack을 구현하는 가장 일반적인 방법이 배열을 사용하는 것이다.

배열 자체에 Stack에서 구현하는 append와 removeLast, popLast 메서드를 가지고 있기 때문에 배열을 이용해서 Stack 연산을 쉽게 구현할 수 있다. 배열을 사용해서 Stack을 구현하면 배열의 마지막 요소를 추가하거나 제거하는 작업만 수행하기 때문에 시간복잡도가 O(1)을 유지한다. (그래서 굳이 Stack을 만들지 않고 배열을 사용해도 된다고 함..!)

 

---

Let's implement a stack🚀‼️

구조체를 이용해서 Stack을 정의해 보자

struct Stack<Element> {
    var elements: [Element] = []
    
    var count: Int {
        return elements.count
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    func top() -> Element? {
        return elements.last
    }
    
    mutating func push(_ element: Element) {
        elements.append(element)
    }
    
    mutating func pop() -> Element? {
        return elements.popLast()
    }
}

 

📍 Stack 구조체에 Generic의 데이터를 담을 수 있는 elements 배열을 생성한다. 

 

📍 그리고 스택에 데이터가 몇 개 있는지 알기 위한 count 프로퍼티를 생성한다. 배열의 count 계산 속성을 사용했다. 마찬가지로 스택에 데이터가 존재하는지 확인하는 isEmpty 프로퍼티도 생성했고 이 또한 배열의 isEmpty 계산 속성으로 구현했다.

 

📍 func top() 은 현재 스택의 가장 마지막에 있는 데이터가 무엇인지 확인하는 함수이다. 배열의 last 속성을 사용해서 확인할 수 있다. 값을 확인했을 때, 없을 수도 있기 때문에 옵셔널로 리턴한다.

📍 func push(_ element: Element) 는 스택에 데이터를 추가하는 함수이다. 배열의 append 메서드를 활용한다. 

📍 func pop() 은 스택의 가장 마지막 데이터를 제거하는 함수이다. 이것도 배열의 popLast 메서드를 활용했다. removeLast도 사용할 수 있지만 값이 없을 경우에 removeLast는 에러를 발생한다. 반면, popLast의 경우에는 nil을 반환할 수 있기 때문에 더 안전하게 popLast를 사용!

 

popLast 공식문서. Self.Element? 옵셔널로 리턴

 

removeLast 공식문서. Self.Element를 리턴

 

💡 이 3개의 함수들이 처리하는 작업들은 모두 마지막 데이터를 확인하거나 추가/제거하는 작업이기 때문에 상수 시간 내에 수행될 수 있어서 시간복잡도는 O(1)이다. 

 

💡 push와 pop 함수에 mutating 키워드가 붙어있다. 이 함수들은 Stack 구조체 내부에서 elements 프로퍼티의 값을 변경하려고 하는데 이럴 경우에는 error: cannot use mutating member on immutable value: 'self' is immutable 하는 에러가 뜬다. 구조체와 열거형과 같은 값 타입(Value Type)은 인스턴스가 생성된 후에 그 인스턴스의 속성이 변경되지 않도록 구현했다. 그래서 인스턴스 내부의 값을 변경하려면 메서드에 mutating 키워드를 붙여서 값을 변경하겠다는 표시를 해주어야 한다. 

 

이렇게 구현해서 실행해 보면

var myStack = Stack<Int>()
myStack.push(1)
myStack.push(2)
myStack.push(3)
print(myStack.elements) // [1, 2, 3]
print(myStack.top()) // Optional(3)
myStack.pop()
print(myStack.elements) // [1, 2]

 

이런 결과를 확인할 수 있다!

 

---

 

내친김에 ㅎ 스택으로 풀 수 있는 코테 문제도 한 번 풀어봤따,,! 

프로그래머스 알고리즘 고득점 Kit에 보면 스택/큐 문제 모아놓은 카테고리가 있댜

 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

내 답안

func solution(_ s: String) -> Bool {
    
    var elements: [Character] = []
    
    guard let first = s.first else { return false }
    if first == ")" {
        return false
    }
    
    for char in s {
        if char == "(" {
            elements.append(char)
        } else {
            if elements.isEmpty {
                return false
            } else {
                elements.popLast()
            }
        }
    }
    return elements.isEmpty
}

 

풀이

1. elements 배열을 생성함. 이 배열을 이제 Stack으로 사용할고임

 

2. 처음에 "(" 로 무조건 시작해야 하기 때문에 ")" 로 시작하는건 먼저 리턴해줬음. 생각해 보니까 굳이 언래핑 안 해줘도 됨

 

3. for-in 구문을 통해 s 에서 아이템을 하나씩 꺼내서 확인하는 작업을 함. 만약, "(" 라면 배열에 추가를 해줌. 그리고 ")" 일 때, 배열이 비어있으면 false로 리턴함. 배열에 "("가 없이 비어있다면 짝을 이룰 수 없기 때문! 비어있지 않다면 "("가 있을거기 때문에 짝을 이룰 수 있음! 그래서 배열에 popLast() 를 해서 짝이 맞으면 배열에 요소를 제거할 수 있음.

 

4. 그래서 만약 배열의 요소가 다 제거되었다면 즉, 스택에 데이터가 남아있지 않다면 elements.isEmpty를 통해 true를 리턴하고, 만약 스택에 데이터가 남아있으면 짝을 다 이루지 못한거니까 false를 리턴하도록 함!

 

---

 

드디어 자료구조 공부를 시작했드아..!!!!

매번 해야지 해야지 생각만 하다가 ,, ㅠ 근데 하니까 재밌네,,~ 아무래도 제일 쉬운 스택을 해서 그럴 수도,,

지금까지 스택이 대충 어떤 건지는 알았는데 구현은 처음 해보기도 하고, 코테에 적용도 해보니까 넘넘 재밌댜

열심히 자료구조 공부해서 여러모로 도움 되었으면 좋겠댜~~!~!

 

---

📖 reference(늘 감사합니당) ♥️

 

https://jeonyeohun.tistory.com/319

스위프트로 구현하는 자료구조 1: 스택(Stack)

https://kimdee.tistory.com/entry/Swift번역-스위프트의-자료구조와-알고리즘-섹션-2-기초-자료구조-챕터45-스택-스택-도전과제?category=937199

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전