스택

안녕하십니까. 그린입니다🟢

이번 포스팅에서는 스택에 대해 알아보고 Swift로 구현해보겠습니다🧑🏻‍💻

 

스택

: 후입선출 자료구조 (LIFO)

 -> 기능이 제한된 배열 (푸쉬/팝/픽의 세가지 역할밖에 못함)

 -> 순서가 중요할때 가장 뒤 순서의 데이터를 꺼냄으로 배열 크기와 상관없이 항상 O(1)의 시간 복잡도를 가짐 (배열보다 효율적)

 -> 중간 데이터 삭제 불가능

Swift로 스택 구현하기

import Foundation

struct Stack<T> {
    var stack: [T] = []
    
    // 초기화 시 아무 값이 주어지지 않을때 동작하는 초기화
    init() {}
    
    // 초기화 시 값이 주어질때 동작하는 초기화
    init(_ element: [T]) {
        stack = element
    }
    
    // 데이터 저장
    mutating func push(_ element: T) {
        stack.append(element)
    }
    
    // 데이터 추출함과 동시에 제거
    mutating func pop() -> T? {
        return stack.popLast()
    }
    
    // 데이터 추출만
    func peek() -> T? {
        return stack.last
    }
    
    // 스택이 비었는지 판별
    func isEmpty() -> Bool {
        return stack.isEmpty
    }
    
    // 스택의 갯수 카운트
    func count() -> Int? {
        return stack.count
    }
}

// 스택을 출력할때 커스텀한 설명을 추가하는 프로토콜
extension Stack: CustomStringConvertible {
    var description: String {
        return stack.description + "이 스택에 들어있습니다."
    }
}

// 스택 초기화 후 반복문 없이 배열로 스택을 넣을때 사용하는 프로토콜
extension Stack: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: T...) {
        for element in elements {
            stack.append(element)
        }
    }
}

var firstStack: Stack = Stack<Int>()
var secondStack: Stack = Stack<Int>([1, 2, 3, 4])
var thirdStack: Stack = Stack<Int>()

firstStack = [2, 4, 6, 8]
thirdStack.push(10)
thirdStack.push(20)
print("\(firstStack)" + "\n" + "\(secondStack)" + "\n" + "\(thirdStack)")

위와 같이 다양하게 스택의 초기화를 두어 편하게 사용할 수 있습니다.

스택의 push와 pop은 구조체의 프로퍼티에 값을 추가/삭제하여 변경됨으로 꼭 mutating 키워드를 붙여 프로퍼티를 변경할 수 있는 메서드라는걸 명시해줘야합니다.

또한, CustomStringConvertible 프로토콜을 채택해 스택을 출력 시 원하는 설명을 커스텀하게 설정할 수 있습니다.

마찬가지로 CustomDebugStringConvertible 프로토콜을 채택해 아래와 같이 사용하면 디버그 메시지에 대해 커스텀하게 설정할 수 있습니다.

extension Stack: CustomDebugStringConvertible {
    var debugDescription: String {
        return stack.debugDescription + "이 스택의 디버그 설명입니다."
    }
}

마지막으로 초기화 시 값을 주어주지 않거나 매번 반복해서 값을 하나씩 주어주기 불편할때 ExpressibleByArrayLiteral 프로토콜을 사용할 수 있습니다.

공식문서에도 나와있듯이 init 초기화 시 arrayLiteral을 통해 주어진 배열리터럴에서 배열을 만듭니다.

만들어진 배열로 스택에 들어가게 초기화를 구현할 수 있습니다.

이 속성을 사용하기위해 해당 프로토콜을 채택하여야합니다.