스택에 대한 개념
Q. 스택을 왜 배워야하죠?
A. 사용하면, 내가 원하는 데이터를 넣을 수 있고 원하는 데이터를 뺄 수 있기 떄문이죠. 물론 이 대답은 자료구조를 왜 사용하는지와도 일맥상통합니다.
Q. 그럼 스택이 뭔가요?
A. 스택이 무엇인지 설명하기 전에 예시를 들어볼게요.
- 팬케이크
- 책
- 종이
- 돈
이것들이 스택의 예시입니다. 감이 오시나요?
무언가 쌓여있다는 느낌이 들죠?
팬케이크를 먼저 볼게요. 제일 먼저 구워진 팬케이크가 제일 아래로 가고 그 다음순서로 구워진 케이크가 그 위로 가죠. 새로 추가되는 팬케이크는 계속 제일 위에 쌓입니다.
그러면 책을 생각해볼까요? 도서관에서 책을 꺼내서 쌓는다고 생각해봅시다.
먼저 꺼낸 책이 제일 아래로가고 나중에 쌓는 책이 제일 위로 갑니다.
종이와 돈도 마찬가지일겁니다.
여기서 스택의 속성을 추출할 수 있겠네요.
"스택"은 무언가 추가할 때, 제일 위에 추가한다. 만약 스텍에서 무언가를 뺀다면, 밑장빼기는 불가능하고 제일 위에서부터 빼야한다. (넣는 순서의 역순으로 뺴야한다.)
(이미지 출처: https://unsplash.com/photos/ecUVGNZA1TM)
스택의 오퍼레이션
Q. 이제 스택이 뭔지 감은 잡힙니다. 그러면 스택에 어떻게 무언가를 추가하고 뺄 수 있나요?
A. 무언가 행위를 하는 것을 "오퍼레이션"이라고 하고 스택에 무언가를 하고 싶은 거잖아요? 그래서 스택에 대한 오퍼레이션 또한 존재합니다.
push: 스택의 최상위에 구성요소를 추가합니다.pop: 스택의 최상위의 구성요소를 제거합니다.
오퍼레이션의 설명을 읽어보시면 느낌이 오셨을 수도 있겠네요. 우리는 제일 위에있는 요소만 조작할 수 있어요. 제일 위에 있는 요소제거하는 것이 pop 이 되겠고, 추가하는 것이 push 가 됩니다.
이러한 데이터 구조를 컴퓨터과학에서는 "LIFO" (Last in First Out) 이라고 칭합니다.
iOS 프로그래밍에서 예시를 들자면,
우리가 viewController.present(내가원하는VC, animated: false. completion: nil)
이라는 메소드를 사용하여 화면을 전환합니다.
이 메소드를 사용하면, 이전 화면이 아래 위치하고 "내가원하는VC"가 그 위에 위치하는 걸 볼 수 있죠. 이것도 스택의 한 예시입니다. 그렇게 여러화면을 쌓은다음에
현재위치한VC.dismiss(animated: false) 를 해보면 제일 최근에 생성된 화면먼저 사라집니다.
스택 구현
Q. 스택을 구현한다고요? 그냥 제가 array에 .append해서 마지막 순서에 추가하고 popLast() 해서 쓰면 안되나요?
A. 네. 간단한 경우는 그렇게해도 되겠죠. 하지만, 그건 자신만 알고 있는 약속일겁니다. 이 배열은 스텍으로 쓸거야! 라고 생각하기에 그렇죠. 애초에 구조가 마지막요소에만 접근할 수 있도록 구조체를 선언한다면, 다른사람이 그 코드를 봐도 그렇게 사용하여 의사소통으로 인한 비용이 줄어들겠죠??
그래서 Struct로 Stack을 구현하고 그 구조체를 채택하여 사용하는 것이 현명합니다.
- Stack의 구조
public struct Stack<Element> {
// 1
private var storage: [Element] = []
// 2
public init() { }
}- "storage" 라는 변수가 "Element" 타입을 따르고 있는 array로 선언되어 있습니다. Element 타입은
제네릭타입입니다. 뭔가 단어 뜻 자체에 이미 답이 있죠? 일반적이고 추상화시킨 타입으로, 이 구조체를 사용할 때, Element의 타입을 정해주면 정해진 타입을 따르게 되는 경우입니다. 이렇게 제네릭을 사용하면 여러가지 타입의 경우에 모두 사용할 수 있는 Stack 구조체가 되겠죠.
추가로 "storage" 옆에 보면private이 있습니다. 이것의 역할은 "접근을 제어" 합니다. 접근제어자 혹은 접근제어 라고 칭합니다. 자세한 설명은 다음에 다루도록 하고, 간단히 설명하자면 현재 구조체 내에서만 접근이 가능하도록 한 겁니다. - "init" 을 보시면 init은
public이죠? 이것도 접근제어입니다. 이것은 어디서든 접근할 수 있도록 설정한것입니다. 위 코드는 사용하실 때, storage에는 직접 접근이 불가능하도록 구성했습니다. 그러므로 값이 추가된 이후에, 변경될 확률이 낮아지죠.
- "CustomStringConvertible" 을 이용하여 보기좋게 print한다.
extension Stack: CustomStringConvertible {
public var description: String {
"""
----top----
\(storage.map { "\($0)" }.reversed().joined(separator: "\(\n)"))
-----------
"""
}
}위 extension으로 추가된 코드는 반드시 필요한 부분은 아닙니다. 그저 개발자가 읽기 좋도록 콘솔로그에 찍기 위해서 구성한 부분이구요. 코드를 간략하게만 설명하자면.
storage 배열에 접근할 때, 고차함수인 map을 사용해서 string으로 바꿔줍니다.(각각의 요소들을)
그것들의 순서를 변경해주는 메소드인 reversed() 를 통해서 역순으로 하였고, string 배열을 하나로 합쳐주는 메소드인 joined(separator:) 를 통해서 합치되 각요소가 합쳐질 때 요소의 마지막에 \n를 붙여줍니다.
이렇게 출력하면 이런식으로 나옵니다.
이제 각각의 오퍼레이션을 구현해보겠습니다.
- push && pop
public mutating func push(_ element: Element) {
storage.append(element)
}
@discardableResult
public mutating func pop() -> Element? {
storage.popLast()
}이 두 메소드를 이용해서 값을 추가하거나 뺄 수 있습니다.
Q. 이거 두개가 오퍼레이션은 끝인가요?
A. 아닙니다. 반드시 필요하지는 않지만, 다른 오퍼레이션도 있습니다. 만약 필요하시면 스스로 구현해도되구요!
비필수 오퍼레이션인 peek와 isEmpty를 보겠습니다.
이 둘은 storage에는 변화가 없습니다.
public func peek() -> Element? {
storage.last
}
public var isEmpty: Bool {
peek() == nil
}스택은 collection 프로토콜을 채택하면 안되나요?
이런 위 질문을 할 수 있습니다.
collection 프로토콜을 채택하게 되면, 모든 element에 서브스크립트로 접근해서 데이터를 찾기 쉽겠죠.
그런데 그렇게 collection 프로토콜을 채택하게되면 stack의 최초목적과 어긋나게 됩니다. stack을 만든 목적이 제한된 접근을 하도록 하게 하는 것이니까요.
하지만 구현은 할 수 있습니다.
public init(_ elements: [Element]) {
storage = elements
}먼저 array 전체를 받아서 storage에 할당할 수 있도록 하비다.
그리고 배열을 받을 수 있도록 다음과 같이 Extension으로 추가합니다.
extension Stack: ExpressibleArrayLiteral {
public init(arrayLiteral elements: Element...) {
storage = elements
}
}스택구조는 "search trees and graphs" 단원에서 중요하게 사용될 것입니다.
이후에 관련된 내용을 작성 후, 링크를 남겨두겠습니다.
참고자료)
