[Data Structures] Stack

Stack

Stack은 번역을 돌려보면 동사로 ‘쌓다’라는 뜻이 있다.

자료구조에서의 Stack도 비슷한 것 같다. 데이터들을 쌓게되면 쌓는 데이터들은 모두 가장 위에 오고, 꺼낼때도 위에 데이터부터 꺼내게 된다.

이걸 우리는 LIFO 라고 부른다. last in first out 으로 나중에 들어온 놈이 먼저 나간다는 뜻이다.

iOS에서도 스택구조로 동작하는 것이 있다. 바로 navigation controller이다. vc가 들어오고 나갈 때 나중에 들어온 놈이 먼저 사라져야 아래 화면을 볼 수 있다.

이번 포스팅에서는 Stack의 기본 동작인 push, pop을 구현해본다.

stack 파일 생성

먼저 Stack 구조체를 담을 Stack.swift 파일을 생성한다.

struct Stack<T> {
    private var storage: [T] = []
}

Stack 구조체는 어떤 값이든 받을 수 있도록 제네릭으로 선언하고 내부에는 데이터들을 관리할 storage를 프로퍼티로 놓는다.

push, pop 구현해보기

Stack 내부에서 데이터를 관리하는 용으로 배열을 사용하기 때문에 push와 pop을 구현하는 것은 아주 쉽다.

    mutating func push(element: T) {
        storage.append(element)
    }
    
    mutating func pop() -> T? {
        return storage.popLast()
    }

push는 기존 배열에 append를 pop은 기존 배열에서 popLast를 실행해주면 된다. 코드를 실행해보면

print로 봤을 때 stack이 1 - 2- 3- 4로 잘 쌓여있고 pop 하면 가장 마지막에 추가된 4가 튀어나오는 것을 확인할 수 있다.

Non-essential operations (peek, isEmpty)

push와 pop은 스택 구현에 필수인 항목이지만 peek과 isEmpty는 그다지 중요한 부분은 아니었나…

isEmpty는 여러번 썼으니 뭔지 알고, peek은 스택의 가장 위에 있는 데이터 (가장 마지막에 들어온 데이터)를 반환해준다.

    func peek() -> T? {
        return storage.last
    }
    
    func isEmpty() -> Bool {
        return peek() == nil
    }

코드로는 이렇게 짤 수 있는데 isEmpty는 storage의 isEmpty를 반환해줘도 되는 게 아닐까 싶음.

배열로 스택 초기화 하기

스택 내부에서 데이터를 배열로 하기 때문에 배열로 한번에 값까지 초기화 하고 싶은 경우가 있을수도 있다.

    init() {}
    
    init(elements: [T]) {
        storage = elements
    }

storage는 private 프로퍼티이므로 init을 추가해서 생성해준다. 단 init()도 함께 넣어줘야 빈 값으로 Stack을 초기화 할 수 있으므로 함께 추가해주자.

코드를 돌려보면 넣어준 배열이 Stack의 형태로 잘 들어갔고 pop 하면 D가 나온다.

조금더 나아가서 var stack: Stack = [1, 2, 3, 4] 와 같이 배열처럼 초기화 할 수도 있다.

extension Stack: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: T...) {
        storage = elements
    }
}

ExpressibleByArrayLiteral을 채택후 init을 구현해주면,

배열처럼 초기화도 가능하다.