[스위프트:자료구조] 스택: Stack: 자료구조: DataStructure: 쌓기: swift

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• [스위프트 : 자료구조] 스택: Stack: 자료구조: DataStructure: 쌓기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

• 스위프트로 구현한 알고리즘 : Algorithms in Swfit4
• [스위프트 : 알고리즘] 재귀호출 (1 / 6) : recursive: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 팩토리얼 (2 / 6) : factorial: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수

• Swift 주제별 분류
• [스위프트] 데이터 구조와 알고리즘을 배우는 이유
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략
• [스위프트 : 기초] 서브스크립트 : Subscript : 지름길
  
  
  

스택 자료구조 : Stack

• What is 'Stack'   
• 스택은 '어떤 것을 쌓는' 인간의 활동을 컴퓨터에서 표현하려는 시도에서 만들어진 자료구조 입니다.
• 택배원이 상자를 차곡차곡 쌓아서 정리했다고 생각하면, 그 '상자를 쌓는 것' 이 '스택'이고 그 '상자' 가 스택 자료구조의 '아이템' 입니다.
• 쌓은 상자를 다른 곳으로 옮긴다고 했을 때 맨 위의 상자부터 빼야하죠?( 물론 힘 좀 들여서 중간꺼만 쏙 빼도 되지만 자연스럽게 옮기려면 ) 
• 이렇게 상자가 들어온 순서대로 쌓이고, 마지막으로 순서대로 빼서 옮기는 과정이 스택의 원리 입니다. 
• '나중에 들어온 것이 먼저 빠진다.' 라고 하여 LIFO ( Last - In - First - Out ) 자료구조 라고 불립니다.
• 상자 뿐만이 아니라 일상생활에서는 '쌓는' 일이 많이 일어나는데 그것을 스택이라는 자료구조로 컴퓨터에선 사용합니다.
• iOS 프로그래밍에선 navigation controller 에서 stack 을 사용합니다. 참고^^
• 종류
• push : 스택의 맨 위에 데이터를 '쌓는' 것 입니다.
• pop : 스택의 맨 위의 데이터를 '빼내는' 것입니다. 빼내서 없애도 되고, 빼낸 것을 사용해도 됩니다.
• 구현
• push

public struct Stack<Element> {
    
    //MARK: - storage : 쌓여있는 것들 배열로
    private var storage = Array<Element>()
    public init(){}
    
    //MARK: - push : 쌓기
    public mutating func push(_ element: Element) { // push 위에 쌓기 .
        storage.append(element) // 배열의 appned 메소드로 push(쌓기) 를 표현합니다.
    }

• pop

 //MARK: - pop : 위에서 꺼내기
public mutating func pop() -> Element? { // pop 위에서 부터 꺼내기.
    return storage.popLast() // 배열의 popLast() 메소드를 사용해서 마지막에 있는 배열의 아이템 제거하는 연산 수행합니다!
}

• 쌓이는 것을 표현
• push 와 pop 을 구현했더라도, 이는 배열에 값을 추가하고, 마지막 배열의 값을 제거하는 것 뿐입니다.
• 이 배열로 저는 스택의 쌓기를 표현할 것입니다.
• Stack 구조체를 출력하면 나오는 description 을 이용해서 쌓기 표현하자!

extension Stack: CustomStringConvertible { 
    // CustomStringConvertible 프로토콜 채택.
    // description 정의하는 프로토콜입니다. 이를 채택한 객체를 출력할 때 내가 지정한 설명서를 출력하게 하는 것이죠!
    public var description: String { // 연산 프로퍼티로 실시간으로 바뀌는 Stack 의 stackElements 를 정의
        
        let topDivider = "--- top ---\n" // 출력했을 때 가장 윗쪽을 표현
        let bottomDivider = "\n ----------" // 출력했을 떄 가장 아랫쪽을 표현
        
        let stackElements = storage
            .map { (i) in // 배열에 있는 요소들을 클로저로 변경하는 연산 수행하는 메소드 map()
                "\(i)"
        }.reversed() // 문자열로 바뀐 배열의 요소를 거꾸로 정렬.
        .joined(separator: "\n") // 문자열 사이사이에 줄 바꿈 추가하기. 이게 쌓은 것처럼 표현하려고 전에 거꾸로 정렬 한 것입니다.
        
        return topDivider + stackElements + bottomDivider
    }
}

• 실행 
• 실행할 때 사용할 helper 메소드 example() 정의

public func example(of description: String, action: () -> ()) {
    print("---Example of \(description)---")
    action()
    print()
} 
 

• example 메소드는 두 번째 매개변수가 함수를 입력받게 되있죠? 클로저를 받으면 실행시키는 역할입니다.
• 그리고 이를 이용해서 Stack 구조체를 실행시켜 봅니다.
• push() 실행

example(of: "Stack") {
    var stack = Stack<Int>() // Stack 구조체 인스턴스 생성.
    stack.push(1) // 아이템을 가장 위에 쌓는 push 연산 수행.
    stack.push(2)
    stack.push(3)
    
    print(stack) // 스택 
}

• 결과
• push의 매개변수에 넣은 값 대로 쌓여있죠?

• pop() 실행
  

example(of: "Stack") {
    var stack = Stack<Int>() // Stack 구조체 인스턴스 생성.
    stack.push(1) // 아이템을 가장 위에 쌓는 push 연산 수행.
    stack.push(2)
    stack.push(3)
 
    stack.pop() // 가장 위의 아이템을 제거하는 pop 연산 수행.
    print(stack) 
}

• 결과
• pop 은 가장 위의 아이템을 제거하는 것이죠? 잘 수행 되었네요.

• 확장
• 제가 정의한 Stack 구조체는 초기화 함수가 init(){}  비어있으므로 초기값이 있더라도 지정해 줄 수 없는 문제가 있습니다.
• a b c d 가 있는데 d 까지 쌓여있는 곳에서 시작해야 하는데 스택 구조체로 표현하려면 어쩔 수 없이 a부터 새로 쌓아야 하죠.
• 이렇게 불편하면 안쓰죠? 그래서 초기화 함수를 좀 더 일반적인 상황에서 쓸 수 있도록 확장시키겠습니다.

public init(_ element: [Element]) {
    storage = element // 초기화 함수의 매개변수로 배열을 넣을 수 있음.
}

• 실행        

example(of: "Stack") {
    let array = ["A","B","C","D"] // 초기값.
    var stackk = Stack(array) // 초기값 배열을 매개변수에 넣어준다.
    print(stackk)
}

• 결과

전체 소스 파일