안녕하세요. 개발하는 정주입니다.
오늘은 Stack(스택)을 정리했습니다.
Stack이란?
Stack이란 "어떤 것을 쌓는다"는 것을 표현하기 위해 만든 선형 자료 구조로 배열과 같지만 특정 기능에 특화된 배열입니다.
원소를 쌓는 것에 중점을 둔 배열인 셈이죠.
따라서 Stack을 활용하는 곳은 무언가를 쌓고 맨 위의 것을 빼는 구조라는 것을 추상적으로 알 수 있게 됩니다.
자료구조는 기능 구현도 중요하지만 이러한 개념을 파악하는 것도 중요한 점이라고 생각하네요.
Stack 특성
Stack의 가장 중요한 특성은 "LIFO"입니다. (리포가 아닌 라이포라고 읽습니다)
LIFO란 Last In First Out의 줄임말로 마지막에 들어온 원소가 가장 먼저 나간다는 의미입니다.
택배를 쌓으면 맨 위에 있는 택배부터 꺼내야 하는 것처럼 Stack도 원소를 push하면 가장 위(뒤)에 있는 원소를 pop 합니다.
이러한 특성 때문에 순서가 중요하며 가장 뒤에 있는 원소를 가져다 쓸 때 유용하게 사용할 수 있습니다.
Stack 기능
Stack은 크게 세 가지 기능으로 구성됩니다.
- push : 원소를 추가합니다.
- pop : 원소를 삭제합니다.
- peek(or top) : 맨 위의 원소를 가져옵니다.
Stack에 원소를 추가할 때는 항상 마지막에 추가됩니다.
따라서 O(1)의 시간복잡도로 원소를 추가할 수 있습니다.
Stack에서 원소를 지울 때는 항상 마지막의 원소가 삭제됩니다.
따라서 O(1)의 시간복잡도로 원소를 추가할 수 있습니다.
추가로, 마지막의 원소를 삭제하는 것이므로 원소를 앞으로 재배치하는 오버헤드가 발생하지 않습니다.
마지막으로 peek(top)도 항상 마지막 원소를 참조하므로 O(1)의 시간복잡도를 갖습니다.
원소를 하나씩 쌓고 "맨 뒤" 원소를 이용할 때 의미가 있는 자료구조이므로 중간 데이터 삭제같은 행위는 올바르지 않습니다.
Stack의 개념을 해칠 뿐만 아니라 효율도 좋지 않기에 주의하여야 합니다.
Stack 활용
Stack은 정말 여러 곳에서 사용이 됩니다.
- 역순 문자열 만들기
- 수식의 괄호 검사 (올바른 괄호인지)
- 후위 표기법 계산
운영체제에서의 Stack
뿐만 아니라 운영체제의 프로세스에서도 사용이 됩니다.
프로세스는 4개의 요소로 구성되어 있는데요. Stack, Heap, Data, Code입니다.
바로 여기서도 Stack이 사용이 됩니다.
프로세스의 Stack은 지역변수 할당과 함수 호출 시 전달되는 인자값들을 저장하고 함수의 호출에 관여합니다.
함수가 함수를 호출하거나 자기 자신을 호출하는 재귀 함수 동작도 Stack에 기반하고 있습니다.
함수 호출을 했을 때 이 함수가 끝난 뒤 자신을 호출한 함수로 돌아가야 합니다.
Stack에 함수가 복귀할 주소를 쌓아두고 완료가 되면 pop을 하며 재귀적으로 복귀하는 것입니다.
이 말이 이해가 안 된다면 재귀를 이용해 피보나치 수열을 구현해보면 좋을 것 같습니다.
iOS에서의 Stack
iOS를 개발하는 분들이라면 push, pop이 익숙하실 것입니다.
iOS의 Navigation Controller에서도 Stack 개념이 나오는데요.
Navigation Controller는 Navigation Stack을 관리하며
Navigation Stack은 Stack을 이용해 ViewController를 관리합니다.
Stack을 이용해 ViewController를 관리하기 때문에 ViewController를 생성, 삭제하는 메서드 이름이 pushViewController, popViewController인 것이죠.
Navigation Stack의 push는 UIViewController의 인스턴스를 생성해서 Navigation Stack에 추가합니다.
(https://developer.apple.com/documentation/uikit/uinavigationcontroller/1621887-pushviewcontroller)
Navigation Stack의 pop은 UIViewController를 메모리에서 해제하고 Navigation Stack에서 제거합니다.
(https://developer.apple.com/documentation/uikit/uinavigationcontroller/1621886-popviewcontroller)
Root ViewController는 가장 먼저 push된 ViewController이며 TopViewController는 맨 위의 View Controller, 즉 가장 마지막에 push된 ViewController입니다.
이렇게 iOS에서도 Stack 자료구조를 활용하는 것을 알 수 있습니다.
Swift로 Stack 구현하기
Swift로 Stack을 구현해보겠습니다.
사실 Swift는 popLast 메서드를 지원하기 때문에 굳이...라는 생각이 들긴 하지만
자료구조를 직접 구현하는 건 또 다른 의미이니 긍정적으로 생각합시다.
제가 구현한 Stack의 기능은 총 5가지 입니다.
- push : 원소를 맨 뒤에 추가합니다.
- pop : 맨 뒤의 원소를 삭제하고 삭제한 원소를 return합니다.
- top : 맨 뒤의 원소를 return합니다.
- size : Stack의 현재 크기를 return합니다.
- isEmpty : Stack이 비었는가를 return합니다.
Code
import Foundation
struct Stack<T> {
private var stack: [T] = []
public var size: Int {
return stack.count
}
public var isEmpty: Bool {
return stack.isEmpty
}
public mutating func push(_ element: T) {
stack.append(element)
}
public mutating func pop() -> T? {
return stack.popLast()
}
public mutating func top() -> T? {
return stack.last
}
}
var stack = Stack<Int>()
print("1) isEmpty? \(stack.isEmpty)")
stack.push(1)
stack.push(2)
print("2) isEmpty? \(stack.isEmpty)")
print("3) stack size: \(stack.size)")
print("4) top: \(stack.top())")
stack.pop()
print("5) top: \(stack.top())")
print("6) stack size: \(stack.size)")
1) true가 출력됩니다. 생성한 직후의 Stack은 당연히 비어있습니다.
2) false가 출력됩니다. Stack에는 [1, 2] 원소가 들어 있습니다.
3) 2가 출력됩니다.
4) 2가 출력됩니다. 맨 뒤의 원소를 출력합니다.
5) 1이 출력됩니다. 2가 pop이 되었기 때문에 맨 뒤의 원소는 1입니다.
6) 1이 출력됩니다. 남은 원소는 한 개입니다.
이렇게 Stack에 대해 알아보았습니다.
잘못된 점이 있다면 댓글로 알려주시면 감사하겠습니다.
감사합니다.