swift 자료구조 stack 코드로 정리 - 스택 일상생활 예제

swift 자료구조 stack 코드로 정리

 

스택이란?

스택은 우리 일생생활에서 쉽게 찾아 볼 수있는 구조 입니다.

예를들어 박스에 책을 한 권씩 높게 쌓아 올린 그림을 떠올려 볼 수 있고, 팬케이크를 한장씩 쌓아올린 그림을 떠오려 볼 수 있습니다.

이 예 말고도 많은데, 스택은 어떤 물건을 하나씩 쌓아 올린 구조라고 떠올리면 됩니다.

 

스택의 작업

스택은 대표적으로 두가지가 있습니다.

[1] push : 스택의 맨 위에 요소를 추가합니다. (높이 쌓인 책들이 있는데 그 위에 책을 하나 올려 놓는 것입니다.)

[2]pop : 스택의 맨 위에 요소를 제거 합니다. ( 높이 쌓인 책들이 있는데 그 중에서 제일 위에 있는 책을 제거하는 것입니다.)

 

스택을 한 마디로 정리하면 스택은 한쪽에서만 요소를 추가하거나 제거 할 수 있는 데이터 구조 입니다.

 

ios 에서도 스택 자료구조를 이용한 곳이 많습니다.

 

[1] navigationViewController 가 스택 구조로 되어 있습니다. 그래서 A화면에서 B화면을 열고 B 화면에서 C화면을 열었다고 가정하면 뒤로가기 버튼을 눌렀을때 C화면 -> B화면 -> A화면 순으로 이동을 합니다.

 

[2]함수 안의 지역변수에 대한 메모리를 관리할 때도 stack 자료구조를 이용해서 관리됩니다.

 

위의 내용을 토대로 코드를 작성해 보겠습니다.

먼저 Stack 이라는 구조체를 만들고 어떤 데이터 타입이든 Stack의 요소로 들어 올 수 있게 <Element> 라고 작성해 줍니다.

변수 중에 storage 라는 변수는 Element 타입의 요소를 배열 타입으로 가지고 있습니다. 즉, 배열로 stack을 구현할 코드 입니다.

public struct Stack<Element> {
    
    private var storage: [Element] = []
    
    public init() { }
    
    public init(_ elements: [Element]) {
      storage = elements
    }
}

extension Stack: CustomStringConvertible {

  public var description: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

 

위 구조체에 스택의 대표적인 함수인 push 와 pop 함수를 작성해 봅시다.

push 함수는 위에서 만들었던 배열에 append를 이용해서 배열에 데이터를 추가합니다. 그럼 배열의 제일 마지막에 요소가 추가됩니다.

 

pop은 위에서 만들었던 storage 배열에 popLast를 이용해서 배열의 제일 마지막에 있는 요소를 꺼내서 리턴합니다.

 //제일 마지막 위치에 요소 넣기 - [필수]
    public mutating func push(_ element: Element) {
        storage.append(element)
    }
    
    //제일 마지막 요소 리턴하고 삭제하기 - [필수]
    @discardableResult
    public mutating func pop() -> Element? {
        storage.popLast()
    }

 

이 외에도 필수적이지는 않지만 구현해놓으면 스택을 좀 더 편리하게 사용할 수 있는 함수들이 있습니다. 

peek 함수는 storage 배열의 마지막 요소를 삭제하지는 않고 리턴만 해줍니다. 

isEmpty는 배열안의 스택이 비었는지 체크해주는 변수입니다.

    //제일 마지막 요소 리턴 - 옵션
    public func peek() -> Element? {
     storage.last
    }

    //배열이 비었는지 체크 - 옵션
    public var isEmpty: Bool {
      peek() == nil
    }

 

stack 테스트

stack 자료구조에 숫자 1,2,3,4를 넣고 pop을 한번 실행했습니다.

//push둘 pop다 O (1) 시간 복잡도를 갖습니다.
var stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)

print("stack : \n\(stack)")


let poppedElement = stack.pop()
print("Popped: \(poppedElement)")

print("pop 이후 stack : \n\(stack)")

 

출력

stack : 
----top----
4
3
2
1
-----------
Popped: Optional(4)
pop 이후 stack : 
----top----
3
2
1
-----------

 

stack.zip

0.02MB

 

참고

코딩퀴즈 - ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9%ED%80%B4%EC%A6%88/id1625309702

코딩퀴즈 - aos

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication

 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/