[자료구조] Swift로 구현하는 Stack

Stack이란?

 스택은 리스트의 끝(즉, 스택의 맨 위)에서 자료의 삽입과 삭제가 이루어지는 자료구조이다. 가장 최근에 들어온 자료가 가장 먼저 나가게 되는 LIFO(Last In First Out) 형태를 띄고있다. 스택의 입출력은 맨 위(top)에서만 일어나기 때문에 스택의 중간에 데이터를 삽입하거나 삭제하는 것은 불가능하며 top을 중심으로 연산이 이루어진다.

 

 스택에서 사용되는 연산은 다음과 같다.

• count : 스택에 들어있는 요소들의 개수 
• isEmpty : 스택이 비어있는 지를 체크
• push : 스택에 새로운 요소를 삽입
• pop : 스택의 top에 있는 요소를 삭제 
• top : 스택의 top에 있는 요소 조회 

 

Stack의 기본 구조

struct Stack<T> {
    // 스택의 요소들을 담아두는 배열
    var elements: [T] = []
    
    // 스택에 몇 개의 요소들이 있는지를 체크하는 연산 프로퍼티
    var count: Int {
        return elements.count
    }
    
    // 스택이 비어있는 지를 체크하는 연산 프로퍼티
    var isEmpty: Bool {
        return elements.isEmpty
    }
}

 

 구조체를 사용하여 Stack을 구현한다. 제네릭을 사용하여 데이터를 담을 수 있는 elements 배열을 만들어준다. 스택의 데이터 개수와 스택이 비어있는지 여부는 배열에서 제공하는 count 프로퍼티와 isEmpty 프로퍼티를 사용하여 구현해준다. 

 

삽입 연산 (push)

    // 스택에 입력으로 받은 element를 push
    mutating func push(_ element: T) {
        elements.append(element)
    }

 

 배열에서 제공하는 append()를 사용하여 elements 배열의 마지막에 새로운 데이터를 삽입한다.

 

삭제 연산 (pop)

    // 스택의 가장 위에 있는 요소(배열의 마지막 요소)를 삭제하며 리턴
    mutating func pop() -> T? {
        return elements.popLast()
    }

 

 삭제 연산 역시 배열에서 제공하는 popLast()를 사용한다. 배열의 마지막 요소를 삭제하는 연산에는 popLast()뿐만 아니라 removeLast()도 있다. 하지만 removeLast()의 경우 배열이 비어있을 경우 에러를 발생시키지만 popLast()의 경우는 반환 타입이 옵셔널이기 때문에 비어있는 배열에 사용해도 에러가 발생하지 않고 nil이 리턴된다.

 popLast()가 옵셔널을 반환하기 때문에 Stack의 pop() 역시 옵셔널을 리턴하도록 구현한다.

 

조회 (top)

    // 스택의 가장 위에 있는 요소(배열의 마지막 요소)
    func top() -> T? {
        return elements.last
    }

 

 스택의 가장 위에 있는 데이터를 조회한다. 배열에서 제공하는 last 프로퍼티를 통해 조회할 수 있다. 

 

전체 코드

import Foundation

struct Stack<T> {
    // 스택의 요소들을 담아두는 배열
    var elements: [T] = []
    
    // 스택에 몇 개의 요소들이 있는지를 체크하는 연산 프로퍼티
    var count: Int {
        return elements.count
    }
    
    // 스택이 비어있는 지를 체크하는 연산 프로퍼티
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    // 스택에 입력으로 받은 element를 push
    mutating func push(_ element: T) {
        elements.append(element)
    }
    
    // 스택의 가장 위에 있는 요소(배열의 마지막 요소)를 삭제하며 리턴
    mutating func pop() -> T? {
        return elements.popLast()
    }
    
    // 스택의 가장 위에 있는 요소(배열의 마지막 요소)
    func top() -> T? {
        return elements.last
    }
}

 

 

References

- https://jeonyeohun.tistory.com/319?category=884320

- https://babbab2.tistory.com/85?category=908011