[Swift] Stack

LIFO 특성을 가지는 자료구조(Data Structure)를 일컫는다.
스택은 일종의 바닥이 막힌 상자라고 보면 된다. 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수밖에 없다.

스택이라는 자료구조는 프로세스를 구성하는 4개의 요소 중 한 부분이며 함수의 호출에 관여한다.

컴파일러가 출력하는 에러

스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다.

메모리 영역

LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다.

구현

배열을 이용한 구현

struct Stack<Element> {
  private var elements: [Element] = []

  // Stack에 원소를 추가
  mutating func push(_ item: Element) {
    elements.append(item)
  }

  // Stack에서 원소를 제거하고 반환
  mutating func pop() -> Element? {
    return elements.popLast()
  }

  // Stack의 맨 위 원소를 반환
  func peek() -> Element? {
    return elements.last
  }

  // Stack이 비어있는지 확인
  func isEmpty() -> Bool {
    return elements.isEmpty
  }

  // Stack의 원소 수를 반환
  func count() -> Int {
    return elements.count
  }
}

// Stack을 사용
var stack = Stack<Int>()

// 원소 추가
stack.push(1)
stack.push(2)
stack.push(3)

// 원소 제거
print(stack.pop()) // 출력: Optional(3)

// 맨 위 원소 확인
print(stack.peek()) // 출력: Optional(2)

// Stack이 비어있는지 확인
print(stack.isEmpty()) // 출력: false

// Stack의 원소 수 확인
print(stack.count()) // 출력: 2

LinkedList 를 이용한 구현

class LinkedListNode<Element> {
  var value: Element
  var next: LinkedListNode?

  init(value: Element) {
    self.value = value
  }
}

class LinkedList<Element> {
  private var head: LinkedListNode<Element>?

  var isEmpty: Bool {
    return head == nil
  }

  func append(_ value: Element) {
    let newNode = LinkedListNode(value: value)
    if let lastNode = lastNode() {
      lastNode.next = newNode
    } else {
      head = newNode
    }
  }

  func lastNode() -> LinkedListNode<Element>? {
    var currentNode = head
    while currentNode?.next != nil {
      currentNode = currentNode?.next
    }
    return currentNode
  }

  func removeLast() -> Element? {
    guard let head = head else {
      return nil
    }
    if head.next == nil {
      let value = head.value
      self.head = nil
      return value
    }

    var prev = head
    var current = head

    while let next = current.next {
      prev = current
      current = next
    }

    prev.next = nil
    return current.value
  }
}

// LinkedList를 사용하여 Stack을 구현
struct Stack<Element> {
  private var linkedList = LinkedList<Element>()

  var isEmpty: Bool {
    return linkedList.isEmpty
  }

  mutating func push(_ value: Element) {
    linkedList.append(value)
  }

  mutating func pop() -> Element? {
    return linkedList.removeLast()
  }

  func peek() -> Element? {
    return linkedList.lastNode()?.value
  }
}

// 구현한 Stack을 사용
var stack = Stack<Int>()

// 원소 추가
stack.push(1)
stack.push(2)
stack.push(3)

// 원소 제거
print(stack.pop()) // 출력: Optional(3)

// 맨 위 원소 확인
print(stack.peek()) // 출력: Optional(2)

// Stack이 비어있는지 확인
print(stack.isEmpty) // 출력: false

CPU의 제어

현대 CPU는 어셈블리어에 스택 영역을 제어하는 명령이 있다.
한 프로그램이 사용하는 스택 영역은 기본적으로 크기가 고정되어 있다.

종류

스택은 힙 영역 메모리에서 일반적인 데이터를 저장하는 스택
스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택

이것도 종류를 나눌 수 있는데,
Ascending stack VS Descending stack
Empty stack VS Full stack

출처

나무위키 - 스택(자료구조)