스택 Stack
- 스택의 데이터 구조는 개념적으로 객체들의 물리적 스택과 동일하다.
- 아이템을 스택에 추가할 때, 스택의 맨 위에 배치한다.
- 아이템을 스택에서 제거할 때 , 스택의 맨 위에서 제거한다.
- →
LIFO(Last-In-First-Out)
Stack Operations
- 스택은 유용하고, 매우 간단하다.
- 스택을 구축하는 메인 목표는 어떻게 데이터에 접근하는지를 enforce하는 것
Stack의 기본 연산자
push: 스택의 맨 위에 요소를 추가pop: 스택의 맨 위에서 요소를 제거- 이렇게 두 가지의 연산으로 인터페이스를 제한하는 것은 데이터구조의 한 쪽에만 요소를 추가하거나 제거할 수 있다는 것을 의미
- 컴퓨터 과학에서, 스택은
LIFO로 알려져 있다.
- 마지막에 추가된 요소Last-In들은 먼저 제거Firrst-Out된다. - 스택은 프로그래밍의 모든 분야에서 사용되는데,
- iOS에서의 Navigation Stack(push, pop 이용)
- 메모리 할당
- 검색, 정복conquer 알고리즘(ex. 미로 찾기)에서의 역추적
적용
import Foundation
public struct Stack<Element> {
private var storage: [Element] = []
public init() { }
}
extension Stack: CustomDebugStringConvertible {
public var debugDescription: String {
"""
----top----
\(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
-----------
"""
}
}
- Stack의 백업 스토리지 정의
- 사용하고자 하는 스택에 올바른 스토리지 타입을 선택하는 것이 중요
- 배열array는 append와 popLast를 통한 삽입과 제거의 연산에 constant time을 제공하기 때문에 확실한obvious 선택이다.
- 이 두가지 작업을 통해 스택의 LIFO를 가능하게 한다.
CustomDebugStringConvertible의 debugDescription
storage.map { "\($0)" }를 통해 엘레멘트들을 String에 매핑하는 배열을 생성reversed()를 사용해 기존의 배열을 뒤집는reverse 배열을 생성joined(separator:)를 사용하여 배열을 문자열string로 평평하게flattening한다. 줄바꿈 문자인"\n"를 이용하여 배열의 요소들을 분리할 수 있다.
이렇게하면 디버깅에 사용할 수 있는 스택 유형의 printable representaition이 만들어진다.
push and pop operations
- Stack에
push(),pop()추가
public struct Stack<Element> {
private var storage: [Element] = []
public init() { }
public mutating func push(_ element: Element) {
storage.append(element)
}
@discardableResult
public mutating func pop() -> Element? {
storage.popLast()
}
}- stack에 1,2,3,4 원소를 push()한 후, print()로 확인해보기
extension Stack: CustomDebugStringConvertible {
public var debugDescription: String {
"""
----top----
\(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
-----------
"""
}
}
- 위의 상황에서 stack의 원소들 4를 pop()해보기
if let popedElement = stack.pop() {
assert(4 == popedElement)
print("Poped: \(popedElement)")
}
print(stack)
assert: 디버깅에서 사용, 논리 조건이 항상 true인지 확인하고, false가 나면 종료한다. 위에서는 stack의 특성 상 마지막 값을 pop()하는 것이기 때문에, 4가 아닌 다른 값(ex. 3, 2, 1 등)을 넣으면 오류가 발생하고 코드가 종료된다.push(),pop()의 time complexity ⇒ O(1)
다른 연산자들
- 스택을 더 쉽게 사용할 수 있게 해 주는 몇 개의 연산자들이 있다.
public func peek() -> Element? {
storage.last
}
public var isEmpty: Bool {
peek() == nil
}peek(): 값의 변경 없이, 스택의 최상위 요소를 확인하는 것isEmpty: stack이 비었는지 확인
🔖 출처
🍫 iOS 🍫 Swift