선형 자료구조

• 순서가 있는 선형 자료구조에 속한다

LIFO / FILO

• Last In First Out
• First In Last Out
• 스택의 가장 큰 특징으로 밑에서부터 쌓아 올리는 구조이다.
• 즉, 먼저 들어간 녀석은 맨 밑에 깔리게 되고, 마지막에 들어간 녀석이 맨 위에 쌓이게 된다.
• ex) 프링글스 통

Stack<Integer> stack = new Stack<>();
stack.push(1) // [1] O(1)
stack.push(2) // [1, 2]
stack.push(3) // [1, 2, 3]

int peek = stack.peek() // [1, 2, 3] O(1)

int peekElement = stack.pop() // peekElement == 3, [1, 2] O(1)

사용 예시

JVM에서의 스택

• JVM 스레드가 생겨날 때, 해당 스레드를 위한 스택도 생성된다.
• 스택에는 프레임이 차곡 차곡 쌓이게 된다.
• 프레임이란, 메소드가 호출될 때 생성되는 것으로, 메소드의 상태 정보를 저장한다.
  • 메소드의 상태 정보
    • Local Variables - 지역변수
    • Operand Stack - 메소드 내 계산을 위한 작업 공간
    • Run-Time Constant Pool Reference - 런타임 상수 풀(메서드 영역에 존재)의 참조
    • cf) String Pool - 힙 영역에 존재
• 스레드의 스택 사이즈를 초과하면 StackOverFlow가 발생한다. (재귀)

재귀(Recursion)와 스택

DFS에서의 스택

• 그래프 탐색 방법 중 하나인 DFS는 스택을 활용하여 구현한다.
• 스택으로 구현할 수 있으므로, 재귀를 통해서도 구현할 수 있다.

출처

• https://velog.io/@sun02/Swift-백준-1260-DFS와-BFS
• https://bentist.tistory.com/57
• https://johngrib.github.io/wiki/jvm-stack/