주제: Create a simple stack structure
Stack은 놀랍도록 많은 양의 Applications에서 사용하는 간단한 data structure이다.
스택이란?
- A Stack is LIFO, Last-In-First-Out, data structure.
- 간단하게 구현 할수있음에도 불구하고, Stack은 data structure에서 발생하는 많은 문제를 풀 수 있는 열쇠이다.
- Stack에는 오직 두 개의 필수 operater가 필요하다.
- push: adding elements
- pop: removing elements
스택 예시
- iOS는 뷰 컨트롤러를 화면에 푸시하고 팝하기 위해 내비게이션 스택을 사용합니다.
- 메모리 할당은 아키텍처 수준에서 스택을 사용합니다. 지역 변수를 위한 메모리도 스택을 사용하여 관리됩니다.
- 미로에서 탈출하는 경로를 찾는 등의 분할 정복 알고리즘은 백트래킹을 용이하게 하기 위해 스택을 사용합니다.
Code
public struct Stack<Element> {
private var storage: [Element] = []
public init() { }
// 배열을 받아서 Stack으로 전환
public init(_ elements: [Element]) {
storage = elements
}
public mutating func push(_ element: Element) {
storage.append(element)
}
public mutating func pop() -> Element? {
storage.popLast()
}
// 스택의 마지막 요소 확인하기 (stack.isEmpty의 전초)
public func peek() -> Element? {
storage.last
}
public var isEmpty: Bool {
peek() == nil
}
}
// array literal data로 초기화 할 수 있게 설정
extension Stack: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: Element...) {
storage = elements
}
}
// stack을 출력할때 아래와 같이 출력되게 설정
extension Stack: CustomStringConvertible {
public var description: String {
"Top: \(storage.map { "\($0)"}.reversed().joined(separator: "")) : Bottom"
}
}배열 뒤집기
- 스택을 사용하여 배열의 내용을 역순으로 출력하는 함수를 생성하는 방법입니다.
public func printInReverse<T>(_ array: [T]) { var stack: Stack<T> = Stack() for value in array { stack.push(value) } while let value = stack.pop() { print(value) } } - 노드를 스택에 푸시하는 시간 복잡도는 O(n)이다. 값들을 팝하여 출력하는 데 걸리는 시간 복잡도도 O(n)이다. 전체적으로 이 알고리즘의 시간 복잡도는 O(n)이다.
- 함수 내에서 컨테이너(스택)를 할당하기 때문에, 공간 복잡도는 O(n)이다.
- 참고: 생산 코드에서 배열을 뒤집는 방법은 표준 라이브러리에서 제공하는 reversed() 메서드를 호출하는 것이다. Array에 대해 이 메서드는 시간과 공간 모두 O(1)이다. 이는 이 메서드가 게으르게 작동하고 원본 컬렉션으로의 역순 뷰만 생성하기 때문이다. 모든 항목을 순회하고 출력하면 예상대로 시간은 O(n)이 되지만 공간은 O(1)이 된다.
괄호 균형 검사
- 괄호가 균형을 이루는지 확인한다. 문자열이 주어졌을 때, "("와 ")" 문자가 있고 괄호가 문자열 안에서 균형을 이루면 true를 반환한다.
pubilc func checkBalancedParentheses(_ string: String) -> Bool {
var stack: Stack<String> = Stack()
for value in string {
if value == "(" {
stack.push("+")
} else if value == ")" {
if stack.isEmpty {
return false
} else {
stack.pop()
}
}
}
return stack.isEmpty
}- 이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 문자열의 문자 수이다. 스택 데이터 구조 사용으로 인해 공간 복잡도도 O(n)이 발생한다.
let array = ["a","b","c","d"]
var stack2 = Stack(array)
var stack3: Stack = [1,2,3,4,5]
var stack4: Stack = ["A","B"]
var stack5: Stack = ["s",1,nil] as Stack<Any?>
stack3
stack3.reversdOrder()
print(stack2)
print(stack3)
print(stack4)
print(stack5)
Top: d c b a : Bottom
Top: 5 4 3 2 1 : Bottom
Top: B A : Bottom
Top: nil Optional(1) Optional("s") : Bottom출처(참고문헌)
- https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/4-stacks
- https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/5-stack-challenges
제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.
감사합니다.
