📌 swift로 stack 자료구조를 구현해보자!!!

0. Stack?

먼저 들어온게 나중에 나간다. (First In, Last Out: FILO)
혹은 나중에 들어온게 먼저 나간다! (Last In, First Out: LIFO)

가장 먼저 들어간 요소는 밑에 깔려서 가장 나중에 나온다. 책을 층층이 쌓아두면 아래쪽 책을 꺼내려면 가장 위의 책부터 꺼내야 한다는 것을 생각해보자.

1. Stack의 구조

스택 자료구조가 하는 역할은 맨 뒤에 있는 요소를 빼거나(pop) 확인하고(top), 새로운 요소를 추가하는(push) 것이다. 이 3가지 기능은 O(1)로 처리되며 가장 핵심 역할이다. 스택의 중간에 있는 요소를 확인할 수도 있지만 그런 것은 보통 스택을 ‘배열'로 만들어서 ‘배열'의 기능을 가져다 쓰는 것이지 스택 자체가 가지는 기능은 아니당.

• push

  • 새로운 요소를 맨 끝에 추가한다.

    

• pop

  • 맨 끝의 요소를 제거한다.

    

• top (흑은 Peek)

  • 맨 끝의 요소가 뭔지 알려준다.

스택을 구현하려면 새로운 값이 들어갈 위치, 즉 마지막 요소가 있는 곳을 알아야 한다. 그래야 새로 값도 추가하고, 제거도 할 수 있다. 이를 pos 라는 이름의 변수로 구현하자~

• pos
  • 다음 요소가 들어갈 인덱스 위치 변수

2. 구현

2.1 직접 구현하기

레퍼런스를 여러개 찾아봤는데, 다들 struct로 구현하더라. 이유가 있는건가? 그거에 대한 답은 아직 못찾았다. swift에도 class 가 있는데 다들 struct를 쓴다. swift에서 struct를 더 많이 쓴다는 건 알고 있었지만 아직까지 왜인지는 모르겠다. 아무튼…

(1) 기본 구현

push, pop, top을 pos 변수를 사용해서 만들어보자. 이 방법은 다른 언어에도 적용할 수 있다!

🔴 전체코드

var max_size = 10005
var items = [String?](repeating: nil, count: max_size)
var pos: Int = 0

// push
func push(_ item: String) {
    items[pos] = item
    pos += 1
}

// pop
func pop() -> String? {
    pos -= 1
    return items[pos]
}

// top
func top() -> String? {
    return items[pos-1]
}

// --- 사용법 ---
push("hi")
push("my")
push("name")
push("is")
push("swift.")

print(items)   // [Optional("hi"), Optional("my"), Optional("name"), Optional("is"), Optional("swift."), nil, ... , nil]

pop()          // Optional("swift.")
pop()          // Optional("is")

top()          // Optional("name")

배열의 크기를 설정하고 pos를 사용하여 배열으로 스택을 구현하였다. 그러나 나는 이게 좋은 코드라고 생각하지 않는다. 물론 이렇게 구현하는게 틀린 것은 아니지만 각각의 언어에 특성에 맞게 구현하는게 더 좋지 않을까 한다. python도, C++도 위의 코드 형식으로 모두 구현할 수 있다.

swift의 언어의 특징에 맞게 제공해주는 기본 함수를 이용해서 충분히 스택을 구현할 수 있다. 그러나 기본적인 스택의 성질을 이해하기 위해 위와 같이 구현해보았다.

필요하다면 pos 없이 아래의 (2),(3) 처럼 구현할 수도 있다.

(2)번과 (3)번의 구현은 모두 구조체 안에 메소드와 변수를 정의하여 사용하고 있다. 그러나 구조체 없이 위처럼 벗기고 구현할 수도 있다!!
둘의 차이점을 알고 적절하게 사용하면 된다.

(2) 배열의 마지막에 값을 넣고, 제거하는 방법 ✨

배열을 이용하여 스택을 구현한다. 이때 새로운 item은 배열의 끝에 추가하고, 삭제한다.

여기서는 pos 변수를 사용하지 않는다.

✔️ 구조체 선언

struct Stack {
	var items: [String] = []
}

Stack 이라는 이름으로 구조체(struct)를 선언하고, 내부에 배열(array)을 프로퍼티(property)로 생성한다. items를 구조체 내부에서만 쓸 예정이라면 private 키워드를 붙여주도록 하자. 용도에 맞게 적절한 키워드를 붙여주자.

✔️ push

// 1
mutating func push(_ item:String) {
	// 2
	self.items.append(item)
}

1. 새로운 item을 스택에 추가하는 push 함수이다. 이 함수는 items 배열의 맨 뒤에 새로운 item을 추가한다.

   • items의 내용을 수정하므로 mutating 키워드를 함수 선언부에 추가한다. 왜냐하면 swift의 struct는 값(value) 타입이므로 struct의 변수 프로퍼티 값을 인스턴스 메소드에서 변경할 수 없기 때문이다. 즉, push 함수는 Stack struct의 인스턴스 메소드이고, 이 함수에서는 Stack struct의 변수 프로퍼티 items의 내용을 수정해야 하기 때문에 mutating 키워드를 함수 선언 앞에 붙여주는 것이다.

   💡 **mutating 키워드**

   struct의 인스턴스를 상수(constant)로 선언하면 struct의 변수 프로퍼티 값을 수정할 수가 없다. 프로퍼티가 상수든 변수든 뭐라고 선언되었든지 간에 모두 다 상수로 취급된다.

   let stk1 = Stack()  // 상수로 선언한 Stack struct의 인스턴스 stk1이다.
   var stk2 = Stack()  // 변수로 선언한 Stack struct의 인스턴스 stk2이다.

   그러나 문제는 Swift에서 struct를 만들면 Swift는 우리가 이 struct를 변수로 쓸지 상수로 쓸지 모른다는 것이다(!). 상수로 선언되면 아예 변경이 불가능하지만, 변수로 선언되면 프로퍼티의 값이 변경 가능하다. 그러므로 안전한 접근을 위해 프로퍼티를 변경하는 메소드를 사용하려면 구체적으로 요청(request)를 해야 한다. ‘이 함수는 프로퍼티 값을 변경해주는 함수에요'라고 표시를 해준다고 생각하면 편하다.

   여기서 요청을 하는 방법은 메소드 선언부 앞에 mutating 키워드를 붙여주는 것이다.

2. 인스턴스 변수 items에 새로운 item을 append를 사용하여 추가한다. 시간 복잡도는 O(1)이 된다.

✔️ pop

mutating func pop() -> String? {
	return self.items.popLast()
}

items의 가장 마지막에 있는 요소를 [popLast()](https://developer.apple.com/documentation/swift/array/poplast())를 사용하여 제거한다. pop함수도 프로퍼티(items)의 값을 변경하므로 mutating 키워드를 작성한다. 시간 복잡도는 O(1)이다.

✔️ top

func top() -> String? {
	return self.items.last
}

top은 배열의 last로 마지막 요소를 구한다. 시간 복잡도는 O(1)이다.

🔴 전체 코드

struct Stack {
    var items: [String] = []
    
    mutating func push(_ item:String) {
        self.items.append(item)
    }
    
    mutating func pop() -> String? {
        return self.items.popLast()
    }
    
    func top() -> String? {
        return self.items.last
    }
}

🔵 사용법

var stk = Stack()

stk.push("hi")     // Stack(items: ["hi"])
stk.push("my")     // Stack(items: ["hi", "my"])
stk.push("name")   // Stack(items: ["hi", "my", "name"])
stk.push("is")     // Stack(items: ["hi", "my", "name", "is"])
stk.push("swift.") // Stack(items: ["hi", "my", "name", "is", "swift."])

stk.pop()          // Optional("swift.")

stk.push("python.") // Stack(items: ["hi", "my", "name", "is", "python."])

stk.top()          // Optional("python.")

아주 잘 작동한다. 단지 pop과 top의 결과가 옵셔널인 이유는 리턴값을 옵셔널로 처리했기 때문이다(와~).

(3) 배열의 처음에 값을 넣고, 제거하는 방법

배열을 이용한 스택 구현을 다르게 만들 수도 있다. 대신 시간 복잡도에서 차이가 난다❗️

이번엔 배열의 가장 첫번째에 새로운 요소를 추가(push)하고, 삭제(pop)해보도록 하자.

✔️ 구조체 선언

struct Stack {
	var items: [String] = []
}

문자열을 자료형으로 하는 배열과 Stack 구조체를 생성한다.

✔️ push

mutating func push(_ item: String) {
	self.items.insert(item, at: 0)
}

배열의 insert(contentsof:at:)를 사용하여 0번째 인덱스에 값을 추가한다. 시간 복잡도는 O(n+m)이다.

✔️ pop

mutating func pop() -> String? {
	return self.items.removeFirst()
}

배열의 removefirst(_:)을 사용하여 가장 최근에 추가된 값(인덱스 0인 값)을 제거한다. 시간 복잡도는 O(n)이다.

✔️ top

func top() -> String? {
	return self.items.first
}

배열의 first를 사용하여 가장 최근의 값을 가져온다. 시간 복잡도는 O(1)이다.

🔴 전체코드

struct Stack {
    var items: [String] = []
    
    mutating func push(_ item: String) {
        self.items.insert(item, at: 0)
    }
    
    mutating func pop() -> String? {
        return self.items.removeFirst()
    }
    
    func top() -> String? {
        return self.items.first
    }
    
}

🔵 사용법

var stk = Stack()

stk.push("hi")       // Stack(items: ["hi"])
stk.push("my")       // Stack(items: ["my", "hi"])
stk.push("name")     // Stack(items: ["name", "my", "hi"])
stk.push("is")       // Stack(items: ["is", "name", "my", "hi"])
stk.push("swift.")   // Stack(items: ["swift.", "is", "name", "my", "hi"])

stk.pop()            // Optional("swift.")

stk.push("python.")  // Stack(items: ["python.", "is", "name", "my", "hi"])

stk.top()            // Optional("python.")

새로운 item은 items 배열의 가장 첫번째 인덱스에 들어온다. 그러므로 pop을 하면 가장 나중에 추가된 item이 제거된다.

2.2 코드를 진화시켜보자

지금까지 배열을 사용해서 스택을 구현했다. 근데 여기서 스택 구조체를 더 ‘아름답게' 발전해볼 수 있다.

1. 스택 구조체를 출력하는 기본 ‘틀'을 만들 수는 없을까?
2. String 타입 말고 다른 타입도 스택에 사용할 수는 없을까?

✅ CustomStringConvertible

그냥 스택 구조체만 출력하면 어떤 값이 앞이고 뒤인지 알기 어렵다. swift에서 제공하는 CustomStringConvertible 프로토콜을 사용하면 내가 원하는 형태로 출력을 커스텀할 수 있다! 와아앙

extension Stack: CustomStringConvertible {
		
    var description: String {
        let header = "----Stack----\n"
        let body = items.reversed().joined(separator: "\n")
        let footer = "\n-------------\n"
        return header+body+footer
    }

}

이는 아래와 같이 사용된다!!

var stk = Stack()

stk.push("hi")     
stk.push("my")     
stk.push("name")  
stk.push("is")
stk.push("swift.")

print(stk)

/*
----Stack----
swift.
is
name
my
hi
-------------
*/

Stack의 모양을 알기 쉽게 출력이 된다. CustomStringConvertible 프로토콜은 선택사항이므로 필요에 따라 구현하면 된다.

✅ Generic Types

지금까지 만든 스택은 String 자료형으로만 선언했다. 그럼 다른 자료형의 스택을 사용하려면 또 똑같은 코드를 작성해야 하나? 너무 비효율적인데…

Swift는 이를 위해 Generic Type을 제공한다. Generic한 코드는 모든 자료형을 수용할 수 있어 재사용이 가능하다~~

새롭게 만들어볼 코드는 (2)의 구조체이다.

// 1
struct Stack<T> {
		// 2
    var items: [T] = []
    // 3
    mutating func push(_ T) {
        self.items.append(item)
    }
    
    mutating func pop() -> T? {
        return self.items.popLast()
    }
    
    func top() -> T? {
        return self.items.last
    }
}

1. 구조체의 이름 옆에 꺽쇠로 자료형이 들어갈 자리의 이름(placeholder type name)을 적어준다. 쿠쿡.
2. 기존에 String이 쓰였던 부분을 placeholder type name으로 대체한다.
3. 함수에서 쓰는 파라미터도 모두 적용해준다.

이제 String 뿐만 아니라 모든 자료형이 이 스택 구조체를 사용할 수 있다.

2.3 Swift Collections의 Deque

여기까지 읽다보면 기본 내장 Stack은 없나… 생각할 것이다. C++의 STL이나 Python의 Collections 처럼!

그래서 알아보니 Swift도 기본 스택 함수가 존재하더라!! 물론 스택 하나로 쓰는 것은 아니고 deque로 쓴다. 이걸로 stack, queue, deque까지 모두 사용할 수 있다. 이름도 python의 collections.deque와 같다.

굉장히 최근에 나온 것으로 확인이 된다. (Swift Collections 1.0.2 released on 16 Nov 2021, apple swift-collections github)

Swift Collections
is an open-source package of data structure implementations for the Swift programming language.

Deque, a double-ended queue backed by a ring buffer. Deques are range-replaceable, mutable, random-access collections.

Deque의 메소드에는 append, prepend, popFirst, popLast가 있으며 특정 인덱스에 삽입과 삭제를 위한 insert(item, at:), remove(at:)이 있다.

그럼 swift collections의 deque를 stack으로 사용하는 방법을 알아보자.

단, DequeModule을 임포트 해줘야 사용할 수 있다.
xcode 프로젝트에서 사용하려고 하니 Collections 패키지를 다운받아줘야 했다. 꼭 확인할 것❗️

코드는 애플 공식 깃허브를 참고했습니다.

(1) push → append

var colors: Deque = ["red", "yellow", "blue"]

colors.append("green")  // 배열의 뒤에 추가
colors.prepend("black") // 배열의 앞에 추가

스택의 Push는 append를 사용하면 되겠다.

(2) pop → popLast

var colors: Deque = ["black", "red", "yellow", "blue", "green"]

colors.popLast()   // 배열의 뒷 요소 제거
colors.popFirst()  // 배열의 앞 요소 제거

스택의 pop은 popLast를 사용하면 되겠다.

(3) top → last

Deque는 Array와 비슷하게 동작한다고 하니, top의 기능은 기존과 동일하게 last를 쓰면 된다.

📒 정리

지금까지 Swift에서 Stack의 구현에 대해 공부해보았다. C++과 Python으로만 하닥 처음 Swift로 해봤는데 python이랑 비슷~~하면서도 자료형 선언 때문에 조금 까탈스럽긴했다. 그래도 스택은 역시 간단하고.. 재밌다.

필요에 따라 Swift에서 스택을 구현하면 되고, 구조체로 만드는게 어렵지 않아서 직접 구현해야 한다면 배열로 간단하게 만들어보자! 만약 코테에서 Collections의 Deque를 사용할 수 있다면 이것을 사용하도록 하자. 이미 만들어진 것을 쓰는게 디버깅할 때 편하다!

---

reference

https://medium.com/devslopes-blog/swift-data-structures-stack-4f301e4fa0dc

https://nitinagam17.medium.com/data-structure-in-swift-stack-part-3-81fdb946b160

https://www.raywenderlich.com/800-swift-algorithm-club-swift-stack-data-structure

https://stackoverflow.com/questions/57059558/is-there-a-built-in-stack-implementation-in-swift

https://docs.swift.org/swift-book/LanguageGuide/Generics.html

https://github.com/apple/swift-collections

https://www.hackingwithswift.com/sixty/7/5/mutating-methods

https://hyerios.tistory.com/190

swift array 선언시 크기 초기화 : https://stackoverflow.com/questions/24395105/how-to-create-a-fixed-size-array-of-objects