Kodeco | Swift의 데이터 구조 및 알고리즘 - Stack

안녕하세요 복잡성에 이어서 정리하고자 합니다

 

kodeco

 

 

사이트(클릭클릭👆🏻) kodeco에 들어가면 다양한 자료들을 볼 수 있으니 강추👍🏻👍🏻👍🏻👍🏻👍🏻 드립니다

강의보단 책이 좋다는 평이 있어서 저도 책으로 구매하였답니다 :)

 

---

 

Stack

스택

|

기본적으로 쌓다 라는 뜻을 가지고 있습니다

 

스택 데이터 구조는 개념적으로 객체의 물리적 스택과 동일하답니다

스택의 항목을 추가하면 해당 항목이 스택 맨 위에 놓이게 됩니다

 

자 팬케이크 / 서적 / 종이 / 현금

공통점은 뭘까요?

쌓을 수 있다는 점입니다

 

맨 처음 쌓게되면 젤 아래로 내려가게 되고

마지막에 쌓으면 제일 위로 올라가게되는것 처럼

 제거하게되면 항상 맨 위에 있는 항목이 제거되는것 처럼

stack도 마찬가집니다

 

그리고 놀라운점은 Swift에는 stack queue가 없는 사실을 아시나요??

 

C#에서는 그렇게 편리하게 썻던걸 여기선 구현을 해야한답니다

 

새 요소를 추가하려면 push 해야하고

상단에서 제거하려고하면 pop의 과정을 거쳐야합니다

 

kodeco

 

Stack Operation

스택 기능

|

스택은 매우 유용하면서 간단합니다

스택 구축의 주요 기능은 데이터에 액세스하는 방법을 적용하는 것입니다

 

스택에서는 두 가지 작업이 있습니다

push : 스택의 맨 위 요소를 추가

pop: 스택의 최근에 추가된 데이터 요소를 제거합니다

 

LIFO(후입선출)

Last In First Out

나중에 들어간 오브젝트가 먼저 나온다

 

여기서 더해서 peek이란 작업도 있습니다

이건 맨 마지막 오브젝트를 가지고 올 수 있습니다

 

https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/4-stacks

Data Structures & Algorithms in Swift, Chapter 4: Stacks

 

https://www.kodeco.com/800-swift-algorithm-club-swift-stack-data-structure

Swift Algorithm Club: Swift Stack Data Structure

 

구현

import UIKit

//스택은 저장할 자료형을 선택하는것이 중요합니다
public struct Stack<Element> {
    
  
  private var storage: [Element] = []

  public init() { }
}

//CustomDebugStringConvertible
//: debugDescription라는 읽기 전용 프로퍼티를 구현해야합니다
extension Stack: CustomDebugStringConvertible {

  public var debugDescription: String {
    //고차함수를 사용하여 기존 배열을 뒤집어서 정렬하고 저장되어있는 요소들을 병합합니다
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

 

배열은 append를 통해 한쪽 끝에서 일정한 삽입과 삭제를 제공합니다

LIFO

 

PUSH / POP

//스택은 저장할 자료형을 선택하는것이 중요합니다
public struct Stack<Element> {
    
  
  private var storage: [Element] = []

  public init() { }
  
  //⭐️ push  
  public mutating func push(_ element: Element) {
      storage.append(element)
  }
   //⭐️ pop
   //반환값을 사용하지 않아도 경고 메세지를 표시 하지않음
   //참고로 와일드카드 패턴이나 반환값(변수저장)하지 않아도 괜찮다는 의미
   @discardableResult
   public mutating func pop() -> Element? {
        storage.popLast()
   }
}

//CustomDebugStringConvertible
//: debugDescription라는 읽기 전용 프로퍼티를 구현해야합니다
extension Stack: CustomDebugStringConvertible {

  public var debugDescription: String {
    //고차함수를 사용하여 기존 배열을 뒤집어서 정렬하고 저장되어있는 요소들을 병합합니다
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

var stack = Stack<Int>()
    
//push, pop 둘 다 시간 복잡도 O(1)을 가집니다
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
stack.push(6)
    
print(stack)

if let element = stack.pop() {
    assert(6 == element)
    print("popped: \(element)")
}

/*
print
----top----
6
5
4
3
2
1
-----------
popped: 6
*/

 

 

Peek

//⭐️ peek
    public func peek() -> Element? {
        storage.last
    }
    
    public var isEmpty: Bool {
        peek() == nil
    }

 

이렇게 추가적으로도 사용할 수 있습니다

peek은 컴퓨터 용어로

구조에서 요소를 제거하지 않고 최상위 요소나 다음 요소를 확인하는 동작으로

최상위 요소가 있는지 유무를 확인하기전 Bool 자료형으로 확인하고 있으면 반환하는 코드를 만들어볼 수 있겠구나 하고 생각했습니다

 

Init

  //⭐️ init
    public init(_ element: [Element]) {
        storage = element
    }

 

추가하고 임의의 배열을 만들어 init에 넣어주게되면 활용을 할 수 있겠죠?

 

print("initializing a stack from an array")
  let array = ["A", "B", "C", "D"]
  var stack = Stack(array)
  print(stack)
  stack.pop()
  print(stack)

/*
initializing a stack from an array
----top----
D
C
B
A
-----------
----top----
C
B
A
-----------
*/

 

반대로 나오는 이유는 우리가 위에 배열을

reversed()를 해주었기 때문입니다

 

그리고 추가적으로

배열리터럴 확장을 통해서

직관적으로 스택구현을 할 수 있습니다

 

//배열 Literal type에 준수하도록 확장하는걸 확인할 수 있음
//간단한 배열 리터럴을 사용해서 인스턴스를 생성할 수 있을것 같음
extension Stack: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: Element...) {
        storage = elements
    }
}

 

print("initializing a stack from an array literal")
var stack: Stack = [1.0, 2.0, 3.0, 4.0]
print(stack)
stack.pop()

/*
initializing a stack from an array literal
----top----
4.0
3.0
2.0
1.0
-----------
*/

 

 

예전에 짯던 코드를 보고싶다면 읽어주세용 :)

 

 

 

 

push 의 경우  새로운 데이터를 하나  추가한다고  생각하면됩니다

 

 

 

 

 

그리고 peek의 경우

 데이터를 삭제하지않고 마지막 데이터를

가지고 옵니다!

 

 

pop의 경우 마지막 인덱스를 삭제해버린답니다

마치 배열에서 사용하는 removeLast와 동일한 기능이라고 생각이 들죠?

 

시간 복잡도를 생각하면

늘 마지막에 추가되고 삭제되기 때문에 시간 복잡도는 O(1)

 

그래서 오버헤드가 발생하지않는답니다 :)

 

배열을 그냥 사용해도 되겠는데 굳이 스택을 사용하는 이유는 뭘까?

라고 GPT에게 물어봤습니다

 

 

 

 

스택은 LIFO(후입선출)데이터 구조

매우 단순하지만 스택은 많은 곳에서 사용하고 있습니다

스택은 유일한 두 가지 필수 작업은 PUSH / POP

 

 

 

 

❤️혹시나 잘못된 부분이 있다면 댓글로 알려주면 감사하겠습니다❤️

 

 

 

 

참고

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

 

 

 

https://www.kodeco.com/800-swift-algorithm-club-swift-stack-data-structure

Swift Algorithm Club: Swift Stack Data Structure

 

+ 내 머리